# Simplex algorithm java

Printable View

• November 29th, 2012, 11:29 AM
musicalwatch
Simplex algorithm java
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; } }```
• November 29th, 2012, 12:25 PM
copeg
Re: Simplex algorithm java
This thread has been cross posted here:

Although cross posting is allowed, for everyone's benefit, please read:

Java Programming Forums Cross Posting Rules

The Problems With Cross Posting

• November 29th, 2012, 12:45 PM
Norm
Re: Simplex algorithm java
Quote:

still didn't find a bug.
How do you know there is a bug?
• November 29th, 2012, 01:11 PM
musicalwatch
Re: Simplex algorithm java
Quote:

Originally Posted by Norm
How do you know there is a bug?

I have tested it with several inputs and only got either "No" or "Unbounded" outputs. I used the textbook examples which definitely had solutions
• November 29th, 2012, 01:14 PM
Norm
Re: Simplex algorithm java
Then try debugging the code to see where it is going wrong.
I use printlns to print out the values of variables as they are used. If you have an interactive debugger try that.
If you understand the algorithm, the debug output should show you where the program is going wrong.