ENGINEERING OPTIMIZATION
Tutorial-04 (21st February 2022)
BITS Pilani
Pilani Campus
(ME F320)
PROBLEM NO : 1 Dual of a Dual is a Prime
Consider the following LPP-
Maximize Z = 4x1 + x2
Subjected to
3x1 + 2x2 ≤ 6
6x1 + 3x2 ≤ 10
x1, x2 ≥ 0
Let the variables of dual LP be y1 and y2
BITS Pilani, Hyderabad Campus
Solution 1
The dual LP is- Dual of the dual LP is-
Minimize W = 6y1 + 10y2 Maximize S = 4v1 + v2
Subjected to, Subjected to,
3v1 + 2v2 ≤ 6
3y1 + 6y2 ≥ 4
6v1 + 3v2 ≤ 10
2y1 + 3y2 ≥ 1 v1, v2 ≥ 0
y1, y2 ≥ 0
Let the variables of second dual LP be
v1 and v2
BITS Pilani, Pilani Campus
PROBLEM NO : 2 “Change in the coefficient of Z row”
(Algebraic Approach)
Maximize Z = 2x1 -x2 + x3
The given problem is same as the problem given in the
Subject to previous tutorial where changes were made in the RHS.
3x1- 2x2+ 2x3 ≤ 15
-x1+ x2+ x3 ≤ 3
x1 - x2 + x3 ≤ 4
x1, x2, x3 ≥ 0
Use sensitivity analysis to find the change in the maximum value of Z when the
coefficients of x1, x2 and x3 are changed to 6, -3, 8 respectively.
BITS Pilani, Hyderabad Campus
Change the coefficients
Let the change in coefficient in the z row will be d1, d2 and d3 respectively
Therefore
Z*= (2+d1)x1 + (-1+d2)x2 + (1+d3)x3
Subject to (No Change in constraints)
=> d1 = 4
d2 = -2
d3 = 7
BITS Pilani, Hyderabad Campus
Original solution
Iteration 0
Basic Z X1 X2 X3 S1 S2 S3 Value
𝑅0 Z 1 -2 1 -1 0 0 0 0
𝑅1 S1 0 3 -2 2 1 0 0 15
𝑅2 S2 0 -1 1 1 0 1 0 3
𝑅3 S3 0 1 -1 1 0 0 1 4
Iteration 3
Basic Z X1 X2 X3 S1 S2 S3 Value
Z 1 0 0 2 1 1 0 18
x2 0 0 1 5 1 3 0 24
S3 0 0 0 2 0 1 1 7
x1 0 1 0 4 1 2 0 21
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Contd
Iteration 3
Basic Z X1 X2 X3 S1 S2 S3 Value
0 -d1 -d2 -d3 0 0 0 0
Z 1 0 0 2 1 1 0 18
x2 0 0 1 5 1 3 0 24
S3 0 0 0 2 0 1 1 7
x1 0 1 0 4 1 2 0 21
Iteration 4 R0→ R0 + d2×R1 + d1×R3
Basic Z X1 X2 X3 S1 S2 S3 Value
0 0 0 -d3 + 5d2 +4d1 d1 + d 2 2d1 + 3d2 0 21d1 + 24d2
Z 1 0 0 2 1 1 0 18
x2 0 0 1 5 1 3 0 24
S3 0 0 0 2 0 1 1 7
x1 0 1 0 4 1 2 0 21
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Optimality check
2 - d3 + 5d2 + 4d1 ≥ 0 1≥0
Satisfied- Optimal solution is unchanged
1+ d1+ d2 ≥ 0 3≥0
1+ 2d1 + 3d2 ≥ 0 3≥0
So, Final Solution
Z* = 18 + 21d1 + 24d2
Z* = 54
@ x1 = 21 x2 = 24 S3 = 7 and x3, S1, S2 = 0
BITS Pilani, Hyderabad Campus
PROBLEM NO : 3 “Solve the LPP Using Graphical
Method”
Consider the following LPP:
Maximize z = 5x1 + 2x2 + 3x3
subject to
x1 + 5x2 + 2x3 ≤ 15
x1 - 5x2 - 6x3 ≤ 20
x1 , x2 , x3 ≥ 0
BITS Pilani, Hyderabad Campus
Prime to Dual
Prime Let y1 and y2 be the dual variables.
Maximize z = 5x1 + 2x2 + 3x3 Minimize W = 15y1 + 20y2
subject to subject to
x1 + 5x2 + 2x3 ≤ 15 y1 + y2 ≥ 5
x1 - 5x2 - 6x3 ≤ 20 5y1 - 5y2 ≥ 2
x1, x2, x3, ≥ 0 2y1 - 6y2 ≥ 3
y1, y2 ≥ 0
BITS Pilani, Pilani Campus
Solution
(1) → y1 + y2 = 5
(2) → 5y1 - 5y2 = 2
(3) → 2y1 - 6y2 = 3
Optimal Solution @ (5,0)
Min W = 5×15 + 0×20 = 75
Thus Max Z = 75
A
BITS Pilani, Hyderabad Campus
Thank You
BITS Pilani
Pilani Campus