Scribd
Upload
23 views10 pages

Tableau Method for Linear Programming

The document outlines the iterations of the Simplex method for solving linear programming problems, detailing the initial tableau, pivot operations, and the changes in variables across iterations. It includes multiple phases, including a two-phase method to handle artificial variables and optimize the objective function. The process continues until an optimal solution is found with no negative coefficients in the z-row.

Uploaded by

sumitvidhani2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as XLSX, PDF, TXT or read online on Scribd
23 views10 pages

Tableau Method for Linear Programming

The document outlines the iterations of the Simplex method for solving linear programming problems, detailing the initial tableau, pivot operations, and the changes in variables across iterations. It includes multiple phases, including a two-phase method to handle artificial variables and optimize the objective function. The process continues until an optimal solution is found with no negative coefficients in the z-row.

Uploaded by

sumitvidhani2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as XLSX, PDF, TXT or read online on Scribd

Initial Tableau

z x1 x2 s1 s2 s3 s4 soln
X0 1 -3 -2 0 0 0 0 0
s1 0 1 2 1 0 0 0 6
s2 0 2 1 0 1 0 0 8
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2

Leaving Var; most negative co-eff.;x1, Entering Var; Min ratio s2


Create new pivot row R2(1) as R2(0)/pivot element. Add multiples of R2(1) to each Ri(0) to generate next iteration

Iteration 1
z x1 x2 s1 s2 s3 s4 soln
z 1 0 -0.5 0 1.5 0 0 12
s1 0 0 1.5 1 -0.5 0 0 2
x1 0 1 0.5 0 0.5 0 0 4
s3 0 0 1.5 0 0.5 1 0 5
s4 0 0 1 0 0 0 1 2

Leaving Var; most negative co-eff.;x2, Entering Var; Min ratio s1

Iteration 2
z x1 x2 s1 s2 s3 s4 soln
z 1 0 0 0.333333 1.333333 0 0 12.66667
x2 0 0 1 0.666667 -0.333333 0 0 1.333333
x1 0 1 0 -0.333333 0.666667 0 0 3.333333
s3 0 0 0 -1 1 1 0 3
s4 0 0 0 -0.666667 0.333333 0 1 0.666667
Row ratio workings
R0
R1 6
R2 4 min ratio
R3
R4

ate next iteration

Row ratio workings


R0
R1 1.333333 min ratio
R2 8
R3 3.333333
R4 2

Row
R0 No negative z-row coefficients: STOP
R1
R2
R3
R4
Initial Tableau
X0 X1 X2 S1 S2 soln Row ratio workings
X0 1 -40 -50 0 0 0 R0
S1 0 1 2 1 0 40 R1
S2 0 4 3 0 1 120 R2

Leaving Var; most negative co-eff.;X2, Entering Var; Min ratio S1


Create new pivot row. Add multiples of new pivot row to each Ri(0) to generate next iteration

Iteration 1
X0 X1 X2 S1 S2 soln Row ratio workings
X0 1 -15 0 25 0 1000 R0
X2 0 0.5 1 0.5 0 20 R1
S2 0 2.5 0 -1.5 1 60 R2

Iteration 1
X0 X1 X2 S1 S2 soln Row
X0 1 0 0 16 6 1360 R0
X2 0 0 1 0.8 -0.2 8 R1
X1 0 1 0 -0.6 0.4 24 R2
ratio workings

20 min ratio
40

ratio workings

40
24 min ratio

No negative z-row coeff;STOP


Initial Tableau
X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 4 1 0 0M M M 0
R1 0 3 1 0 0 1 0 0 3
R2 0 4 3 -1 0 0 1 0 6
R3 0 1 2 0 -1 0 0 1 4

Iteration 0 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 4-8M 1-6M M M 0 0 0 "-13M"
R1 0 3 1 0 0 1 0 0 3
R2 0 4 3 -1 0 0 1 0 6
R3 0 1 2 0 -1 0 0 1 4

Leaving Var; most negative (remember we're minimising but we've set up the tableau with a negative coefficient for z!) co-eff.;X
Entering Var; Min ratio R1, Create new pivot row. Add multiples of new pivot row to each Ri(0) to generate next iteration, try M =

