Linear Programming: Duality, Optimality Conditions Homework Solution

This assignment solution covers several aspects of linear programming duality and optimality conditions. It includes problems related to finding the dual of a given linear program, interpreting shadow prices, and verifying complementary slackness. The solution demonstrates how to formulate the dual problem, solve both the primal and dual problems, and interpret the results in terms of shadow prices. The solution also illustrates the application of complementary slackness, showing that the product of the optimal primal variables and the surplus variables of the dual is zero, and vice versa. The document further discusses the transformation of constraints and the implications for the dual problem. Desklib offers a wide range of study tools and solved assignments to help students excel in their studies.

1) a)
Dual of the problem is
Minimize v=6 y1 +7 y2+10 y3
Subject to:
12 y1−3 y2 ≥ 2
y1 + y2+ y3 ≥ 1
y3 ≥0
y1 ≥ 0 , y2 ≥ 0
b) Solution of Primal
The leaving variable is P1 and entering variable is P2.

The optimal solution value is Z = 6
X1 = 0
X2 = 6
The optimal solution value is Z = 7
X1 = 0
X2 = 7
Shadow prices of constraint 1
= (7-6)/ (1) = 1
The optimal solution value is Z = 6
X1 = 0
X2 = 6
Shadow prices of constraint 2
= (6-6)/ (1) = 0
The optimal solution value is Z = 6
X1 = 0
X2 = 6
Shadow prices of constraint 3
= (6-6)/ (1) = 0
Solution of dual

The optimal solution value is Z = 6
X1 = 1
X2 = 0
X3 = 0
Solution of the dual matches with the shadow prices of the primal. So shadow prices solve
the dual problem.
2)

a) Maximize 2 x1 +x2
+¿+x2
−¿+ 3 x3+ x4
+ ¿+ x4
−¿ ¿ ¿
¿¿
Subject to:
x1+ x2
+¿+ x2
−¿+ x3+ x4
+¿ + x4
−¿+ x 5
=5¿
¿
¿ ¿
2 x1 −x2
+¿−x2
−¿+ 3 x3=−4¿ ¿
x1−x3+ x4
+¿+ x4
−¿−x6=1 ¿¿
x1 ≥ 0 , x2
+¿ ≥0 , x2
−¿≥ 0 ,x3≥ 0 ,x4
+¿ ≥0, x 4
−¿ ≥0, x5 ≥0,x 6≥0 ¿
¿
¿¿
b) Dual of part a
Minimize 5 y1−4 y2− y3
Subject to:
y1 +2 y2− y3 ≥ 2
y1− y2=1
y1 +3 y2+ y3 ≥ 3
y1− y3 ≥1
y1 ≥ 0 , y3 ≥0 , y2 unrestricted ∈sign
Dual of transformed equations in part a
Minimize 5 y1−4 y2− y3
Subject to:
y1 +2 y2− y3 ≥ 2
y1− y2 ≥1
y1− y2 ≥3
y1 +3 y2+ y3 ≥ 3

y1− y3 ≥1
y1− y3 ≥1
y1 ≥ 0 , y3 ≥0 , y2 unrestricted ∈sign
We can see both the dual are same in equations.
3)
a) Primal is
Maximize 1 2 x1 +20 x2 +18 x3+ 40 x4
Subject to:
4 x1 +9 x2 +7 x3 +10 x4 ≤ 6
x1+ x2 +3 x3+ 40 x4 ≤ 4
x1 ≥ 0 , x2 ≥ 0 , x3 ≥0 , x4 ≥ 0
Dual is:
Minimize 6 y1 +4 y2
Subject to:
4 y1+ y2 ≥ 12
9 y1 + y2 ≥ 20
7 y1 +3 y2 ≥ 18
10 y1+40 y2 ≥ 40
y1 ≥ 0 , y2 ≥ 0
Optimal solution of the dual:

The optimal solution value is Z = 56 / 3
X1 = 44 / 15
X2 = 4 / 15
b) In the table the term is not clearly mentioned so the calculations cannot be done to
cross verify.
c) From the optimal solutions of the primal is individually multiplied by the surplus
variable of the dual then it is zero and similarly when the optimal solution of the dual
variable is individually multiplied by the slack variable then also it is zero. SO this proves
the complementary slackness property