Simplex Method program unknown logic error

[asoo]

Hi,
Her is a program that I write to solve a simplex method problem, the program is right and working good with almost all the examples I used to test it, but only one generate a problem making the program processing in an infinite loop until the buffers are overloaded.
her the way of calculating simplex method
her the way of calculating simplex method (http://www.universalteacherpublications.com/univ/ebooks/or/Ch3/simalgo.htm)

and this is the example generate the problem
Maximize z=3x1 + 2x2
subject to
-x1 + 2x2 <= 4
3x1 + 2x2 <= 14
x1 - x2 <= 3

x1, x2 >= 0

The Solution (http://www.universalteacherpublications.com/univ/ebooks/or/Ch3/simplex.htm)

My program solving it in right way until calculating the last value it produce a wrong number then repeat that last calculating - the program depend in looping until the right result show up - .

In my program there are 2 classes
this is the class calculating the result

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.*;

class Equations extends JFrame implements ActionListener{
JTextField[][] t;
JLabel[][] l;
JTextField[] b1;
JRadioButton[] less, greater;
float[][] a;
float[] b2 , c , cb , zMc;
public int n1 , m1 ;
JButton d , con ;
JPanel[] panel1 , panel2;
int ch;

public Equations (int n , int m) { ch=0;
n1 = n;
m1 = m ;
// Create Panels
JPanel p1 = new JPanel();
p1.setLayout(new GridLayout(m1+1,1));
JPanel p2 = new JPanel();
panel1 =new JPanel[m1];
for ( int i=0 ; i < m1 ; i++){
panel1[i] = new JPanel();
}
panel2 =new JPanel[m1];
for ( int i=0 ; i < m1 ; i++){
panel2[i] = new JPanel();
}

t = new JTextField[m1][n1];
l = new JLabel[m1][n1];
b1 = new JTextField[m1];
less = new JRadioButton[m1-1];
greater = new JRadioButton[m1-1];
for ( int i = 0; i < m-1; i++) {
less[i] = new JRadioButton("<=");
greater[i] = new JRadioButton(">=");
less[i].addActionListener(this);
greater[i].addActionListener(this);
}
a = new float[m1-1][n1+m1-1];
b2 = new float[m1-1];
c = new float[n1+m1-1];
zMc = new float[n1+m1-1];
cb = new float[m1-1];

// Create Textfields & Labels & add them
panel1[0].add(new JLabel("z ="));
for ( int i=0 ; i < m1 ; i++){
for ( int j=0 ; j < n1 ; j++ ) {
t[i][j] = new JTextField(2);
l[i][j] = new JLabel("x" + (j+1));
panel1[i].add (t[i][j]);
panel1[i].add (l[i][j]);
if ( j+1 == n1 && i != 0) {
panel1[i].add(less[i-1]);
panel1[i].add(greater[i-1]);
b1[i-1] = new JTextField(2);
panel1[i].add(b1[i-1]);
}
else {
if ( j+1 != n1 )
panel1[i].add(new JLabel("+"));}
}
p1.add(panel1[i]);
}

d = new JButton("insert");
d.addActionListener(this);
p2.add(d);
con=new JButton("convert");
con.addActionListener(this);
p2.add(con);
p1.add(p2);

add(p1);

}

/////////////// Events ///////////////////

public void actionPerformed(ActionEvent e ) {
if ( e.getSource()==d){
insert();
insertT();
}
if ( e.getSource()==con){
convert();
}
}

/////////////// Convert Inequality to Equalities///////////////////

public void convert() {
JFrame f=new JFrame();
JPanel p2=new JPanel();
p2.setLayout(new GridLayout(m1,1));

panel2[0].add(new JLabel("z ="));

for ( int i=0 ; i < m1 ; i++){
for ( int j=0 ; j <= n1 ; j++ ) {
if ( i == 0 && j == n1)
continue;
if ( j == n1 ){
if ( less[i-1].isSelected())
panel2[i].add(new JLabel(" + x" + (n1+i)));
else
panel2[i].add(new JLabel(" - x" + (n1+i)));
panel2[i].add(new JLabel(" = " + b1[i-1].getText()));
continue;
}
panel2[i].add(new JLabel(t[i][j].getText() + "x" + (j+1)));

if ( j+1 != n1 )
panel2[i].add(new JLabel("+"));

}
p2.add(panel2[i]);
}

f.add(p2);
f.setVisible(true);
f.setSize(200, 200);
}

////////////////Fill The Arrays//////////////////
void insert() {
for ( int i=0 ; i < m1 ; i++){
for ( int j=0 ; j <= n1 ; j++ ) {
if (i == 0 )
if ( j == n1)
continue;
else{
c[j]=Integer.parseInt(t[i][j].getText());
//System.out.print(c[j]);
}
else if ( j == n1) {
b2[i-1]=Integer.parseInt(b1[i-1].getText());
//System.out.print(b2[i-1]);
}
else {
a[i-1][j]=Integer.parseInt(t[i][j].getText());
//System.out.print(a[i-1][j]);
}

}
//System.out.println();
}

// Complete filling array a[][]
for ( int i = 0 ; i < m1-1 ; i++){
for ( int j = n1 ; j < n1+m1-1 ; j++ ) {
if ( i+n1 == j){
if ( less[i].isSelected())
a[i][j] = 1;
else
a[i][j] = -1;
}
}
}

}

/////////////// Insert The Values into Table ///////////////////

public void insertT() {
calculateZminC ();

String[] s = new String[m1+2];
for ( int i = 0 ; i < m1+2 ; i++){
s[i] = new String();
}
s[0] = " Cj ";
s[1] = "Cb B ";
s[m1+1] = "Zj-Cj ";

for ( int i=0 ; i < m1+2 ; i++){
for ( int j=0 ; j <= n1+m1 ; j++){
if ( j >= m1+n1-1 && (i == 0 || i == 1 || i == m1+1 ))
continue;
else
if ( j == n1+m1)//last column
s[i] += " " + b2[i-2];
else {
if ( i == 0 ) //all variables coefficients
s[i] +=" " + c[j];
else
if ( i == 1) //all variables names
s[i] += " " + "X" + (j+1);
else
if ( i == m1+1) // Zj - Cj
s[i] += " " + zMc[j];
else
if ( j == 0 ) // basic variables coefficients
s[i] += cb[i-2] + " X" + (n1+i-1);
else // values of a
s[i] += " " + a[i-2][j-1];
}
}
}
s[1] += " b(Xb)";

for ( int i = 0 ; i < m1+2 ; i++){
System.out.println(s[i]);
}

int check = 0 , t=0;
for ( int i = 0 ; i < n1+m1-1 ; i++){
if ( zMc[i] < 0){
calculatePivot();
check = 1;
t=check;
check++;
break;
}
}
if ( check == t)
result();

}

/////////////// Calculate Zj-Cj ///////////////////
void calculateZminC () {
float temp;
for ( int i=0 ; i < n1+m1-1 ; i++){
temp=0;
for ( int j=0 ; j < m1-1 ; j++ ) {
temp += (a[j][i] * cb[j]);
}
zMc[i] = temp - c[i];
}
}


/////////// Calculate Pivot /////////////////

void calculatePivot() {
int i = 1;
int keyCol=0 , keyRow=0;

// Calculate key column
float keyColValue = zMc[0];
while ( i < n1 ) {
if ( zMc[i] < keyColValue && zMc[i] < 0){
keyColValue = zMc[i];
keyCol = i;
}
i++;
}//Calculate key column end

i = 1; //Reset i
// Calculate key row
float keyRowValue = ( b2[0] / positive(a[0][keyCol]) );
while ( i < m1-1 ) {
float temp = ( b2[i] / positive(a[i][keyCol]) );
if ( temp < keyRowValue ){
keyRowValue = temp;
keyRow = i;
}
i++;
}//Calculate key row end

float pivot = a[keyRow][keyCol];
System.out.println(keyColValue+" keyCol= "+keyCol + " keyRow = " + keyRow+" "+keyRowValue + " pivot" + pivot);
tableCells( keyRow , keyCol , pivot);
}


/////////// Calculate Table Cells /////////////////

void tableCells( int keyRow , int keyCol , float pivot) {

float[] keyRowValues= new float[n1+m1];
float[] keyColValues = new float[m1-1];
// saving the key row & key column values
for ( int i = 0 ; i < n1+m1-1 ; i++ )
keyRowValues[i] = a[keyRow][i];
keyRowValues[n1+m1-1] = b2[keyRow];

for ( int i = 0 ; i < m1-1 ; i++ )
keyColValues[i] = a[i][keyCol];

for ( int i=0 ; i < m1-1 ; i++) {
for ( int j = 0 ; j < n1+m1-1 ; j++){
if ( i == keyRow)
a[i][j] /= pivot ;
else
{System.out.println("a["+i+"]["+j+"] = "+a[i][j]+"-"+keyRowValues[j] +"*"+ keyColValues[i] +" /"+ pivot);

a[i][j] = a[i][j] - ( keyRowValues[j] * keyColValues[i] ) / pivot ;
}
System.out.println("a["+i+"]["+j+"] = "+a[i][j]);
}
if ( i == keyRow)
b2[i] /= pivot ;
else
b2[i] = b2[i] - ( keyRowValues[n1+m1-1] * keyColValues[i] ) / pivot ;
System.out.println("b["+i+"] = "+b2[i]);
}
cb[keyRow] = c[keyCol];
//show the table again
insertT();
//loop();
}

float positive ( float test) {
if ( test < 0 )
return ( -1 * test );
else
return test ;
}

////////// Result /////////////

void result() {
float z=0;
for ( int i = 0 ; i < n1 ; i++ ) {
for ( int j = 0 ; j < m1-1 ; j++ ) {
if ( c[i] == cb[j])
z += cb[j] * b2[j];
}
}
System.out.println("z = " + z );
}
}


and this is the class containing main

//starter class
import javax.swing.*;
public class SimplexMethod {

public static void main (String[] args) {

int n=Integer.parseInt(JOptionPane.showInputDialog("Please enter the number of your variables"));

int m=Integer.parseInt(JOptionPane.showInputDialog("Please enter the number of your constraints"));
Equations slack = new Equations( n , m + 1);
slack.setSize(300,200);
slack.setVisible(true);

}
}


Please try it to figure out what I mean and if there is any thing not clear ask me, I really to try to correct it but I failed beside I am not professional so it most contain some thing not good programing practice.

[Norm]

The way to solve logic errors is to add println() statements to your code so you can see how the values change. This can be a tedious and lengthy process, but sometimes is the only/best way to find your logic error.

[asoo]

yeah if u run my code u will find I try that actually but still don't know what cause this error
The program suppose to stop after calculation of the 3rd table in this example but there's one number which is not right causing the program to loop in an infinite loop
This is the table:
Cj 3.0 2.0 0.0 0.0 0.0
Cb B X1 X2 X3 X4 X5 b(Xb)
0.0 X3 0.0 0.0 1.0 -0.2 1.6 6.0
2.0 X4 0.0 1.0 0.0 0.2 -0.6 1.0
3.0 X5 1.0 0.0 0.0 0.2 0.39999998 4.0
Zj-Cj 0.0 0.0 0.0 1.0 -1.1920929E-7

The program should produce 0 instead of -1.1920929E-7 to stop the other numbers is right all other examples I test too.
I hope I make it clear now.

[Norm]

Where is the value -1.1920929E-7 computed? Why do you think it should be 0?

[ajhampson]

I don't have a solution, but I do have some comments related to this:
I am not professional so it most contain some thing not good programing practice.

Your class members should all have access modifiers (http://java.sun.com/docs/books/tutorial/java/javaOO/accesscontrol.html) (public, private, or protected) applied. Without this, they are all public or package private.

Was there a reason you created a second class just for the main? The main can be part of the class it's accessing.

You should set a default close operation on your JFrame so it can be closed without using CTRL-C

Your indentation seems to be random. Especially here: for ( int i=0 ; i < m1+2 ; i++){
for ( int j=0 ; j <= n1+m1 ; j++){
if ( j >= m1+n1-1 && (i == 0 || i == 1 || i == m1+1 ))
continue;
else
if ( j == n1+m1)//last column
s[i] += " " + b2[i-2];
else {
if ( i == 0 ) //all variables coefficients
s[i] +=" " + c[j];
else
if ( i == 1) //all variables names
s[i] += " " + "X" + (j+1);
else
if ( i == m1+1) // Zj - Cj
s[i] += " " + zMc[j];
else
if ( j == 0 ) // basic variables coefficients
s[i] += cb[i-2] + " X" + (n1+i-1);
else // values of a
s[i] += " " + a[i-2][j-1];
}

It was really difficult to see what was going on.

Don't put code statements right after opening brackets (i.e. { i=0; ), especially right at the start of classes or methods..

Don't put closing brackets right after code (i.e. x-0; } ), it makes them hard to find.

You should consider always using brackets with loop and if constructs. This makes the code clearer and protects you from bugs if you go back and add another line later.

Be consistent about code formatting. Decide on a single style and use it.

You might also consider using more descriptive names for your variables. Names like f, p1, p2, n1, etc. confuse other readers and will only make things hard for you when you come back to read the code later.

Putting most of the above together and you get the following:
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.*;

class Equations extends JFrame implements ActionListener
{

JTextField[][] t;
JLabel[][] l;
JTextField[] b1;
JRadioButton[] less, greater;
float[][] a;
float[] b2, c, cb, zMc;
public int n1, m1;
JButton d, con;
JPanel[] panel1, panel2;
int ch;

public Equations(int n, int m)
{
ch = 0;
n1 = n;
m1 = m;
// Create Panels
JPanel p1 = new JPanel();
p1.setLayout(new GridLayout(m1 + 1, 1));
JPanel p2 = new JPanel();
panel1 = new JPanel[m1];
for (int i = 0; i < m1; i++)
{
panel1[i] = new JPanel();
}
panel2 = new JPanel[m1];
for (int i = 0; i < m1; i++)
{
panel2[i] = new JPanel();
}

t = new JTextField[m1][n1];
l = new JLabel[m1][n1];
b1 = new JTextField[m1];
less = new JRadioButton[m1 - 1];
greater = new JRadioButton[m1 - 1];
for (int i = 0; i < m - 1; i++)
{
less[i] = new JRadioButton("<=");
greater[i] = new JRadioButton(">=");
less[i].addActionListener(this);
greater[i].addActionListener(this);
}
a = new float[m1 - 1][n1 + m1 - 1];
b2 = new float[m1 - 1];
c = new float[n1 + m1 - 1];
zMc = new float[n1 + m1 - 1];
cb = new float[m1 - 1];

// Create Textfields & Labels & add them
panel1[0].add(new JLabel("z ="));
for (int i = 0; i < m1; i++)
{
for (int j = 0; j < n1; j++)
{
t[i][j] = new JTextField(2);
l[i][j] = new JLabel("x" + (j + 1));
panel1[i].add(t[i][j]);
panel1[i].add(l[i][j]);
if (j + 1 == n1 && i != 0)
{
panel1[i].add(less[i - 1]);
panel1[i].add(greater[i - 1]);
b1[i - 1] = new JTextField(2);
panel1[i].add(b1[i - 1]);
}
else
{
if (j + 1 != n1)
{
panel1[i].add(new JLabel("+"));
}
}
}
p1.add(panel1[i]);
}

d = new JButton("insert");
d.addActionListener(this);
p2.add(d);
con = new JButton("convert");
con.addActionListener(this);
p2.add(con);
p1.add(p2);

add(p1);
}

// ///////////// Events ///////////////////

public void actionPerformed(ActionEvent e)
{
if (e.getSource() == d)
{
insert();
insertT();
}
if (e.getSource() == con)
{
convert();
}
}

// ///////////// Convert Inequality to Equalities///////////////////

public void convert()
{
JFrame f = new JFrame();
JPanel p2 = new JPanel();
p2.setLayout(new GridLayout(m1, 1));

panel2[0].add(new JLabel("z ="));

for (int i = 0; i < m1; i++)
{
for (int j = 0; j <= n1; j++)
{
if (i == 0 && j == n1)
continue;
if (j == n1)
{
if (less[i - 1].isSelected())
{
panel2[i].add(new JLabel(" + x" + (n1 + i)));
}
else
{
panel2[i].add(new JLabel(" - x" + (n1 + i)));
}
panel2[i].add(new JLabel(" = " + b1[i - 1].getText()));
continue;
}
panel2[i].add(new JLabel(t[i][j].getText() + "x" + (j + 1)));

if (j + 1 != n1)
{
panel2[i].add(new JLabel("+"));
}

}
p2.add(panel2[i]);
}

f.add(p2);
f.setVisible(true);
f.setSize(200, 200);
}

// //////////////Fill The Arrays//////////////////
void insert()
{
for (int i = 0; i < m1; i++)
{
for (int j = 0; j <= n1; j++)
{
if (i == 0)
{
if (j == n1)
{
continue;
}
else
{
c[j] = Integer.parseInt(t[i][j].getText());
// System.out.print(c[j]);
}
}
else if (j == n1)
{
b2[i - 1] = Integer.parseInt(b1[i - 1].getText());
// System.out.print(b2[i-1]);
}
else
{
a[i - 1][j] = Integer.parseInt(t[i][j].getText());
// System.out.print(a[i-1][j]);
}

}
// System.out.println();
}

// Complete filling array a[][]
for (int i = 0; i < m1 - 1; i++)
{
for (int j = n1; j < n1 + m1 - 1; j++)
{
if (i + n1 == j)
{
if (less[i].isSelected())
{
a[i][j] = 1;
}
else
{
a[i][j] = -1;
}
}
}
}

}

// ///////////// Insert The Values into Table ///////////////////

public void insertT()
{
calculateZminC();

String[] s = new String[m1 + 2];
for (int i = 0; i < m1 + 2; i++)
{
s[i] = new String();
}
s[0] = " Cj ";
s[1] = "Cb B ";
s[m1 + 1] = "Zj-Cj ";

for (int i = 0; i < m1 + 2; i++)
{
for (int j = 0; j <= n1 + m1; j++)
{
if (j >= m1 + n1 - 1 && (i == 0 || i == 1 || i == m1 + 1))
{
continue;
}
else if (j == n1 + m1)// last column
{
s[i] += " " + b2[i - 2];
}
else
{
if (i == 0) // all variables coefficients
{
s[i] += " " + c[j];
}
else if (i == 1) // all variables names
{
s[i] += " " + "X" + (j + 1);
}
else if (i == m1 + 1) // Zj - Cj
{
s[i] += " " + zMc[j];
}
else if (j == 0) // basic variables coefficients
{
s[i] += cb[i - 2] + " X" + (n1 + i - 1);
}
else
// values of a
{
s[i] += " " + a[i - 2][j - 1];
}
}
}
}
s[1] += " b(Xb)";

for (int i = 0; i < m1 + 2; i++)
{
System.out.println(s[i]);
}

int check = 0, t = 0;
for (int i = 0; i < n1 + m1 - 1; i++)
{
if (zMc[i] < 0)
{
calculatePivot();
check = 1;
t = check;
check++;
break;
}
}
if (check == t)
result();

}

// ///////////// Calculate Zj-Cj ///////////////////
void calculateZminC()
{
float temp;
for (int i = 0; i < n1 + m1 - 1; i++)
{
temp = 0;
for (int j = 0; j < m1 - 1; j++)
{
temp += (a[j][i] * cb[j]);
}
zMc[i] = temp - c[i];
}
}

// ///////// Calculate Pivot /////////////////

void calculatePivot()
{
int i = 1;
int keyCol = 0, keyRow = 0;

// Calculate key column
float keyColValue = zMc[0];
while (i < n1)
{
if (zMc[i] < keyColValue && zMc[i] < 0)
{
keyColValue = zMc[i];
keyCol = i;
}
i++;
}// Calculate key column end

i = 1; // Reset i
// Calculate key row
float keyRowValue = (b2[0] / positive(a[0][keyCol]));
while (i < m1 - 1)
{
float temp = (b2[i] / positive(a[i][keyCol]));
if (temp < keyRowValue)
{
keyRowValue = temp;
keyRow = i;
}
i++;
}// Calculate key row end

float pivot = a[keyRow][keyCol];
System.out.println(keyColValue + " keyCol= " + keyCol + " keyRow = " + keyRow
+ " " + keyRowValue + " pivot" + pivot);
tableCells(keyRow, keyCol, pivot);
}

// ///////// Calculate Table Cells /////////////////

void tableCells(int keyRow, int keyCol, float pivot)
{

float[] keyRowValues = new float[n1 + m1];
float[] keyColValues = new float[m1 - 1];
// saving the key row & key column values
for (int i = 0; i < n1 + m1 - 1; i++)
{
keyRowValues[i] = a[keyRow][i];
}
keyRowValues[n1 + m1 - 1] = b2[keyRow];

for (int i = 0; i < m1 - 1; i++)
{
keyColValues[i] = a[i][keyCol];
}

for (int i = 0; i < m1 - 1; i++)
{
for (int j = 0; j < n1 + m1 - 1; j++)
{
if (i == keyRow)
{
a[i][j] /= pivot;
}
else
{
System.out.println("a[" + i + "][" + j + "] = " + a[i][j] + "-"
+ keyRowValues[j] + "*" + keyColValues[i] + " /" + pivot);
a[i][j] = a[i][j] - (keyRowValues[j] * keyColValues[i]) / pivot;
}
System.out.println("a[" + i + "][" + j + "] = " + a[i][j]);
}
if (i == keyRow)
{
b2[i] /= pivot;
}
else
{
b2[i] = b2[i] - (keyRowValues[n1 + m1 - 1] * keyColValues[i]) / pivot;
}
System.out.println("b[" + i + "] = " + b2[i]);
}
cb[keyRow] = c[keyCol];
// show the table again
insertT();
// loop();
}

float positive(float test)
{
if (test < 0)
{
return (-1 * test);
}
else
{
return test;
}
}

// //////// Result /////////////

void result()
{
float z = 0;
for (int i = 0; i < n1; i++)
{
for (int j = 0; j < m1 - 1; j++)
{
if (c[i] == cb[j])
{
z += cb[j] * b2[j];
}
}
}
System.out.println("z = " + z);
}

public static void main(String[] args)
{
int n = Integer.parseInt(JOptionPane
.showInputDialog("Please enter the number of your variables"));
int m = Integer.parseInt(JOptionPane
.showInputDialog("Please enter the number of your constraints"));

Equations slack = new Equations(n, m + 1);
slack.setDefaultCloseOperation(EXIT_ON_CLOSE); // added
slack.setSize(300, 200);
slack.setVisible(true);

}
}


Sorry for changing the opening bracket placement (I don't want to start any formatting wars), but that's what Eclipse does when I run the code cleanup tool, as that's my default formatting.

Why is this important? When you follow the rules and good code conventions, you'll get more and better responses from the forum. Not many people here have the time to wade through a ton of poorly formatted code trying to see what is going on. The easier you make it for others,. the more chance there is that someone can help you.

This shouldn't be a major effort on your part, as any good IDE (Eclipse, NetBeans, etc.) makes most of this easy for you.

Hope the better formatted code will help you or someone here to see what's going on.

[Norm]

Does your code test float values to be equals with ==? This doesn't always work the way you might expect. How close in value do two values need to be to be considered equal? Sometimes its better to see if the difference between two values is less than some very small value vs using ==.

[asoo]

Hi,
Thank you all, I just found the problem it was because I used float type so after I replace them by double it's working all right.

Also spacial thanks for you ajhampson your instructions really help me to organize my code.