16.6 Review of the course
The course has followed one idea, optimisation under constraints, from its linear core outwards.
Linear programming. The feasible region is a polyhedron and the optimum is at a vertex (the sections on models and geometry); the simplex method walks between vertices, in tableau or revised form (the next two sections); duality supplies certificates of optimality, shadow prices, and sensitivity ranges (the sections on duality and sensitivity).
Structure. Transportation, assignment and network problems have totally unimodular matrices, so their LPs give integer answers and special algorithms are fast (the sections on transportation and networks). General integer programmes need branch and bound and cutting planes; non-linear ones the KKT conditions, which extend duality; and staged problems dynamic programming (the next three sections).
Uncertainty. Decisions under risk use expected values and the value of information; games use minimax, which is LP duality again; inventories, queues and Markov models give formulas for the effect of randomness; and simulation handles what the formulas cannot (the last five sections).
| Problem | Main tool |
| allocate scarce resources | linear programming, duality |
| ship, assign, route, schedule a project | network flows, total unimodularity |
| yes–no decisions, fixed costs | integer programming |
| curved costs, risk | KKT conditions, quadratic programming |
| decisions in stages | dynamic programming |
| uncertain states, opponents | decision trees, minimax |
| stock, waiting lines, deterioration | EOQ, newsvendor, queues, MDPs |
| anything else | simulation |
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.