Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs

Abstract

This paper presents a new derivation of the key ideas of Dantzig's simplex algorithm by using the differential approach to nonlinear programming. Specifically, the necessary condition shows that a candidate for the optimum is a basic feasible solution, while the sufficiency condition indicates that the optimality indicator ( c j − z j ) for nonbasic variables x j must be nonpositive (nonnegative) in order for a maximization (minimization) linear program to be optimal.