Minimization Example
Solve the following LPP using simplex method
Minimize Z = 2x1 – 3x2 + 6x3
Sbject to 3x1 – x2 + 2x3 ≤ 7
2x1 + 4x2 ≥-12
-4x1 + 3x2 + 8x3 ≤ 10
X1, x2, and x3 ≥ 0
Solution
3x1 – x2 + 2x3 ≤ 7
-2x1 - 4x2 ≤ 12
-4x1 + 3x2 + 8x3 ≤ 10
Add the slack variables
Z = 2x1 – 3x2 + 6x3 + 0S1 + 0S2 + 0S3
3x1 – x2 + 2x3 + S1 ≤ 7
-2x1 - 4x2 + S2 ≤ 12
-4x1 + 3x2 + 8x3 + S3 ≤ 10
CBi Cj 2 -3 6 0 0 0 Solution Ratio
Basic X1 X2 X3 S1 S2 S3
Variable
0 S1 3 -1 2 1 0 0 7
0 S2 -2 -4 0 0 1 0 12
0 S3 -4 3 8 0 0 1 10
Zj 0 0 0 0 0 0 0
Cj – Zj 2 -3 6 0 0 0
Optimality Condition:
Minimization:
All the Cj – Zj ≥ 0
Maximization:
All the Cj – Zj ≤ 0
Select the most negative value as key column
Divide the solution by the elements of the key column
Then select the highest ratio for key row
CBi Cj 2 -3 6 0 0 0 Solution Ratio
Basic X1 X2 X3 S1 S2 S3
Variable
0 S1 5/3 0 14/3 1 0 1/3 31/3 31/3x3/5 = 31/5
0 S2 -22/3 0 32/3 0 1 4/3 76/3 76/3x-3/22=-38/11
-3 X2 -4/3 1 8/3 0 0 1/3 10/3 10/3x-3/4=-10/4
Zj 4 -3 -8 0 0 -1 -10
Cj – Zj -2 0 14 0 0 1
For the entering variable X2, divide the old values by the key element (3).
For New values of S1 and S2, use the formula
Old Value – [Corr. Key Column Value x Corr. new value]
Where X2 row becomes the corresponding new values for both S1 and S2
For S1 Values
3 – [-1 x -4/3] = 3 – 4/3 = 5/3
-1 – [-1 x 1] = -1 + 1 = 0 e.t.c
For S2 Values
-2 – [-4 x -4/3] = -2 – 16/3 = -22/3 e.t.c
For Zj Values
(0 x 5/3) + (0 x -22/3) + (-3 x -4/3) = 0 + 0 + 12/3 = 4
(0x0) + (0x0) + (-3x1) = 0 + 0 – 3 = -3 e.t.c
Test the Optimality Condition after filling in the Cj – Zj row
Pick the most negative number for the key column and then find the ratio by dividing the
solutions by the elements in the key column.
We then pick the most positive number from the ratios for the key row and hence get the key
element.
In the next iteration table, divide the old S1 values by the key element (5/3)
CBi Cj 2 -3 6 0 0 0 Solution Ratio
Basic X1 X2 X3 S1 S2 S3
Variable
2 X1 1 0 14/5 3/5 0 1/5 31/5
0 S2 0 0 156/5 22/5 1 14/5 354/5
-3 X2 0 1 32/5 4/5 0 3/5 58/5
Zj 2 -3 -68/5 -6/5 0 -7/5 -112/5
Cj – Zj 0 0 98/5 6/5 0 7/5
The entering variable X1 values form the new values used in the formula
For New values of S2, use the formula
Old Value – [Corr. Key Column Value x Corr. new value] i.e
-22/3 – [-22/3x1] = -22/3 + 22/3 = 0 e.tc
We use the same formula to find the new values for X2.
We then get all the positive values hence the optimality condition is met.
X3 value is taken to be zero because we didn’t get a new value for it hence optimum solution is -
112/-
X1 = 31/5 , X2 = 58/5 , X3 = 0
This can be tested by substituting into the objective function as;
Minimize Z = 2x1 – 3x2 + 6x3
Z = 2[31/5] – 3[58/5] + 6[0]
= 62/5 – 174/5
= -112/5
