Dual program

Dual program

Although the primal program offers a solution by the method of simplex, we are only guaranteed not to be able to improve the solution. In order to prove that it is an optimal solution, we must also solve its dual program. This dual program, in addition to guaranteeing whether or not optimality, will also make it possible to analyze the sensitivity of the variables to change.

When the primal program has more variables than constraints, then there is no guaranteed solution (as for a system of equations). In this case, it is preferable to go through the dual in order to find a solution.

Construction of the 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.

For the following special transformation rules, the primal is considered to be under the canonic form :

• If the variable i of the primal is positive or zero, then the constraint i of the dual is in its canonical form
• If the variable i of the primal is a real number, then the constraint i of the dual is an equality (logical if we consider equality as a combination of “less than or equal” and “greater or equal”)
• If the constraint j of the primal is in canonical form, then the variable j of the dual is positive or zero
• If the constraint j of the primal is an equality, then the variable j of the dual is a real number (logical if we consider equality as a combination of “less than or equal” and “greater or equal”)

Considering the transformation of a linear program in canonical form, the second point and the fourth point are normally not applied during the transformation into dual for the calculation of the Simplex!

Here is a summary of the transformation into Dual by the canonical form.

Weak duality and strong duality

Low 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 *.

Strong duality : if the primal has an optimal solution x * then the dual has an optimal solution y * and 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 relation in the solutions of the primal and the dual:

• if a problem has feasible solutions and a bounded domain for the objective function, then so does 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 either has an unbounded domain for the objective function, or has no feasible solutions.

Interpretation of the dual program