| musicawlatch |
11-29-2012 06:54 AM |
Simplex algorithm problem
Hey guys! I am trying to write a Simplex algorithm program that reads input from a file. It runs but every time gives a no solution output ('No').
I have spent several days working on this program and still didn't find a bug.
Code:
import java.util.*;
import java.io.*;
import java.math.*;
public class first {
public static void main (String[]args) throws IOException {
/* Reading input from a file*/
File inputFile = new File("input.txt");
Scanner in = new Scanner(inputFile);
// Reading the number of free variables
int n = in.nextInt();
// Reading the number of equations
int m = in.nextInt();
// Defining indexes
int i=0, j=0, k=0, l=0;
double f = 0;
//Creating a simplex tableau
double[][] S = new double[m+1][n+m+1];
// Helping variable
double x=0;
// A very big number
int M=10000;
// Filling up the coefficients of function z
for (i = 0; i < n; i++)
S[m][i] = in.nextDouble();
// Filling up the coefficients of constraint equations
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
S[i][j] = in.nextDouble();
// Filling up the RHS
for (i = 0; i < m; i++) {
S[i][n+m] = in.nextDouble();
// if RHS is negative, change the sign
if (S[i][n+m]<0) {
S[i][n+m]=-S[i][n+m];
for (j = 0; j < n; j++)
S[i][j]=-S[i][j];
}
x+=S[i][n+m];
//Adding basis variables to the simplex table
S[m][n+i]=0;
S[i][n+i]=1;
}
S[m][m+n] = x*M;
x=0;
// Changing the last row/column of the tableau
for (j = 0; j < n; j++)
{
for (i = 0; i < m; i++)
x+=S[i][j];
S[m][j]=x*M - S[m][j];
x=0;
}
// Now the tableu is filled up
// Creating an array for the basis indexes
int[] num = new int[n];
for(i=0; i<n;i++)
num[i]=-1;
int ni=0; // number of variables in the basis
File outputFile = new File("output.txt");
BufferedWriter bw= new BufferedWriter(new FileWriter(outputFile, false));
//Test to see check what is in the tableau
for(i=0;i<=m;i++){
for(j=0;j<=m+n;j++){
System.out.println(S[i][j] + " ");
}
}
//--------------------------------------------------------------------//-----------------------ALGORITHM-------------------------------------//--------------------------------------------------------------------
x=S[m][0];
for (j = 1; j < n; j++)
if (S[m][j]<x) {
x=S[m][j];
k=j;
}
//Writing k in the array of basis variables
num[ni]=k;
ni++;
while (S[m][k]>0) {
x=10000;
for (i = 0; i < m; i++)
if (S[i][k] > 0) // For the positive values we count (S[i][n+m]/S[i][k])
if ((S[i][n+m]/S[i][k]) < x) { //Find the minimum among them
x = S[i][n+m]/S[i][k];
l=i;
}
//If all elements of the column are <= 0, there are no solutions
if (((x-10000)<1.e-009)||((x-10000)>-(1.e-009))) {
bw.write ("No");
bw.flush();
bw.close();
return;
}
// We found k and l indexes, so now we can perform the Gauss-Jordan method
x=S[l][k];
for (j = 0; j <= m+n; j++)
S[l][j]/=x;
for (i=0; i<=m; i++) {
x=S[i][k];
if(i!=l)
for (j = 0; j <= m+n; j++)
S[i][j]=S[i][j]-(S[l][j]*x);
}
// Finding the largest maximum element in the last row
x=S[m][0];
for (j = 1; j < n; j++)
if (S[m][j]>x) {
x=S[m][j];
k=j;
}
num[ni]=k; // Record the index in the array of indexes of basis variables
ni++;
// After the first iteration we return to Step 1
}
/*
for(i=0;i<=m;i++){
for(j=0;j<=m+n;j++){
String str3 = new String();
str3 = Double.toString(S[i][j]);
bw.write(str3);
bw.write(" ");
}
bw.write("\n");
}
bw.write("\n"); */
// At this point, we got a solution. Need to check it
for (j = n; j < n+m-1; j++)
{if ((S[m][j]<1.e-009)&&(S[m][j]>-(1.e-009)))
if ((S[m][m+n]<1.e-009)&&(S[m][m+n]>-(1.e-009))) {
bw.write ("Unbounded");
bw.flush();
bw.close();
return;
}
else {
bw.write ("No");
bw.flush();
bw.close();
return;
}
}
// If the solution is not unbounded, then the solution is found.
bw.write("Yes\n");
double f1;
f1 = S[m][n+m];
new BigDecimal(f1).setScale(6, BigDecimal.ROUND_HALF_EVEN);
String str1 = new String();
str1 = Double.toString(f1);
str1 = String.format("%8.6f", f1).replace(',','.');
bw.write(str1.replaceAll(" ","") + "\n");
//bw.write(Double.toString(S[m][n+m])+"\n");
for(i=0;i<n;i++)
{
if ((S[m][i]<1.e-009)&&(S[m][i]>-(1.e-009))) {
for (j=0; j<m;j++)
if ((S[j][i]-1<1.e-009)&&(S[j][i]-1>-(1.e-009))) {
f = S[j][n+m];
new BigDecimal(f).setScale(6, BigDecimal.ROUND_HALF_EVEN);
String str = new String();
str = Double.toString(f);
str = String.format("%8.6f", f).replace(',','.');
bw.write(str.replaceAll(" ",""));
//bw.write(Double.toString(S[j][n+m]));
bw.write(" ");
}
} else
bw.write("0.000000 ");
}
bw.flush();
bw.close();
return;
}
}
|
