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,641
    Rep Power
    8

    Default Re: Simplex algorithm java

    Cross posted at Simplex algorithm java

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,045
    Blog Entries
    7
    Rep Power
    23

    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
    The only person who got everything done by Friday was Robinson Crusoe.

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, 08: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
  •