Problems of Linear Programming

Problems of Linear Programming
1

Problem A
Solution:
The LP Problem is,
Max Z = 6 x1 + 4 x2 + 8 x3
Subject to
0 . 02 x1 + 0 .02 x2 + 0 . 02 x3 ≤ 12 ( Molding )
0 . 03 x1 + 0 .02 x2 + 0 . 01 x3 ≤9 ( Curing )
0 . 02 x1 + 0 .01 x2 + 0 . 03 x3 ≤ 16 ( Assembly )
And x1, x2, x3 ≥ 0
We add slack, surplus and artificial variables to convert the problem in canonical form
(Ficken, 21-30). We add slack variables S1 , S2 , S3 S1 to three less than type constraints.
The canonical forms is,
Max Z =6 x1 + 4 x2 + 8 x3+ 0 S1+ 0 S2+ 0 S3
subject to
0 . 02 x1+0 . 02 x2+ 0 . 02 x3 +S1=12
0 . 03 x1+0 . 02 x2+ 0 . 01 x3+S2=9
0 . 02 x1+0 . 01 x2+ 0 . 03 x3+S3 =16
And x1, x2, x3, S1, S2, S3 ≥ 0
B -Z x1 x2 x3 S1 S2 S3 XB
Min Ratio
XB /x3
-Z 1 6 4 8 0 0 0 0
S1 0 0.02 0.02 0.02 1 0 0 12 12/0.02 =
600
S2 0 0.03 0.02 0.01 0 1 0 9 9/0.01 = 900
S3 0 0.02 0.01 0.03 0 0 1 16 16/0.03=
533.33
Positive maximum Z is - 8 and its corresponding column is x3. So, x3 enters the basis.
Minimum ratio is calculated as 533.33 corresponding to the leaving basis variable is S3.
∴ The pivot element is 0.03.
2

So, the new tableau is,
B -Z x1 x2 x3 S1 S2 S3 XB
Min Ratio
XB/ x2
-Z 1 0.666
7
1.333
3 0 0 0
-
266.66
7
4266.6
7
S1 0 0.006
7
0.013
3 0 1 0 -0.67 1.33 1.33/0.0133
= 100
S2 0 0.023
3
0.016
7 0 0 1 -0.33 3.67 3.67/0.0167
= 220
x3 0 0.666
7
0.333
3 1 0 0 33.33 533.33
533.33/
0.3333 =
1600
Positive maximum Z is 1.3333 and its corresponding column vector is the next entering
variable x2.
Calculated minimum ratio is 100 for the leaving basis variable S1.
∴ The pivot element is 0.0133.
New R1 = Old R1 × 75
New R2 = Old R2 - 0.0167* NewR1
New R3 = Old R3 - 0.33* New R1
B -Z x1 x2 x3 S1 S2 S3 XB MinRatio
-Z 1 0 0 0 -100 0 -200 4400
x2 0 0.5 1 0 75 0 -50 100
S2 0 0.015 0 0 -1.25 1 0.5 2
x3 0 0.5 0 1 -25 0 50 500
Since all Z j≤0
Hence, optimal solution is x1 = 0, x2 = 100, x3 = 500, Max Z = 4400
3

Problem B
Solution:
The LP problem is,
Max z = 2 x1 + x2 + x3
subject to
2 x1 + 3 x2−x3 ≤ 9
2 x2+ x3 ≥ 4
x1+ x3 = 6
and x1, x2, x3 ≥ 0
-->Phase-1<--
We add slack variable S1 to the first constraint. We subtract surplus variable S2 from the
second constraint and add artificial variable A1. For the third constraint we add artificial
variable A2
Phase 1 problem is,
Max z =-A1 -A2
subject to
2 x1 + 3 x2- x3+ S1= 9
2 x2+ x3 - S2 + A1 = 4
x1 + x3 + A2 = 6
and x1, x2, x3, S1, S2, A1, A2 ≥ 0
B -Z x1 x2 x3 S1 S2 A1 A2 XB
Min
Rati
o
XB /
x2
-Z 1 0 0 0 0 0 -1 -1 0
S1 0 2 3 -1 1 0 0 0 9
A1 0 0 2 1 0 -1 1 0 4
A2 0 1 0 1 0 0 0 1 6
4