Identify the optimal solution and construct the dual for this (primal) problem C
ID: 3034699 • Letter: I
Question
Identify the optimal solution and construct the dual for this (primal) problem
Consider the following LP problem: Maximize z = 3 x_1 + x_2 + 4 x_3 6x_1 + 3x_2 + 5x_3 lessthanorequalto 25 3x-1 + 2x_2 + 5x_3 lessthanorequalto 20 x_i greaterthanorequalto 0, i = 1, 2, 3 the corresponding final set of equations yielding the optimal solution is z = 2x_2 + 1/5 x_4 + 3/5 x_5 = 17 x_1 - 1/3 x_2 + 1/3 x_4 - 1/3 x_4 - 1/3 x_5 = 5/3 x_2 + x_3 - 1/5 x_4 + 2/4 x_5 = 3. Identify the optimal solution and construct the dual for this (primal) problem. Identify the shadow prices for the resources in the primal problem. Identify the optimal solution for the dual problem from the final set of equations and check if indeed it is optimal. Conduct sensitivity analysis for (i.e., in which range the current solution is optimal): b_1 - and, if you let b_1 = 10, is the current basic solution still optimal? C_3 - (cost coefficient for x_3) is current solution still optimal if C_3 = 2? C_2 - (cost coefficient for x_2) is current solution still optimal if C_2 = 3?Explanation / Answer
Tableau #1
x y z s1 s2 s3 s4 s5 p
6 3 5 1 0 0 0 0 0 25
3 4 5 0 1 0 0 0 0 20
1 0 0 0 0 -1 0 0 0 0
0 1 0 0 0 0 -1 0 0 0
0 0 1 0 0 0 0 -1 0 0
-3 -1 -4 0 0 0 0 0 1 0
Tableau #2
x y z s1 s2 s3 s4 s5 p
6 3 5 1 0 0 0 0 0 25
3 4 5 0 1 0 0 0 0 20
-1 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 -1 0 0 0
0 0 1 0 0 0 0 -1 0 0
-3 -1 -4 0 0 0 0 0 1 0
Tableau #3
x y z s1 s2 s3 s4 s5 p
6 3 5 1 0 0 0 0 0 25
3 4 5 0 1 0 0 0 0 20
-1 0 0 0 0 1 0 0 0 0
0 -1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 -1 0 0
-3 -1 -4 0 0 0 0 0 1 0
Tableau #4
x y z s1 s2 s3 s4 s5 p
6 3 5 1 0 0 0 0 0 25
3 4 5 0 1 0 0 0 0 20
-1 0 0 0 0 1 0 0 0 0
0 -1 0 0 0 0 1 0 0 0
0 0 -1 0 0 0 0 1 0 0
-3 -1 -4 0 0 0 0 0 1 0
Tableau #5
x y z s1 s2 s3 s4 s5 p
3 -1 0 1 -1 0 0 0 0 5
3/5 4/5 1 0 1/5 0 0 0 0 4
-1 0 0 0 0 1 0 0 0 0
0 -1 0 0 0 0 1 0 0 0
3/5 4/5 0 0 1/5 0 0 1 0 4
-3/5 11/5 0 0 4/5 0 0 0 1 16
Tableau #6
x y z s1 s2 s3 s4 s5 p
1 -1/3 0 1/3 -1/3 0 0 0 0 5/3
0 1 1 -1/5 2/5 0 0 0 0 3
0 -1/3 0 1/3 -1/3 1 0 0 0 5/3
0 -1 0 0 0 0 1 0 0 0
0 1 0 -1/5 2/5 0 0 1 0 3
0 2 0 1/5 3/5 0 0 0 1 17
Optimal Solution: p = 17; x = 5/3, y = 0, z = 3