This is a home page for a course of 24 lectures to Cambridge MMath/MASt
(Part III) students. It was last given in the autumn of 2010 by me. It will next be given in winter 2012 by Dr Felix Fischer, who will be making some changes to the topics that are covered.
This material is provided for students, supervisors (and others) to
freely use in connection with this course. Copyright remains with the
This course covers a selection of mathematical tools and models for
operational research, in particular, linear
programming, algorithms, and game theory. It does not cover
statistical and stochastic methods, such as queueing theory, or
stochastic dynamic programming, which are also important mathematical
tools in OR. The coverage of each topic (such as linear programming) is
taken to a level beyond that which is commonly found in any
undergratuate course, but stops short of what might be covered in a
course that is wholely devoted to that topic.
The Simplex Algorithm
Advanced Simplex Procedures
Complexity of Algorithms
Computational Complexity of LP
The Network Simplex Algorithm
Transportation and Assignment Problems
Maximum Flow and Shortest Path Problems
Algorithms for Shortest Path Problems
Branch and Bound
Travelling Salesman Problem
Two-person Zero-sum Games
Solution of Two-person Games
Construction of a Nash Equilibrium
Shapley Value and Market Games
Games and Mechanism Design
Please send me email
with comments or corrections on my lectures, the notes or
the examples sheet. I am very glad to receive comments and suggestions
from students studyng the course.
They are mostly complete, but I may make changes at the course
Since the course began this year I
have made some changes to the notes as follows:
Lectures 16-18 (revised 15 Oct 2010).
Lecture 16 (small corrections made in Section 16.4 on 13 Nov 2010)
Lecture 18 (further revised on 17 Nov 2010)
Lecture 18 (corrections to section 18.3 have been made following
lecture on 17 Nov 2010)
Lecture 19 revised 17 Nov 2010 (added sketch proof of Nash's
Lecture 20 corrected a n to 2^n on 4th line of page 82 (Nov 22).
Lectures 22-24 basic outine finalized (Nov 24)
Lecture 23 some improvements were made to pages 92-93 following the lecture, to make some of the ideas a bit clearer.
Lecture 24 some final corrections and improvements were made on 1 Dec.
Some further changes may be made after Lectures 22-24 have been delievered.
Compared to previous years, some topics have be deleted and others
added. So not all past exam questions remain relevant. In particular, I have REMOVED:
Rigorous details for the Ellipsoid Algorithm, some trivial material
about representation of some integer programs, Facility Location
Problem, Joint Maximization of Profits, Evolutionary Games
and analysis of some Stackelberg leadership games. ADDED:
Semi-definite Programming, Primal-Dual Interior Point Algorithm,
Lemke-Howsen Algorithm, Linear Complementarity Problem, and all
material in Lecture 24.
A file of overheads,
some of which I have used in lectures.
Those interested in Semidefinite Programming can read more in Semidefinite Programming, by Vandenberghe and Boyd.
A good program for solving semidefinite programs (and linear programs) using an interior point method is SeDuMi. This is what I used for my numerical research on the Rendezvous Problem.
A LP solver. Simple2x is a small program written to run under Windows
and designed to assist students to learn the simplex algorithm. It
takes the hard labour out of performing pivot operations and it may be
configured to prompt the choice of pivot elements.