SchedulesiiiNotationiiiIndexiv 1Preliminaries1 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 2The Solution of LP Problems5 2.1 Basic solutions 5 2.2 Primal-dual relationships 6 3The Simplex Method10 3.1 Preview of the simplex algorithm 10 3.2 The simplex algorithm 12 4The Simplex Tableau14 4.1 Choice of pivot 14 4.2 Initialization: the two-phase method 15 4.3 Sensitivity: shadow prices 17 5Lagrangian Methods19 5.1 The Lagrangian 19 5.2 The Lagrangian sufficiency theorem 20 5.3 Strategy to solve problems with the Lagrangian sufficiency theorem 21 6The Lagrangian Dual23 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 7Shadow Prices and Lagrangian Necessity27 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 8Algebra of Linear Programming31 8.1 Basic feasible solutions and extreme points 31 8.2 Algebra of the simplex method 34 9Two Person Zero-Sum Games36 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 10Maximal Flow in a Network40 10.1 Max-flow/min-cut theory 40 10.2 Ford-Fulkerson algorithm 42 10.3 Minimal cost circulations 43 11Minimum Cost Circulation Problems44 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 12Transportation and Transshipment Problems48 12.1 The transportation algorithm 48 12.2 *Simplex-on-a-graph* 51 12.3 Example: optimal power generation and distribution 52