Unit 2- Simplex Method

Example 1 –
Use the simplex method to solve the following LP
problem.

Maximize 𝑍 = 7𝑥1 + 6𝑥2

subject to the constraints
1.𝑥1 + 𝑥2 ≤ 4
2. 2𝑥1 + 𝑥2 ≤ 6
and 𝑥1 , 𝑥2 , ≥ 0
Introducing non-negative slack variables s1, s2 and s3 to
convert the given LP problem
into its standard form
Set up initial tableau

Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4 4/1=4

S2 0 2 1 0 1 6 6/2=3→
Z=0 Zj 0 0 0 0
Cj-Zj 7↑ 6 0 0
Set up initial tableau

Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4 4/1=4

S2 0 2 1 0 1 6 6/2=3→
Z=0 Zj 0 0 0 0
Cj-Zj 7↑ 6 0 0
Set up initial tableau

Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4 4/1=4

S2 0 2 1 0 1 6 6/2=3→
Z=0 Zj 0 0 0 0
Cj-Zj 7↑ 6 0 0
Set up initial tableau

Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4 4/1=4

S2 0 2 1 0 1 6 6/2=3→
Z=0 Zj 0 0 0 0
Cj-Zj 7↑ 6 0 0
Since all bi (RHS values) > 0, (i = 1, 2, 3), therefore choose the
initial basic feasible solution as
Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4 4/1=4

S2 0 2 1 0 1 6 6/2=3→
Z=0 Zj 0 0 0 0
Cj-Zj 7↑ 6 0 0

Positive maximum Cj-Zj is 7 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 3 and its row index is 2. So, the leaving basis variable is S2.

The pivot element is 2.

Entering =x1, Departing =S2, Key Element =2

New values of row 2
Iteration-1 Cj 7 6 0 0

MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1 1 1 0 4
X1 7 2/2 1/2 0/2 1/2 6/2
Z=0 Zj 0 0 0 0
Cj-Zj 7 6 0 0

Iteration-1 Cj 7 6 0 0

B CB x1 x2 S1 S2 XB

S1 0 1 1 1 0 4
X1 7 1.0 0.5 0.0 0.5 3.0
Z=0 Zj 0 0 0 0
Cj-Zj 7 6 0 0
New values of row 1
Iteration-1 Cj 7 6 0 0
MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 1-1 1-0.5 1-0 0-0.5 4-3
X1 7 1.0 0.5 0.0 0.5 3.0
Z=0 Zj 0 0 0 0
Cj-Zj 7 6 0 0

Iteration-1 Cj 7 6 0 0
MinRatio
B CB x1 x2 S1 S2 XB
xB/X1
S1 0 0 0.5 1 -0.5 1.0
X1 7 1.0 0.5 0.0 0.5 3.0
Z=0 Zj 0 0 0 0
Cj-Zj 7 6 0 0
Since all bi (RHS values) > 0, (i = 1, 2, 3), therefore
choose the initial basic feasible solution as
Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
S1 0 0 0.5 1 -0.5 1 1/0.5=2→
x1 7 1 0.5 0 0.5 3 3/0.5=6
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 -3.5

Positive maximum Cj-Zj is 2.5 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 2 and its row index is 1. So, the leaving basis variable is S1.

The pivot element is 0.5.

Entering =x2, Departing =S1, Key Element =0.5

New values of row 1
Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
x2 6 0/0.5 0.5/0.5 1/0.5 -0.5/0.5 1/0.5 1/0.5=2→
x1 7 1 0.5 0 0.5 3 3/0.5=6
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 -3.5

Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB
B CB

x2 6 0 1 2 -1 2
x1 7 1 0.5 0 0.5 3
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 -3.5
 Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
New values of row 2 x2 6 0*0.5=0 1*0.5=0.5 2*0.5=1 -1*0.5=(-0.5) 2*0.5=1
x1 7 1 0.5 0 0.5 3
New Row 2 = Old Row 2 Z=21 Zj 7 3.5 0 3.5
– (0.5*New row 1) Cj-Zj 0 2.5↑ 0 -3.5

Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
x2 6 0 0.5 1 (-0.5) 1
x1 7 1 0.5 0 0.5 3
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 (-3.5)

Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
x2 6 0 0.5 1 (-0.5) 1
x1 7 1-0=1 0.5-0.5=0 0-1=(-1) 0.5-(-0.5)=1 3-1=2
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 (-3.5)

