Results 1 to 3 of 3
  1. #1
    musicalwatch is offline Member
    Join Date
    Nov 2012
    Posts
    1
    Rep Power
    0

    Default 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.

    Java 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;
        }
    }

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default Re: Simplex algorithm java

    Cross posted at Simplex algorithm java

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,574
    Blog Entries
    7
    Rep Power
    21

    Default Re: Simplex algorithm java

    I didn't wade through all that code but a big-M value 10000 isn't very big and it most certainly shouldn't participate in actual calculations.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. * Help: Java Code For Cpu Scheduling Algorithm
    By coldvoice05 in forum New To Java
    Replies: 1
    Last Post: 07-15-2009, 04:30 AM
  2. run MD5 algorithm in Java Servlet
    By avinash4m in forum Java Servlet
    Replies: 0
    Last Post: 03-12-2009, 07:20 PM
  3. Java Algorithm problems?
    By JavaInLove in forum New To Java
    Replies: 8
    Last Post: 07-02-2008, 08:50 AM
  4. Using Java To Implement RSA Algorithm
    By Floetic in forum New To Java
    Replies: 3
    Last Post: 03-31-2008, 11:56 PM
  5. Help with algorithm in java
    By coco in forum AWT / Swing
    Replies: 1
    Last Post: 08-01-2007, 06:45 AM

Posting Permissions

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