Linear programming - Optimal Solution, Dual Variable

Question

Common Data for Question 01 & 02

Consider a linear programming problem with two variables and two constraints. The objective function is: Maximize x₁ + x₂. The corner points of the feasible region are (0,0), (0,2), (2,0) and (4/3, 4/3).

Q1. If an additional constraint x₁ + x₂ $\leq$5 is added, the optimal solution is                                                                                                      

      (a) $\left ( \frac{5}{3},\frac{5}{3} \right )$                                                              (b) $\left ( \frac{4}{3},\frac{4}{3} \right )$ 

      (c) $\left ( \frac{5}{2},\frac{5}{2} \right )$                                                             (d)  $\left ( 5,0 \right )$

 

Q2. Let y₁ and y₂ be the decision variables of the dual and v₁ and v₂ be the slack variables of the dual of the given linear programming problem. The optimum dual variable are

      (a) y₁ and y₂                                                              (b) y₁ and v₁

      (c) y₁ and v₂                                                              (d) v₁ and v₂

Answer 1

Q1. Option B

If you draw the feasible region on graph with given corner points, it will look as follows. We know that optiomal solution of a LP lies in one of the corner poins f the feasible region. With the given corner points, if we calculate the objective value,

Obj. value with O (0,0) is 0+ 0 = 0

Obj. value with A (2,0) is 2 + 0 = 2

Obj. value with C (0,2) is 0 + 2 = 2

Obj. value with B (4/3,4/3) is 4/3+4/3= 8/3.

Optimal solution is (4/3.4/3)

 

 

Also, draw the given constraint. As you can see, new constraint added is out of feasible region. So, the corner points of the feasible regin doesnt change. Optimal slution remains the same i.e, (4/3,4/3).

Q2.  Option A

Y1 and Y2 are the decision variables or dual variables corresponding to the dual of the given LP. 

v1 and v2 are the slack variables of the dual problem which helps us in determining the optimal solutions and also help us in finding which constraints are binding and which or not. 

For example, consider the following constraint of the given LP (derived from corner points given)

2x1 + x2 +S1 ==  4 (Y1).  

Here, S1 is the primal slack variable and Y1 is the dual variable or shadow price associated with the constraint. 

If S1 = 0, that means constraint is binding, then Y1 will be positive as shadow price will take a positive value if we increase RHS of this constraint. 

If S1 > 0, that means constraint is not binding, then Y1 will be zero as objective value doesnt change even if we increase RHS of this constraint. 

Same applies to dual slack variables. So, optimal dual variables are the decision variables of the dual problem.