Duality & Sensitivity Testing

Solving the dual problem

Maximize z = 40w₁ + 50w₂

subject to

2w₁ + 3w₂ £ 3
4w₁ + 2w₂ £ 3

w₁, w₂ ³ 0

After adding slack variables, we have

Maximize z = 40w₁ + 50w₂ + 0x₃ + 0x₄

2w₁ + 3w₂ + x₃ = 3
4w₁ + 2w2 + x₄ = 3
w₁, w₂, x₃, x₄ ³ 0

Where x₃ and x₄ are slack variables.

Initial basic feasible solution

w₁= 0, w₂ = 0, z = 0
x₃ = 3, x₄ = 3

Table 1

Table 2

Table 3

The optimal solution is:
w₁ = 3/8, w₂ = 3/4
z = 40 X 3/8 + 50 X 3/4= 105/2.

In case of primal problem, you noted that the values of z_j-c_j under the surplus variables x₃ and x₄ were 3/8 and 3/4. In case of dual problem, these values are the optimal values of dual variables w₁ and w₂.

The optimal values of the dual variables are often called shadow prices.

Further, the values of the objective functions in both the problems are same (i.e., 105/2)

Important Primal-Dual Results

1. If one problem has an unbounded optimal solution, then the other problem cannot have a feasible solution.
2. Optimal solution of either problem gives complete information about the optimal solution of the other.
3. If either the primal or dual problem has a finite optimal solution, then the other has also a finite optimal solution.
4. The dual of a dual is primal.