Linear ProgrammingFormulation of linear programming; the simplex method; geometry of the simplex method; duality in linear programming; revised (primal) simplex method; the dual simplex method; numerically stable forms of the simplex method; parametric linear programs; sensitivity analysis; degeneracy in linear programming; bounded-variable linear programs; the decomposition principle of linear programming; the transportation problem; computational complexity of the simplex algorithm; the ellipsoid method; iterative methods for linear inequalities and linear programs; vector minima. |
Contents
Formulation of Linear Programs | 1 |
The Simplex Method | 52 |
Geometry of the Simplex Method | 91 |
Copyright | |
18 other sections not shown
Common terms and phrases
affine functions artificial variables b₁ basic cell basic set basic solution basic variable BFSS bounded canonical tableau column vector computational Consider the LP convex convex combination corresponding criterion denote dropping variable dual feasible dual problem dual simplex algorithm ellipsoid method entering variable entries equality constraints equations Example feasible basic vector feasible basis Hence inequality constraints infeasible integer inverse tableau lexico linear programming linearly independent matrix of order Minimize Subject minimum ratio nonbasic variable nondegenerate nonnegative nonzero objective function obtained optimal optimum basis optimum feasible solution optimum objective value optimum solution original problem original tableau parameter Phase I problem pivot column pivot row pivot step primal feasible relative cost coefficient right-hand-side constants row vector satisfying set of feasible simplex algorithm simplex method slack variables solving subset Suppose system of linear termination theorem tion transportation problem unbounded zero