Iteration-2 Cj 7 6 0 0
x1 x2 S1 S2 XB MinRatio
B CB
XB/x2
x2 6 0 0.5 1 -0.5 1
x1 7 1 0 (-1) 1 2
Z=21 Zj 7 3.5 0 3.5
Cj-Zj 0 2.5↑ 0 (-3.5)
Optimal Solution
Cj 7 6 0 0

B CB x1 x2 S1 S2 XB MinRatio

x2 6 0 1 2 (-1) 2

x1 7 1 0 (-1) 1 2

Z=26 Zj 7 6 5 1

Cj-Zj 0 0 (-5) (-1)

Since all Cj-Zj≤0

Hence, optimal solution is arrived with value of variables as :

x1=2,x2=2

Max Z=26
Example 2 –
Use the simplex method to solve the following LP problem.
MAX Z = 4x1 + 4x2
subject to
x1+x2<=10
6x1 + 6x2 <= 36
x1 <= 6
and x1,x2 >= 0
Standard Form
Initial Tableau
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 1 2 1 0 0 10 10/1=10

S2 0 6 6 0 1 0 36 36/6=6→

S3 0 1 0 0 0 1 6 6/1=6

Z=0 Zj 0 0 0 0 0

Cj-Zj 4↑ 4 0 0 0
New values of Row 2
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 1 2 1 0 0 10

x1 4 6/6 6/6 0/6 1/6 0/6 36/6

S3 0 1 0 0 0 1 6
Z=0 Zj
Cj-Zj
New values of Row 2
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 1 2 1 0 0 10

x1 4 1 1 0 0.17 0 6

S3 0 1 0 0 0 1 6
Z=24 Zj 4 4 0 0.68 0
Cj-Zj 0 0 0 (-0.68) 0
New values of Row 1 = Old R1 – New Row 2
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 1-1=0 2-1=1 1-0=1 0-0.17=(-0.17) 0-0=0 10-6=4

x1 4 1 1 0 0.17 0 6

S3 0 1 0 0 0 1 6
Z=24 Zj 4 4 0 0.68 0
Cj-Zj 0 0 0 (-0.68) 0
New values of Row 3 = Old R3 – New Row 2
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 0 1 1 -0.17 0 4

x1 4 1 1 0 0.17 0 6

S3 0 1-1=0 0-1=-1 0-0=0 0-0.17=-0.17 1-0=1 6-6=0

Z=24 Zj 4 4 0 0.68 0
Cj-Zj 0 0 0 (-0.68) 0
New values of Row 3 = Old R3 – New Row 2
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1

S1 0 0 1 1 (-0.17) 0 4

x1 4 1 1 0 0.17 0 6

S3 0 0 (-1) 0 (-0.17) 1 0

Z=24 Zj 4 4 0 0.68 0
Cj-Zj 0 0 0 (-0.68) 0
Optimal Solution
Iteration-1 Cj 4 4 0 0 0

MinRatio
B CB x1 x2 S1 S2 S3 XB
XB/x1
S1 0 0 1 1 (-0.17) 0 4
x1 4 1 1 0 0.17 0 6

S3 0 0 (-1) 0 (-0.17) 1 0
Z=24 Zj 4 4 0 0.68 0
Cj-Zj 0 0 0 (-0.68) 0

Since all Cj-Zj ≤ 0

Hence, optimal solution is arrived with value of variables as :
x1=6,
x2=0
Max Z=24
Duality in LPP
The Essence
• Every linear program has another linear program associated with it:
Its ‘dual’
• The dual complements the original linear program,
the ‘primal’
• The theory of duality provides many insights into what is happening
‘behind the scenes’

Duality/Sensitivity-25
Primal and Dual
Primal Dual

Decision variables: x Decision variables: y

max Z = cx min W = yb
[Link] Ax  b n [Link] yA  c m
x0 m y0 n

Duality/Sensitivity-26
Primal and Dual - Example
Standard Algebraic Form
Primal Dual
Max Z = 3x1+ 5x2 Min W = 4y1+ 12y2+ 18y3

s. to x1 ≤4 s. to y1+ 3y3 ≥3
2x2 ≤ 12 2y2+ 2y3 ≥5
3x1+ 2x2 ≤ 18
y1, y2, y3 ≥ 0
x1,x2 ≥ 0

Duality/Sensitivity-27