5 Duality

Every linear programme has a twin, its dual, built from the same data. If the original problem, the primal, asks how to use scarce resources to maximise profit, the dual asks what the resources are worth. The two problems have the same optimal value, the solution of each certifies the optimality of the other, and the dual variables are the shadow prices met in the simplex tableau. Duality is the central theoretical result of linear programming; it underlies sensitivity analysis, the theory of games, the dual simplex method and most algorithms for large problems.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.