Simplex Method
Author's Data: Housam BINOUS
Department of Chemical Engineering
National Institute of Applied Sciences and Technology
Tunis, TUNISIA
Email: binoushousam@yahoo.com

The linear programming problem is:



This problem is used to illustrate the simplex method in Pratical 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

title={Basis,x1,x2,x3,x4,x5,x6,x7,RightHandSide};

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

object={obj,-3/4,20,-1/2,6,0,0,0,f};

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

SimplexMatrix=TableSimplex//MatrixForm

Adding x1 to the basic set and taking x5 out of the basic set

Print[1 4/1,"  ",3 2/1,"  ",1 1/0]

B0={{1/4,0,0},{1/2,1,0},{0,0,1}};

N0={{-8,-1,9,1},{-12,-1/2,3,0},{0,1,1,0}};

cB0={-3/4,0,0};

cN0={20,-1/2,6,0};

b0={1,3,1};

w0=cB0.Inverse[B0];

w0.b0;

r0=cN0-w0.N0;

title={Basis,x1,x6,x7,x2,x3,x4,x5,RightHandSide};

eq=Transpose[Join[Join[{{x1,x6,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B0].N0],{Inverse[B0].b0}]]];

object=Join[{obj,0,0,0},r0,{f-w0.b0}];

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

SimplexMatrix=TableSimplex//MatrixForm

Adding x2 to the basic set and taking x6 out of the basic set

Print[-4/32,"  ",1/4,"  ",1/0]

B1={{1,-32,0},{0,4,0},{0,0,1}};

N1={{-4,36,4,0},{3/2,-15,-2,1},{1,1,0,0}};

cB1={0,-4,0};

cN1={-7/2,33,3,0};

b1={4,1,1};

w1=cB1.Inverse[B1];

w1.b1;

r1=cN1-w1.N1;

title={Basis,x1,x2,x7,x3,x4,x5,x6,RightHandSide};

eq=Transpose[Join[Join[{{x1,x2,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B1].N1],{Inverse[B1].b1}]]];

object=Join[{obj,0,0,0},r1,{f-w1.b1-w0.b0}];

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

SimplexMatrix=TableSimplex//MatrixForm

Adding x3 to the basic set and taking x2 out of the basic set

Print[12/8,"  ",1/4 8/3," ",1/1]

B2={{1,8,0},{0,3/8,0},{0,1,1}};

N2={{0,-84,-12,8},{1,-15/4,-1/2,1/4},{0,1,0,0}};

cB2={0,-2,0};

cN2={0,18,1,1};

b2={12,1/4,1};

w2=cB2.Inverse[B2];

w2.b2;

r2=cN2-w2.N2;

title={Basis,x1,x3,x7,x2,x4,x5,x6,RightHandSide};

eq=Transpose[Join[Join[{{x1,x3,x7}},IdentityMatrix[3]],Join[Transpose[Inverse[B2].N2],{Inverse[B2].b2}]]];

object=Join[{obj,0,0,0},r2,{f-w2.b2-w1.b1-w0.b0}];

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

SimplexMatrix=TableSimplex//MatrixForm

Adding x4 to the basic set and taking x7 out of the basic set

Print[-20/3 1/4,"  ",-2/3 1/10,"  ",1/3 1/11]

B3={{1,0,-4},{0,1,-10},{0,0,11}};

N3={{-64/3,-4/3,8/3,0},{8/3,-4/3,2/3,0},{-8/3,4/3,-2/3,1}};

cB3={0,0,-2};

cN3={16/3,-5/3,7/3,0};

b3={20/3,2/3,1/3};

w3=cB3.Inverse[B3];

w3.b3;

r3=cN3-w3.N3;

title={Basis,x1,x3,x4,x2,x5,x6,x7,RightHandSide};

eq=Transpose[Join[Join[{{x1,x3,x4}},IdentityMatrix[3]],Join[Transpose[Inverse[B3].N3],{Inverse[B3].b3}]]];

object=Join[{obj,0,0,0},r3,{f-w3.b3-w2.b2-w1.b1-w0.b0}];

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

SimplexMatrix=TableSimplex//MatrixForm

Adding x5 to the basic set and taking x4 out of the basic set

Print[-224/33 33/28,"  ",-32/33 33/4,"  ",1/33 33/4]

B4={{1,0,-28/33},{0,1,-4/33},{0,0,4/33}};

N4={{-736/33,0,80/33,4/11},{8/33,0,2/33,10/11},{-8/33,1,-2/33,1/11}};

cB4={0,0,-47/33};

cN4={160/33,0,73/33,2/11};

b4={224/33,32/33,1/33};

w4=cB4.Inverse[B4];

w4.b4;

r4=cN4-w4.N4;

title={Basis,x1,x3,x5,x2,x4,x6,x7,RightHandSide};

eq=Transpose[Join[Join[{{x1,x3,x5}},IdentityMatrix[3]],Join[Transpose[Inverse[B4].N4],{Inverse[B4].b4}]]];

object=Join[{obj,0,0,0},r4,{f-w4.b4-w3.b3-w2.b2-w1.b1-w0.b0}];

TableSimplex={title,eq[[1]],eq[[2]],eq[[3]],object};

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.

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}]

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}}]