Linear Programming and Resource Allocation Modeling

6Duality Theory

6.1 The Symmetric Dual

Given a particular linear programming problem, there is associated with it another (unique) linear program called its dual. In general, duality theory addresses itself to the study of the connection between two related linear programming problems, where one of them, the primal, is a maximization (minimization) problem and the other, the dual, is a minimization (maximization) problem. Moreover, this association is such that the existence of an optimal solution to any one of these two problems guarantees an optimal solution to the other, with the result that their extreme values are equal. To gain some additional insight into the role of duality in linear programming, we note briefly that the solution to any given linear programming problem may be obtained by applying the simplex method to either its primal or dual formulation, the reason being that the simplex process generates an optimal solution to the primal‐dual pair of problems simultaneously. So with the optimal solution to one of these problems obtainable from the optimal solution of its dual, there is no reason to solve both problems separately. Hence the simplex technique can be applied to whichever problem requires the least computational effort.

We now turn to the expression of the primal problem in canonical form and then look to the construction of its associated dual. Specifically, if the primal problem appears as

then its dual is

Henceforth, this form of the dual will ...