Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Nov 2012
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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;
        }
    }
    Last edited by musicawlatch; 11-29-2012 at 07:00 AM.

  • #2
    New Coder
    Join Date
    Aug 2014
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    •