Simplex Method
Authors: Housam Binous and Ahmed Bellagi
Simplex Method
Authors: Housam Binous and Ahmed Bellagi
Authors: Housam Binous and Ahmed Bellagi
We present the solution of an optimization problem that was used to illustrate the Simplex method in Pratical Optimization Methods with Mathematica Applications, M . Asghar Bhatti, Springer - Verlag 2000. The steps in order to apply the Simplex method using Mathematica are shown in details and the solution is compared to the ones obtained using two Mathematica' s built - in functions Minimize and LinearProgramming.
The linear programming problem is:This problem is used to illustrate the simplex method in Practical Optimization Methods with Mathematica Applications, M. Asghar Bhatti, Springer-Verlag 2000.Introducing slack variables (called x5, x6 and x7), we obtain:
Building the first Simplex tableau
In[]:=
title={Basis,x1,x2,x3,x4,x5,x6,x7,RightHandSide};
In[]:=
eq={{x5,1/4,-8,-1,9,1,0,0,1},{x6,1/2,-12,-1/2,3,0,1,0,3},{x7,0,0,1,1,0,0,1,1}};
In[]:=
object={obj,-3/4,20,-1/2,6,0,0,0,f};
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Out[]//MatrixForm=
Basis | x1 | x2 | x3 | x4 | x5 | x6 | x7 | RightHandSide |
x5 | 1 4 | -8 | -1 | 9 | 1 | 0 | 0 | 1 |
x6 | 1 2 | -12 | - 1 2 | 3 | 0 | 1 | 0 | 3 |
x7 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
obj | - 3 4 | 20 | - 1 2 | 6 | 0 | 0 | 0 | f |
Adding x1 to the basic set and taking x5 out of the basic set
In[]:=
Print[1 4/1," ",3 2/1," ",1 1/0]
1
0
4 6 ComplexInfinity
In[]:=
B0={{1/4,0,0},{1/2,1,0},{0,0,1}};
In[]:=
N0={{-8,-1,9,1},{-12,-1/2,3,0},{0,1,1,0}};
In[]:=
cB0={-3/4,0,0};
In[]:=
cN0={20,-1/2,6,0};
In[]:=
b0={1,3,1};
In[]:=
w0=cB0.Inverse[B0];
In[]:=
w0.b0;
In[]:=
r0=cN0-w0.N0;
In[]:=
title={Basis,x1,x6,x7,x2,x3,x4,x5,RightHandSide};
In[]:=
eq=Transpose[Join[Join[{{x1,x6,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B0].N0],{Inverse[B0].b0}]]];
In[]:=
object=Join[{obj,0,0,0},r0,{f-w0.b0}];
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Out[]//MatrixForm=
Basis | x1 | x6 | x7 | x2 | x3 | x4 | x5 | RightHandSide |
x1 | 1 | 0 | 0 | -32 | -4 | 36 | 4 | 4 |
x6 | 0 | 1 | 0 | 4 | 3 2 | -15 | -2 | 1 |
x7 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
obj | 0 | 0 | 0 | -4 | - 7 2 | 33 | 3 | 3+f |
Adding x2 to the basic set and taking x6 out of the basic set
In[]:=
Print[-4/32," ",1/4," ",1/0]
1
0
- ComplexInfinity
1
8
1
4
In[]:=
B1={{1,-32,0},{0,4,0},{0,0,1}};
In[]:=
N1={{-4,36,4,0},{3/2,-15,-2,1},{1,1,0,0}};
In[]:=
cB1={0,-4,0};
In[]:=
cN1={-7/2,33,3,0};
In[]:=
b1={4,1,1};
In[]:=
w1=cB1.Inverse[B1];
In[]:=
w1.b1;
In[]:=
r1=cN1-w1.N1;
In[]:=
title={Basis,x1,x2,x7,x3,x4,x5,x6,RightHandSide};
In[]:=
eq=Transpose[Join[Join[{{x1,x2,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B1].N1],{Inverse[B1].b1}]]];
In[]:=
object=Join[{obj,0,0,0},r1,{f-w1.b1-w0.b0}];
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Out[]//MatrixForm=
Basis | x1 | x2 | x7 | x3 | x4 | x5 | x6 | RightHandSide |
x1 | 1 | 0 | 0 | 8 | -84 | -12 | 8 | 12 |
x2 | 0 | 1 | 0 | 3 8 | - 15 4 | - 1 2 | 1 4 | 1 4 |
x7 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
obj | 0 | 0 | 0 | -2 | 18 | 1 | 1 | 4+f |
Adding x3 to the basic set and taking x2 out of the basic set
In[]:=
Print[12/8," ",1/4 8/3," ",1/1]
3
2
2
3
In[]:=
B2={{1,8,0},{0,3/8,0},{0,1,1}};
In[]:=
N2={{0,-84,-12,8},{1,-15/4,-1/2,1/4},{0,1,0,0}};
In[]:=
cB2={0,-2,0};
In[]:=
cN2={0,18,1,1};
In[]:=
b2={12,1/4,1};
In[]:=
w2=cB2.Inverse[B2];
In[]:=
w2.b2;
In[]:=
r2=cN2-w2.N2;
In[]:=
title={Basis,x1,x3,x7,x2,x4,x5,x6,RightHandSide};
In[]:=
eq=Transpose[Join[Join[{{x1,x3,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B2].N2],{Inverse[B2].b2}]]];
In[]:=
object=Join[{obj,0,0,0},r2,{f-w2.b2-w1.b1-w0.b0}];
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Out[]//MatrixForm=
Basis | x1 | x3 | x7 | x2 | x4 | x5 | x6 | RightHandSide |
x1 | 1 | 0 | 0 | - 64 3 | -4 | - 4 3 | 8 3 | 20 3 |
x3 | 0 | 1 | 0 | 8 3 | -10 | - 4 3 | 2 3 | 2 3 |
x7 | 0 | 0 | 1 | - 8 3 | 11 | 4 3 | - 2 3 | 1 3 |
obj | 0 | 0 | 0 | 16 3 | -2 | - 5 3 | 7 3 | 16 3 |
Adding x4 to the basic set and taking x7 out of the basic set
In[]:=
Print[-20/3 1/4," ",-2/3 1/10," ",1/3 1/11]
- -
5
3
1
15
1
33
In[]:=
B3={{1,0,-4},{0,1,-10},{0,0,11}};
In[]:=
N3={{-64/3,-4/3,8/3,0},{8/3,-4/3,2/3,0},{-8/3,4/3,-2/3,1}};
In[]:=
cB3={0,0,-2};
In[]:=
cN3={16/3,-5/3,7/3,0};
In[]:=
b3={20/3,2/3,1/3};
In[]:=
w3=cB3.Inverse[B3];
In[]:=
w3.b3;
In[]:=
r3=cN3-w3.N3;
In[]:=
title={Basis,x1,x3,x4,x2,x5,x6,x7,RightHandSide};
In[]:=
eq=Transpose[Join[Join[{{x1,x3,x4}},IdentityMatrix[3]],Join[Transpose[Inverse[B3].N3],{Inverse[B3].b3}]]];
In[]:=
object=Join[{obj,0,0,0},r3,{f-w3.b3-w2.b2-w1.b1-w0.b0}];
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Adding x5 to the basic set and taking x4 out of the basic set
In[]:=
Print[-224/33 33/28," ",-32/33 33/4," ",1/33 33/4]
In[]:=
B4={{1,0,-28/33},{0,1,-4/33},{0,0,4/33}};
In[]:=
N4={{-736/33,0,80/33,4/11},{8/33,0,2/33,10/11},{-8/33,1,-2/33,1/11}};
In[]:=
cB4={0,0,-47/33};
In[]:=
cN4={160/33,0,73/33,2/11};
In[]:=
b4={224/33,32/33,1/33};
In[]:=
w4=cB4.Inverse[B4];
In[]:=
w4.b4;
In[]:=
r4=cN4-w4.N4;
In[]:=
title={Basis,x1,x3,x5,x2,x4,x6,x7,RightHandSide};
In[]:=
eq=Transpose[Join[Join[{{x1,x3,x5}},IdentityMatrix[3]],Join[Transpose[Inverse[B4].N4],{Inverse[B4].b4}]]];
In[]:=
object=Join[{obj,0,0,0},r4,{f-w4.b4-w3.b3-w2.b2-w1.b1-w0.b0}];
In[]:=
TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};
In[]:=
SimplexMatrix=TableSimplex//MatrixForm
Conclusion: Minimum is -23/4 and it is obtained for x1=7, x2=0, x3=1 and x4=0. Slack variables are equal to x5=1/4, x6=0 and x7=0. Inequalities 2 and 3 are active.
Checking our result with Mathematica's built-in functions Minimize and LinearProgramming. We get the same results.
In[]:=
Minimize[{-3/4 x1+20 x2-1/2 x3+6 x4,1/4 x1-8x2-x3+9 x4≤1,1/2 x1-12 x2-1/2 x3+3 x4≤3,x3+x4≤1,x1≥0,x2≥0,x3≥0,x4≥0},{x1,x2,x3,x4}]
In[]:=
LinearProgramming[{-3/4,20,-1/2,6},{{1/4,-8,-1,9},{1/2,-12,-1/2,3},{0,0,1,1},{-1,0,0,0},{0,-1,0,0},{0,0,-1,0},{0,0,0,-1}},{{1,-1},{3,-1},{1,-1},{0,-1},{0,-1},{0,-1},{0,-1}}]