Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## 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++;
}
/*
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. In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century.The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•