SIMPLEX METHOD TO SOLVE LPP:
If the number of variables are more than two , then simplex
method is applicable.
PURE MAXIMIZATION CASE :
When the objective function ‘Z’ is of maximization and all the
constraints are ≤ type, then we use slack variables. Slack
variables are added into the objective function with ‘0’ coefficient
and with ‘1’ coefficient in the constraints in such a way that it
forms unitary matrix.
Steps to solve the problem:
1. Objective function is maximization.
2. All constraints are ≤ type.
3. Slack variables are added with ‘0’ coefficient in ‘Z’ and ‘1’
coefficient in constraints.
4. Zj is computed for each variable.
5. Calculated Cj – Zj for each variable. (Net Evaluation)
6. Select the new entering variable which has maximum value
of net evaluation.
7. Minimum ratio is calculated by dividing the solution value
with the corresponding coefficients of Key column.
8. Select the Key Element
9. Leaving variable is selected with Key Row having positive
minimum ratio.
10. Step 4 to 8 are repeated till we get all C j – Zj ≤ 0 and
then we get optimum solution.
Numerical 1: MaxZ = 6X + 8Y
Subject to 30X + 20Y ≤ 300 5X + 10Y ≤ 110 Where X , Y ≥ 0
Solution:
Simplex method is applicable
MaxZ = 6X + 8Y + 0S1 + 0S2
Subject to
30X + 20Y + 1S1 + 0S2 = 300
5X + 10Y + 0S1 + 1S2 ¿ 110
Where
X , Y, S1 ,S2 ≥ 0
Initial Simplex Table:
Cost : basic variables , RHS , Coeff
Cost each 6 8 0 0
CB B.V Sol X Y S1 S2 Min Ratio
0 S1 30 30 20 1 0 300/20 = 15
0
0 S2 11 5 10 * 0 1 110/10 = 11 →
0
Ne CJ - Zj 6 8 0 0
t
↑
First Simplex Table :
6 8 0 0
CB B.V Sol X Y S1 S2 Min Ratio
0 S1 80 20* 0 1 -2 80/20 = 4 →
8 Y 11 5 /10 1 0 1/10 11/1/2 = 22
CJ - Zj 2 0 0 -8/10
↑
Key element = 20
Convert 20 to 1 and other element ( 5/10 ) into zero by using row operation
Second Simplex Table :
6 8 0 0
CB B.V Sol X Y S1 S2 Min
Ratio
6 X 4 1 0 1/20 -1/10 -----------
--
8 Y 9 0 1 -1/40 3/20 -----------
--
CJ - Zj 0 0 -1/10 -6/10
Hence all net evaluations CJ - Zj <= 0 . Optimal solution exists.
[ 6]
MaxZ = CB X Sol = 8 [ 4 9 ] = 6X4 + 8X9 = 96
Z = 96 at X = 4 and Y = 9
Optimal Solution : MaxZ = 96 at X= 4 , Y = 9
Numerical 2: MaxZ = 500X + 600Y + 1200Z
Subject to 2X + 4Y + 6Z≤ 160 3X + 2Y + 4Z ≤ 120
Where X , Y,Z ≥ 0
Solution:
MaxZ = 500X + 600Y + 1200Z +0S1 + 0S2
Subject to
2X + 4Y + 6Z + 1S1 + 0S2 ¿ 160
3X + 2Y + 4Z +0 S 1+1 S 2=¿ 120
Where
X , Y, S1 ,S2 ≥ 0
Initial Simplex Table:
Cost 500 600 1200 0 0
CB B.V Sol X Y Z S1 S2 Min
Ratio
0 S1 16 2 4 6 1 0 160/6 =
0 26.67 →
0 S2 12 3 2 4* 0 1 120/0 =
0 30
Zj 0 0 0 0 0
Ne CJ - Zj 500 600 1200 0 0
t
↑
First Simplex Table :
Cost 500 600 1200 0 0
CB B.V Sol X Y Z S1 S2 Min
Ratio
1200 Z 160/6 1/3 2/3 1 1/6 0 80
0 S2 80/6 5/3* -4/6 0 -2/3 1 8→
Zj 400 800 1200 200 0
Net CJ - Zj 100 -200 0 -200 0
↑
Second Simplex Table :
Cost 500 600 1200 0 0
CB B.V Sol X Y Z S1 S2 Min
Ratio
120 Z 24 0 4/5 1 27/90 -1/5 -------
0
500 X 8 1 -2/5 0 -2/5 3/5 -------
Zj 500 760 1200 160 60
Net CJ - Zj 0 -160 0 -160 -60
Hence all net evaluations CJ - Zj <= 0 . Optimal solution exists.
[ 1200 ]
MaxZ = CB X Sol = 500 [ 24 8 ] = 1200 X 24 + 500 X 8 = 32800
Optimal Solution : MaxZ = 32800
at X= 8 , Y = 0 , Z = 24
BIG – M Method: ( Only Std formation)
Numerical 3: MinZ = 500X + 600Y + 1200Z
Subject to 2X + 4Y + 6Z≥160 3X + 2Y + 4Z ≥ 120
Where X , Y,Z ≥ 0
Standard Form:
MinZ = 500X + 600Y + 1200Z +0S1 + 0S2 + MA1 + MA2
Subject to
2X + 4Y + 6Z - 1S1 + 0S2 + 1A1 +0A2¿ 160
3X + 2Y + 4Z +0 S 1−1 S 2+ 0 A 1+1 A 2=¿ 120
Where X , Y,S1 , S2, A1,A2 ≥ 0
Numerical 4: MaxZ = 5X + 6Y + 12Z
Subject to 2X + 4Y + 6Z≥160 3X + 2Y + 4Z ≤120
X + Y + Z≥100 Where X , Y,Z ≥ 0
Standard Form:
MaxZ = 5X + 6Y + 12Z +0S1 + 0S2 + 0S3 - MA1 - MA2
Subject to
2X + 4Y + 6Z - 1S1 + 0S2 +0S3 + 1A1 +0A2¿ 160
3X + 2Y + 4Z +0 S 1+1 S 2+0 S 3+0 A 1+0 A 2=¿ 120
X + Y + Z +0 S 1+0 S 2−1 S 3+ 0 A 1+1 A 2=¿ 100
Where X , Y,S1 , S2,S3 A1,A2 ≥ 0