Thread: 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++;
	    // 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;
    }
}

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