Optimization IB

# Optimization IB

```   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
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.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
```