Linear Programming

Linear Programming Eco: - 357 Mathematical Economics

Prepared for Dr. Amir Hussain Department of Economics East West University

Prepared by Kazi Sohag 2005-2-30-016

Date: Sunday, March

C = 40 X 1 + 20 X 2 + 60 X 3 Subject to

Primal problem

2 X 1 + 4 X 2 + 10 X 3 ≥ 24

Minimizing cost 5 X 1 + X 2 + 5 X 3 ≥ 8 X1, X 2 , X 3 ≥ 0 Duel Problem Maximize π = 24V1 +8V2 Subject to 2V1 + 5V2 ≤ 40 4V1 + V2 ≤ 20 10V1 + 5V2 ≤ 60

Basic Solution V1 V2 0 0 20 0 5 0 6 4 2.5 3.33

0 8 0 20 0 12 0 4 7 6.67

Corner Point O(0,0) B(0,8) C(20,0) D(0,20) E(5,0) F(0,12) G(6,0) H(4,4) I(2.5,7) J(3.33,6.66)

Feasible Yes Yes No No Yes No No Yes Yes No

Slope π = 24V1 + 8V2 8V2 = π − 24V1

π − 3V1 8 ∴ Slope = −3 Slope -3 tangent the highest feasible point at H and which point contain the maximum profit. V2 =

whenV1 = 4, V2 = 4

π = 24V1 + 8V2 Maxπ = 24(4) + 8(4) Maxπ = 128 2V1 + 5V2 + t1 = 40 t1 = 12 4V1 + V2 + t 2 = 20 t2 = 0 10V1 + 5V2 + t 3 = 60 t3 = 0 ∴ X1 = 0 X 2 > 0, X 3 > 0 If the decision variables in primal problem are positive (e.g . X 1 , X 2 , X 3 > 0) , corresponding slack variables in the duel problem will be zero and vice versa.

4 X 2 + 10 X 3 = 24 X 2 + 5X 3 = 8 X 2 = 4, X 3 = 0.8 ∴ MinCost C = 40 X 1 + 20 X 2 + 60 X C = 0 + 20( 4) + 60(0.8) C = 80 + 48 C = 128 It is proved since C = π = 128 Thus, the minimum value of C is the as the maximum value of π . Notice that the optimum solutions that produce this optimal value are different: (0,4,0.8) is the optimal solution for primal problem and (4,4) is the optimal solution for the duel problem. The theorem only guarantees that the optimal values of a minimization problem and its duel are equal, not that the optimal solution are same.

Thank you,