
4
Duality Theory
4.1 Introduction
Every linear program has associated with it another linear program called
the dual. A given linear program and its dual will be related in important
ways. For example, a feasible solution for one will provide a bound on the
optimal objective function value of the other. Also, if one has an optimal
solution, then the other will have an optimal solution as well and the objective
function values of both will be the same. In particular, if one problem has an
optimal solution, then a “certificate” of optimality can be obtained from the
corresponding dual problem verifying the optimality.
The theory related to the relationship ...