Synopsis for Optimisation

Overview

Linear programming is about making the most of limited resources: it deals with maximising a linear function of real variables subject to linear constraints. Applications range from planning and production to networks and nutrition, and the theory underlies much of combinatorial optimisation. The aim is to provide a simple introduction to the subject.

Learning Outcomes

Students should have an appreciation of the uses of linear programmes, and an understanding of how to solve them using the simplex method. They should understand linear programming duality and corresponding economic interpretations. They should understand the fundamentals of two-person zero-sum games.

Synopsis

Linear programming problems, convexity, extreme points and basic feasible solutions.

The simplex method (excluding procedures to cope with degeneracy), the two-phase method.

The dual problem, duality theorem (proof by analysing the simplex method), complementary slackness. Economic interpretation of dual variables, sensitivity analysis.

Two-person zero-sum games.

1. V. Chvatal, Linear Programming (Freeman, 1983), Chapters 1–5, 15.

Alternative Reading

1. K. Trustrum, Linear Programming (RKP, 1971). Out of print but available in college libraries. Chapters 1–5
2. D. G. Luenberger, Linear and Nonlinear Programming (Addison- Wesley, 1984) Chapters 2–4.