Schedules iii Notation iii Index iv 1 Preliminaries 1 1.1 Optimization under constraint 1 1.2 Representation of constraints 1 1.3 Geometry of linear programming 2 1.4 Extreme points and optimality 3 1.5 *Efficiency of algorithms* 4 2 The Solution of LP Problems 5 2.1 Basic solutions 5 2.2 Primal-dual relationships 6 3 The Simplex Method 10 3.1 Preview of the simplex algorithm 10 3.2 The simplex algorithm 12 4 The Simplex Tableau 14 4.1 Choice of pivot 14 4.2 Initialization: the two-phase method 15 4.3 Sensitivity: shadow prices 17 5 Lagrangian Methods 19 5.1 The Lagrangian 19 5.2 The Lagrangian sufficiency theorem 20 5.3 Strategy to solve problems with the Lagrangian sufficiency theorem 21 6 The Lagrangian Dual 23 6.1 Example: further use of the Lagrangian sufficiency theorem 23 6.2 The Lagrangian dual problem 24 6.3 The dual problem for LP 25 6.4 The weak duality theorem in the case of LP 26 7 Shadow Prices and Lagrangian Necessity 27 7.1 Sufficient conditions for optimality 27 7.2 Shadow prices 27 7.3 Lagrangian necessity 29 7.4 Convexity of the feasible set in the case of LP 30 8 Algebra of Linear Programming 31 8.1 Basic feasible solutions and extreme points 31 8.2 Algebra of the simplex method 34 9 Two Person Zero-Sum Games 36 9.1 Games with a saddle-point 36 9.2 Example: Two-finger Morra, a game without a saddle-point 37 9.3 Determination of an optimal strategy 37 9.4 Example: Colonel Blotto 39 10 Maximal Flow in a Network 40 10.1 Max-flow/min-cut theory 40 10.2 Ford-Fulkerson algorithm 42 10.3 Minimal cost circulations 43 11 Minimum Cost Circulation Problems 44 11.1 Sufficient conditions for a minimal cost circulation 44 11.2 Max-flow as a minimum cost circulation problem 45 11.3 The transportation problem 46 12 Transportation and Transshipment Problems 48 12.1 The transportation algorithm 48 12.2 *Simplex-on-a-graph* 51 12.3 Example: optimal power generation and distribution 52