i'm using simplex method to
compute the maximum of the objective function in standard form
given equations
i build a table adding slack variables.
In the table the last row is objective function
and the first column is slack variables initially.
Below is the algo, can someone tell me if i'm doing anything wrong,
I want to know how to get the values of the final solution vector from
this tableau, in the example it is obvious but in some cases it isn't
1) Get the min of all the negative variables in last row. It is the
pivot column ie col
2) In all the rows of col except the last compute the min ratio test
of the RHS of the equations / each col.
I ignore the rows of the col which have zero or negative entry
The row which gives the minim is row
If you don't have any row whose entries are positive break
3) Normalize row using col variable and eliminate all the entries in
other rows including the last (objective function)
4) We have row,col , Swap the element in (row 0) of col with element
in col 0 of row . We are exchanging slack variables with equation
variables x and y.
5) go to 1
Ex
Max 3x+4y
1x +2y <=4
2x + 1y <=5
s1,s2 are slack variables
=====================================
x y s1 s2 RHS
=====================================
Choosing 1,2
s1 1.00 2.00 1.00 0.00 4.00
s2 2.00 1.00 0.00 1.00 5.00
-3.00 -4.00 0.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,2.00
x 0.50 1.00 0.50 0.00 2.00
s2 2.00 1.00 0.00 1.00 5.00
-3.00 -4.00 0.00 0.00 0.00
@@@@@@@@@@@@@@@*********
x 0.50 1.00 0.50 0.00 2.00
s2 1.50 0.00 -0.50 1.00 3.00
-1.00 0.00 2.00 0.00 8.00
@@@@@@@@@@@@@@@*********
return pivot 0
return row 1
Choosing 2,1
y 0.50 1.00 0.50 0.00 2.00
x 1.50 0.00 -0.50 1.00 3.00
-1.00 0.00 2.00 0.00 8.00
@@@@@@@@@@@@@@@*********
Normailzing,1.50
0.50 1.00 0.50 0.00 2.00
1.00 0.00 -0.33 0.67 2.00
-1.00 0.00 2.00 0.00 8.00
@@@@@@@@@@@@@@@*********
y 0.00 1.00 0.67 -0.33 1.00
x 1.00 0.00 -0.33 0.67 2.00
0.00 0.00 1.67 0.67 10.00
In the above case i was able to read y=1,x=2 but in an equation like
Last row is the x,y,z and s1,s2,s3 ie 0,1,2,3,4,5
and last col is slack variabls 3,4,5
Here i'm not able to determine the solution vector
Max 4x +2y +1z
1x + 0y + 0z <=5
4x+ 1y +0z <= 25
8x+ 4y+ 1z <= 125
I get tables like this
return pivot 0
return row 0
Choosing 0,0
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 4.00
8.00 4.00 1.00 0.00 0.00 1.00 125.00 5.00
-4.00 -2.00 -1.00 0.00 0.00 0.00 0.00 0.00
0.00 1.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 4.00
8.00 4.00 1.00 0.00 0.00 1.00 125.00 5.00
-4.00 -2.00 -1.00 0.00 0.00 0.00 0.00 0.00
3.00 1.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 5.00
0.00 -2.00 -1.00 4.00 0.00 0.00 20.00 0.00
3.00 1.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 1
return row 1
Choosing 1,1
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 5.00
0.00 -2.00 -1.00 4.00 0.00 0.00 20.00 0.00
3.00 1.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 5.00
0.00 -2.00 -1.00 4.00 0.00 0.00 20.00 0.00
3.00 4.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 5.00
0.00 0.00 -1.00 -4.00 2.00 0.00 30.00 0.00
3.00 4.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 3
return row 0
Choosing 0,3
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 5.00
0.00 0.00 -1.00 -4.00 2.00 0.00 30.00 0.00
3.00 4.00 2.00 3.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 5.00
0.00 0.00 -1.00 -4.00 2.00 0.00 30.00 0.00
3.00 4.00 2.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 5.00
4.00 0.00 -1.00 0.00 2.00 0.00 50.00 0.00
3.00 4.00 2.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 2
return row 2
Choosing 2,2
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 5.00
4.00 0.00 -1.00 0.00 2.00 0.00 50.00 0.00
3.00 4.00 2.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 2.00
4.00 0.00 -1.00 0.00 2.00 0.00 50.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 2.00
-4.00 0.00 0.00 0.00 -2.00 1.00 75.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 0
return row 0
Choosing 0,0
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 2.00
-4.00 0.00 0.00 0.00 -2.00 1.00 75.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 1.00
-8.00 0.00 1.00 0.00 -4.00 1.00 25.00 2.00
-4.00 0.00 0.00 0.00 -2.00 1.00 75.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 2.00
0.00 0.00 0.00 4.00 -2.00 1.00 95.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 4
return row 1
Choosing 1,4
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 1.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 2.00
0.00 0.00 0.00 4.00 -2.00 1.00 95.00 0.00
3.00 4.00 5.00 0.00 4.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 0.00 1.00 8.00 -4.00 1.00 65.00 2.00
0.00 0.00 0.00 4.00 -2.00 1.00 95.00 0.00
3.00 4.00 5.00 0.00 1.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 2.00
0.00 2.00 0.00 -4.00 0.00 1.00 105.00 0.00
3.00 4.00 5.00 0.00 1.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot 3
return row 0
Choosing 0,3
1.00 0.00 0.00 1.00 0.00 0.00 5.00 3.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 2.00
0.00 2.00 0.00 -4.00 0.00 1.00 105.00 0.00
3.00 4.00 5.00 0.00 1.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
Normailzing,1.00
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
0.00 1.00 0.00 -4.00 1.00 0.00 5.00 4.00
0.00 4.00 1.00 -8.00 0.00 1.00 85.00 2.00
0.00 2.00 0.00 -4.00 0.00 1.00 105.00 0.00
3.00 4.00 5.00 3.00 1.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 4.00
8.00 4.00 1.00 0.00 0.00 1.00 125.00 2.00
4.00 2.00 0.00 0.00 0.00 1.00 125.00 0.00
3.00 4.00 5.00 3.00 1.00 5.00 0.00 0.00
@@@@@@@@@@@@@@@*********
return pivot -1
1.00 0.00 0.00 1.00 0.00 0.00 5.00 0.00
4.00 1.00 0.00 0.00 1.00 0.00 25.00 4.00
8.00 4.00 1.00 0.00 0.00 1.00 125.00 2.00
4.00 2.00 0.00 0.00 0.00 1.00 125.00 0.00
3.00 4.00 5.00 3.00 1.00 5.00 0.00 0.00
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
