Dual problem

Although the primal program offers a solution by the simplex method, we have only the guarantee of not being able to improve the solution. In order to prove that this is an optimal solution, we must also solve its dual program. This dual program, in addition to ensuring optimality or not, will also analyze the sensitivity of variables to change.

Dual program

The dual program is a symmetry of the primal program:

There is a constraint for each variable of the primal program; and a dual variable for each constraint of the primal program; the coefficients of the primal objective function are elements b of the dual and vice versa.
It should be noted that the dual of the dual is the primal.

primdual

dual

Weak duality: for any solution of the dual and for any solution of the primal, the objective value of the dual z=cx* is greater than or equal to that of the primal w=by*.

dual2

Strong duality: if the primal has an optimal solution x* and the dual has an optimal solution y* then the objective value of the primal is equal to that of the dual.

Since the dual of the dual is the primal, the primal has an optimal solution if and only if the dual has an optimal solution.

There is a relationship in the solutions of primal and dual:

  • if a problem has feasible solutions and a bounded domain for the objective function, then it is the same for its dual.
  • if a problem has feasible solutions and an unbounded domain for the objective function, then its dual has no feasible solution.
  • if a problem has no feasible solutions, the dual has either an unbounded domain for the objective function, or has no feasible solutions.

Complementary slackness

v.I. Let x* and y* be the solutions of primal and dual. These two solutions are optimal if and only if:

  • for  j from 1 to n
    • either the constraint j of the dual is saturated
    • either x*j=0
    • or both
  • for i from 1 to m
    • either the constraint i of the primal is saturated
    • either y*i=0
    • or both

dual3

v.II. A solution x of the primal is optimal if and only if there exists a vector y* such that:

  • y* is in the domain
  • if xj>0 then the constraint j of the dual is saturated
  • if the constraint i of the primal is not saturated then y*i=0

It is possible to build a solution of one program from the other, and to prove the strong duality for the optimality of the solution.

economic-interpretation-of-duality-shadow-price-and-the-complementary-slackness-property-19-638

Interpretation of the dual program

dual4

 

Publicités