ABSTRACT
This chapter shows that each linear programming problem has a special correspondence to another "dual" linear programming problem. It deals with the model stability of a linear programming problem. The chapter presents a new algorithm known as the dual simplex procedure. The complementary slackness theorem is developed, which leads to a reformulation of the linear programming problem as a linear complementarity problem. A method, known as C. E. Lemke's complementary pivoting algorithm, is presented for solving the latter problem. Many dual problems are meaningfully related to the original problem. The duality results can be useful when interpreting the meanings of the dual variables. Duality has an important application concerning the model stability of a linear programming problem. K. Murty also discusses model stability for linear programming problems which possess both equality and inequality constraints, as well as, nonnegative and unrestricted variables.
