ENGINEERING OPTIMIZATION
Tutorial-05 (28th February 2022)
BITS Pilani
Pilani Campus
(ME F320)
Consider the following LPP
Maximize Z = 2x1 + 2x2 + 4x3
Subject to
2x1+ x2+ x3 ≥ 2
3x1+ 4x2+ 2x3 ≤ 8
x1 - 2x2 - 3x3 ≤ 5
x1 , x2 , x3 ≥ 0
BITS Pilani, Pilani Campus
Initial optimal solution
Iteration 0
BV x1 x2 x3 S1 A1 S2 S3 Solution
Z -2 -2 -4 0 -100 0 0 0
A1
S2
2
3
1
4
1
2
-1
0
1
0
0
1
0
0
2
8
x1 = 0
S3 1 -2 -3 0 0 0 1 5
x2 = 0
Iteration 4 Optimal
BV x1 x2 x3 S1 A1 S2 S3 Solution
x3 = 4
Z 4 6 0 0 100 2 0 16
x3 3/2 2 1 0 0 ½ 0 4 Max Z = 16
S1 -1/2 1 0 1 -1 ½ 0 2
S3 11/2 4 0 0 0 3/2 1 17
BITS Pilani, Hyderabad Campus
P1- “Verify the optimal table using Post Optimal Analysis”
Iteration 0
BV x1 x2 x3 S1 A1 S2 S3 Solution
Z -2 -2 -4 0 -100 0 0 0
A1 2 1 1 -1 1 0 0 2
S2 3 4 2 0 0 1 0 8
A
S3
x3 S1 S3
1 -2 -3 0 0 0 1 5
1 -1 0
Iteration 4 Optimal
2 0 0
BV x1 x2 x3 S1 A1 S2 S3 Solution
-3 0 1
Z 4 6 0 0 100 2 0 16
x3 3/2 2 1 0 0 ½ 0 4
S1 -1/2 1 0 1 -1 ½ 0 2
S3 11/2 4 0 0 0 3/2 1 17
BITS Pilani, Hyderabad Campus
P1- Inverse of Basic Variable
A I
x3 S1 S3 A1 S2 S3
1 -1 0 1 0 0
2 0 0 0 1 0 A.x=b
-3 0 1 0 0 1
I A-1
x3 S1 S3 A1 S2 S3
[x] BV = A-1.b
1 0 0 0 1/2 0
0 1 0 -1 1/2 0
0 0 1 0 3/2 1
BITS Pilani, Hyderabad Campus
P1- Coefficients of Constraints
A-1 xi
[ ][ ][ ]
0 1/ 2 0 −2 3/ 2
C X1 = −1 1/ 2 0 * 3 = −1/ 2
0 3/ 2 1 1 11 / 2
[ ][ ][ ]
0 1/ 2 0 1 2
C X2 = −1 1/ 2 0* 4 = 1
0 3/ 2 1 2 4
[ ][ ][ ]
0 1/ 2 0 1 1
C X3 = 0 This Verifies in
= −1 1/ 2 0* 2 iteration 4
−3 0
0 3/ 2 1
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
P1- Dual of LPP
Maximize Z = 2x1 + 2x2 + 4x3 Dual of Z
Minimize S = 2y1 + 8y2 + 5y3
Subject to
Subject to
2x1+ x2+ x3 ≥ 2
3x1+ 4x2+ 2x3 ≤ 8 2y1 + 3y2 + y3 ≥ 2
x1 - 2x2 - 3x3 ≤ 5 y1 + 4y2 - 2y3 ≥ 2
y1 + 2y2 – 3y3 ≥ 4
x1 , x2 , x3 ≥ 0
y1 ≤ 0 and y2, y3 ≥ 0
BITS Pilani, Pilani Campus
P1- Post optimal analysis using Duality
[ ]
Dual Variables: 0 1/ 2 0
[] ═ [𝑥 3¿ 𝑆 1¿𝑆 3 []𝐼𝑛𝑣𝑒𝑠𝑒 𝑜𝑓 𝐴 ] ═ [ 4 ¿0 ¿0 ] −1 1/ 2 0 ═ [ 0¿ 2¿0 ]
0 3/ 2 1
x1 ; 2y1 + 3y2 + y3 – 2 = 4
Coefficients of non basic xi: x ; y + 4y – 2y -2 = 6
2 1 2 3
S2 ; y 2 – 0 = 2
BV x1 x2 x3 S1 A1 S2 S3 Solution
Z 4 6 0 0 100 2 0 16
x3 3/2 2 1 0 0 ½ 0 4
S1 -1/2 1 0 1 -1 ½ 0 2
S3 11/2 4 0 0 0 3/2 1 17
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
P2-1 POA: Changes in the feasibility
If the RHS of constraints of original problem changed to 4, 3, Maximize Z = 2x1 + 2x2 + 4x3
=>
& 10.
Subject to 2x1+ x2+ x3 ≥ 4
Since, RHS of original Problem is changed to [4 3 10]
Change in 4th iteration
3x1+ 4x2+ 2x3 ≤ 3
[ [] ] [ ]
x1 - 2x2 - 3x3 ≤ 10
0 1/ 2 0 4 3/2
=> −1 x1, x 2, x 3 ≥ 0
1/ 2 0 3 = −5 / 2
0 3/ 2 1 10 29 /2
Iteration 4* BV x1 x2 x3 S1 A1 S2 S3 Solution
Z 4 6 0 0 100 2 0 16
x3 3/2 2 1 0 0 ½ 0 3/2
S1 -1/2 1 0 1 -1 ½ 0 -5/2
S3 11/2 4 0 0 0 3/2 1 29/2
BITS Pilani
P2-1 Contd..
Dual Simplex
Iteration
4* BV x1 x2 x3 S1 S2 S3 Solution
Z 4 6 0 0 2 0 16
x3 3/2 2 1 0 ½ 0 3/2
S1 -1/2 1 0 1 ½ 0 -5/2
S3 11/2 4 0 0 3/2 1 29/2
R0 → R0 - 8R2 R1 → R1 + 3R2 R2 → (-2)*R2 R3 → R3 + 11R2
Iteration 5
BV x1 x2 x3 S1 S2 S3 Solution Ratio
Z 0 -2 0 -8 -4 0 36
x3 0 2 1 0 ½ 0 3/2 (3/2)/0 Undefined
x1 Negative
1 -2 0 -2 -1 0 5 5/-2
Undefined
S3 0 4 0 0 3/2 1 29/2 (29/2)/0
BITS Pilani
P2-2 POA: Addition of the constraint
If there is addition of the following constraint: x1 - x2 + 3x3 ≤ 20
Maximize Z = 2x1 + 2x2 + 4x3
Subject to Is the New constraint satisfying the already
2x1+ x2+ x3 ≥ 4 found optimal solution?
3x1+ 4x2+ 2x3 ≤ 3 Þ 0-0+3*4 = 12 ≤ 20 (Satisfying)
x1 - 2x2 - 3x3 ≤ 10
x1 - x2 + 3x3 ≤ 20
x1, x2, x3 ≥ 0
BITS Pilani
P2-2 Contd..
BV x1 x2 x3 S1 S2 S3 S4 Solution
R0 Z 4 6 0 0 2 0 0 16
R1 x3 3/2 2 1 0 ½ 0 0 4
R2 S1 -1/2 1 0 1 ½ 0 0 2
R3 S3 11/2 4 0 0 3/2 1 0 17
R4 S4 1 -1 3 0 0 0 1 20
R4 → R4 - 3R1
BV x1 x2 x3 S1 S2 S3 S4 Solution
Z 4 6 0 0 2 0 0 16
x3 3/2 2 1 0 ½ 0 0 4
S1 -1/2 1 0 1 ½ 0 0 2
S3 11/2 4 0 0 3/2 1 0 17
S4 -7/2 -7 0 0 -3/2 0 1 8
Thus, there is no change in the optimal solution.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
P3-1 POA: Change in Coeff. of objective function
Dual Variable:
If the change in objective function is
[ ]
0 1/ 2 0
Max Z* = 3x1 + x2 + 5x3 [] ═ [ 5¿0 ¿0 ] −1 1/ 2 0 ═ [ 0¿5 / 2¿0 ]
0 3/ 2 1
Minimize S = 2y1 + 8y2 + 5y3
New coefficients Non-basic of variables in Z row in the 4 th
iteration →
S.T 2y1 + 3y2 + y3 ≥ 3 x1 ; 2y1 + 3y2 + y3 – 2 = 11/2
y1 + 4y2 - 2y3 ≥ 1 x2 ; y1 + 4y2 – 2y3 -2 = 8
y1 + 2y2 – 3y3 ≥ 5 S2 ; y2 - 0 = 5/2
Iteration 4*y1 ≤ 0 and y2, y3 ≥ 0
BV x1 x2 x3 S1 S2 S3 Solution
Z 11/2 8 0 0 5/2 0 20
x3 3/2 2 1 0 ½ 0 4
S1 -1/2 1 0 1 ½ 0 2
S3 11/2 4 0 0 3/2 1 17
BITS Pilani
P3-2 POA: Addition of New Variable
If a new variable x4 is added such that
Maximize Z = 2x1 + 2x2 + 4x3 + 3x4
Subject to
2x1+ x2+ x3 + 2x4 ≥ 2
3x1+ 4x2+ 2x3 + 4x4 ≤ 8
x1 - 2x2 - 3x3 + x4 ≤ 5
Iteration 0*
x1, x2, x3 ≥ 0 BV x1 x2 x3 x4 S1 S2 S3 Solution
Z -2 -2 -4 -3 0 0 0 0
A1 -2 1 1 2 -1 0 0 2
S2 3 4 2 4 0 1 0 8
S3 1 -2 -3 1 0 0 1 5
BITS Pilani
P3-2 Addition of New Variable
[ ][ ]
Coeffn of Constraints of x4 = 2 2
4 0
1 =7
Also, to find constraint of x4 in Z row, we have y1, y2, y3.
New Duality constraint => 2y1 + 4y2 + y3 ≥ 3
New coefficient of x4 in Z row: 2y1 + 4y2 + y3 – 3 = 2*(0) + 4*(5/2) + 0 – 3 = 7
Iteration 4*
BV x1 x2 x3 x4 S1 S2 S3 Solution
Z 4 6 0 7 0 2 0 16
x3 3/2 2 1 2 0 ½ 0 4
S1 -1/2 1 0 0 1 ½ 0 2
S3 11/2 4 0 7 0 3/2 1 17
No Change in the optimal solution
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Thank You
BITS Pilani
Pilani Campus