Iteration 1 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 -796 -599 100 100 0 0 0 -1300
R1 0 3 1 0 0 1 0 0 3
R2 0 4 3 -1 0 0 1 0 6
R3 0 1 2 0 -1 0 0 1 4

Iteration 2 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 -333.6667 100 100 ### 0 0 -504
X1 0 1 0.333333 0 0 0.333333 0 0 1
R2 0 0 1.666667 -1 0 -1.333333 1 0 2
R3 0 0 1.666667 0 -1 -0.333333 0 1 3

Iteration 3 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 0 -100.2 100 ### 200.2 0 -103.6
X1 0 1 0 0.2 0 0.6 -0.2 0 0.6
X2 0 0 1 -0.6 0 -0.8 0.6 0 1.2
R3 0 0 0 1 -1 1 -1 1 1

Iteration 4 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 00 ### ###
X1 0 1 0 0 0.2 0.4
X2 0 0 1 0 -0.6 1.8
S1 0 0 0 1 -1 1

Iteration 5 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 1 0 0.00 0 0 0 0 -3
S2 0 5 0 0 1 0 0 0 2
X2 0 3 1 0 0 0 0 0 3
S1 0 5 0 1 0 0 0 0 3
Row
0
1
2
3

ratio workings

1 min ratio
1.5
4

e coefficient for z!) co-eff.;X 1,


nerate next iteration, try M = 100

ratio workings

3
1.2 min ratio
1.8

ratio

3
-2
1

ratio

2
-3
-1

Stop, optimal solution


Initial Tableau for Phase 1 of 2-Phase method
Basic X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 0 00 1 1 1 0
R1 0 3 1 0 0 1 0 0 3
R2 0 4 3 -1 0 0 1 0 6
R3 0 1 2 0 -1 0 0 1 4

iteration 0
Basic X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 -8 -6 11 0 0 0 -13
R1 0 3 1 0 0 1 0 0 3
R2 0 4 3 -1 0 0 1 0 6
R3 0 1 2 0 -1 0 0 1 4

Iteration 1
Basic X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 -3.333333 1 1 2.666667 0 0 -5
X1 0 1 0.333333 0 0 0.333333 0 0 1
R2 0 0 1.666667 -1 0 -1.333333 1 0 2
R3 0 0 1.666667 0 -1 -0.333333 0 1 3

Iteration 2
Basic X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 0 -1 1 0 2 0 -1
X1 0 1 0 0.2 0 0.6 -0.2 0 0.6
X2 0 0 1 -0.6 0 -0.8 0.6 0 1.2
R3 0 0 0 1 -1 1 -1 1 1

Iteration 3
4 X0 X1 X2 S1 S2 R1 R2 R3 soln
X0 -1 0 0 0 0 1 1 1 0
X1 0 1 0 0 0.2 0.4 0 -0.2 0.4
X2 0 0 1 0 -0.6 -0.2 0 0.6 1.8
S1 0 0 0 1 -1 1 -1 1 1

at It3, phase 1 optimal solution has the amended objective minimised to 0, x1 = .4, x2 = 1.8 and s1 = 1

Phase 2 drop artificial variables, return to original obj fn, sub out basic var with nnonzero coeff
Basic X0 X1 X2 S1 S2 soln
X0 -1 4 1 0 0 0
X1 0 1 0 0 0.2 0.4
X2 0 0 1 0 -0.6 1.8
S1 0 0 0 1 -1 1

Initial tableau of Phase 2


Basic X0 X1 X2 S1 S2 soln ratio
X0 -1 0 0 0 -0.2 -3.4
X1 0 1 0 0 0.2 0.4 2
X2 0 0 1 0 -0.6 1.8 -3
S1 0 0 0 1 -1 1 -1

Basic X0 X1 X2 S1 S2 soln ratio


X0 -1 1 0 0 0 -3
S2 0 5 0 0 1 2
X2 0 3 1 0 0 3
S1 0 5 0 1 0 3
ratio

1
1.5
4

ratio

3
1.2
1.8

ratio

3
-2
1

You might also like