Question

[6.4] Solve the following linear program by a graphical method:

Maximize 3x₁ + 3x₂ + 21x₃

subject to 6x₁ + 9x₂ + 25x₃ <= 15

3x₁ + 2x₂ + 25x₃ <= 20

x₁ , x₂ , x₃ >= 0

(Hint: utilize the dual problem.)

   

Answer 1

Dual of the problem is following:

Minimize 15y1+20y2

s.t.

6y1+3y2 >= 3

9y1+2y2 >= 3

25y1+25y2 >= 21

y1, y2 >= 0

Solution using graphical method is following:

Optimal solution of the dual is:

y1 = 0.84

y2 = 0

The objective function at the optimal intersects only constraint 3 . Therefore, constraiint 3 is the binding constraint and the other two constraints are non-binding. So dual price of constraint 1 and 2 = 0

To find the dual price of constraint 3, increase its RHS by 1 unit and note the difference in the objective value.

the new point of intersection (optimal point) = 22/25 = 0.88

New objective value = 15*.88+20*0 = 13.2

Increase in objective value = 13.2 - 12.6 = 0.6

Which means the dual price of constraint 3 is 0.6

According to duality theorem, the solution of the primal is the dual price of the dual

So, optimal solution of the primal is:

x1 = 0 (dual price of constraint 1 of the dual)

x2 = 0 (dual price of constraint 2 of the dual)

x3 = 0.6 (dual price of constraint 3 of the dual)

Objective value = 12.6 (objective value of primal and dual is the same)