Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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.
```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++;
}
/*
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;
}
}```

2. ## Re: Simplex algorithm java

This thread has been cross posted here:

Java Programming Forums Cross Posting Rules

3. ## Re: Simplex algorithm java

still didn't find a bug.
How do you know there is a bug?

4. ## Re: Simplex algorithm java

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

5. ## 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.