Strong Duality: Without Simplex and without theorems of alternatives

The simplex method has its own problems related to degenerate basic feasible solutions. While such solutions are infrequent, from a theoretical standpoint a proof of the strong duality theorem that uses the simplex method is not complete until it has taken a few extra steps. Further, for economists the duality theorem is extremely important whereas the simplex method is not necessarily so. If we add to it the fact, that the simplex method has faster substitutes for computational purpose, an alternative proof of the strong duality theorem which does not use the simplex method would be very welcome. The alternative is to use the Farkas’s lemma or a theorem of alternative than can be derived from it. Such proofs while extremely elegant pre-empt deriving Farkas’s lemma itself from the strong duality theorem of LP. We provide an alternative proof of the strong duality theorem whose main step is a proposition which says that every canonical linear programming minimization problem whose image under its objective function of the set of feasible solutions is non-empty and bounded below has an optimal solution. We also use this proposition to obtain an independent proof of the Farka’s lemma.

Article

Download

View PDF