23AE2076
Industrial Management
Solving Linear Programming Problem
Simplex Method
Dr. G. Jims John Wessley
Simplex Method – Introduction
• Simplex method is used for solving linear programming
problems when more than two variables are involved
• Conditions to be met
– Variables should be non-negative
– Objective function is to maximize or minimize
• Iterative process which gradually reaches to optimal solution
Definitions
1. Slack Variable :
Variable added to convert constraints into =
Added to the LHS of the constraint equation
Ex : a1x1 + a2x2 b
a1x1 + a2x2 + S1 = b S1 is slack variable
Definitions
2. Surplus Variable :
Variable added to convert constraints into =
Added to the LHS of the constraint equation
Ex : a3x3 + a4x4 b
a3x3 + a3x3 – S2 = b
S2 is surplus variable
Definitions
3. Artificial Variable :
Extra variable added to overcome mathematical
inconvenience (to avoid negative variables)
Added to the LHS of the constraint equation
Ex : a5x5 + a6x6 C
a5x5 + a6x6 – S3 + R1 = b
S3 is surplus variable
R1 is Artificial variable
Simplex Method - Problem 1
• Solve the following LPP using Simplex method
Z = 7 X1 + 6 X2
Subject to
X1 + X2 4
2X1 + X2 6
Where X1, X2 0
Simplex Method - Problem 1
1. Convert constraint equation to standard /normalized
form
X1 + X2 4 X1 + X2 + S1 = 4
2X1 + X2 6 2X1 + X2 + S2 = 6
Maximize Z = 7 X1 + 6 X2 Z = 7 X1 + 6 X2 + 0S1 +0 S2
Also, X1, X2, S1, S2 0
Simplex Method - X1 + X2 + S1 = 4
Problem 1 2X1 + X2 + S2 = 6
Z = 7 X1 + 6 X2 + 0S1 +0 S2
2. Simplex Table – Iteration 1
Cj 7 6 0 0 b =
CB BV X1 X2 S1 S2 b/Key
column
0 S1 1 1 1 0 4 4
0 S2 2 1 0 1 6 3
Key
Zj 0 0 0 0 Row
Cj-Zj 7 6 0 0 (Min
Value
of
Key Element Key column (Max value of Cj-Zj) Cj-Zj)
Simplex Method - Problem 1
2. Simplex Table – Iteration 1
Cj 7 6 0 0 b =
CB BV X1 X2 S1 S2 b/Key
column
0 S1 1 1 1 0 4 4
0 S2 2 1 0 1 6 3
Zj 0 0 0 0
Cj-Zj 7 6 0 0
For optimum solution Cj-Zj 0
Initial Basic Feasible Solution Else move to Iteration 2
Z = 7 X1 + 6 X2 + 0S1 +0 S2 S1 = 4, S2 = 6, X1 = 0, X2 = 0 X 1 = incoming variable &
Z max = 0 S2 = Outgoing variable
Simplex Method
Simplex Method -
Problem 1
Iteration 2
Cj 7 6 0 0 b =
CB BV X1 X2 S1 S2 b/Key
column
0 S1 0 0.5 1 -0.5 1 2
7 X1 1 0.5 0 0.5 3 6
Zj 7 3.5 0 3.5
Cj-Zj 0 2.5 0 -3.5
For optimum solution Cj-Zj 0
Feasible Solution Else move to Iteration 3
Z = 7 X1 + 6 X2 + 0S1 +0 S2 S1 = 1, S2 = 0, X1 = 3, X2 = 0 X 2 = incoming variable &
Z max = 21 S1 = Outgoing variable
Simplex Method -
Problem 1
Iteration 3
Cj 7 6 0 0 b
CB BV X1 X2 S1 S2
6 X2 0 1 2 -1 2
7 X1 1 0 -1 1 2
Zj 7 6 5 1
Cj-Zj 0 0 -5 -1
Optimal Solution For optimum solution Cj-Zj 0
S1 = 0, S2 = 0, X1 = 2, X2 = 2
Z = 7 X1 + 6 X2 + 0S1 +0 S 2
Z = 26
Simplex Method - Problem 2
• Solve the following LPP using Simplex method
Z = X1 + 3 X2
Subject to
X1 5
X1 + 2X2 10
X2 4
Where X1, X2 0
Simplex Method - Problem 2
1. Convert constraint equation to standard /normalized
form
X1 5 X1 + S1 = 5
X1 + 2X2 10 X1 + 2X2 + S2 = 10
X2 4 X2 + S3 = 4
Also, X1, X2, S1, S2, S3 0
Maximize Z = X1 + 3 X2
Z = X1 + 3 X2+ 0S1 +0 S2 +0 S3
Simplex Method - Problem 2
1. Convert constraint equation to standard /normalized
form
Also, X1, X2, S1, S2, S3 0
X1 + S1 + 0S2 + 0S3 = 5
X1 + 2X2 + 0S1 + S2 + 0S3 = 10
X2 + 0S1 + 0S2 + S3 = 4
Z = X1 + 3 X2+ 0S1 +0 S2 +0 S3
X1 + 0X2 S1 + 0S2 + 0S3 = 5
Simplex Method - X1 + 2X2 + 0S1 + S2 + 0S3 = 10
X2 + 0S1 + 0S2 + S3 = 4
Problem 2
Z = X1 + 3 X2+ 0S1 +0S2 +0S3
2. Simplex Table – Iteration 1
Cj 1 3 0 0 0 b =
CB BV X1 X2 S1 S2 S3 b/Key
column
0 S1 1 0 1 0 0 5
0 S2 1 2 0 1 0 10 5
0 S3 0 1 0 0 1 4 4
Zj 0 0 0 0 0
Cj-Zj 1 3 0 0 0
Z = X1 + 3 X2+ 0S1 +0 S2 +0 S3 Z1=0
Simplex Method
- Problem 2
2. Simplex Table – Iteration 2
Cj 1 3 0 0 0 b =
CB BV X1 X2 S1 S2 S3 b/Key
column
0 S1 1 0 1 0 0 5 5
0 S2 1 0 0 1 -2 2 2
3 X2 0 1 0 0 1 4
Zj 0 3 0 0 3
Cj-Zj 1 0 0 0 -3
Z = X1 + 3 X2+ 0S1 +0 S2 +0 S3 S1 = 5, S2 = 2, X2 = 4 Z 2 = 12
Simplex Method
- Problem 2
2. Simplex Table – Iteration 3
Cj 1 3 0 0 0 b
CB BV X1 X2 S1 S2 S3
0 S1 0 0 1 -1 2 3
1 X1 1 0 0 1 -2 2
3 X2 0 1 0 0 1 4
Zj 1 3 0 1 1
Cj-Zj 0 0 0 -1 -1
Z = X1 + 3 X2+ 0S1 +0 S2 +0 S3 S1 = 3, X1 = 2, X2 = 4 Z max = 14