University of Cambridge >
Mathematics >
Statistical Laboratory >
Richard Weber >
Mathematics of Operational Research

# Mathematics of Operational Research

## Contents

## Lecture Notes

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.

## Supporting materials

## Examples classes

There will be 3 examples classes for this course. These will be
in Room 4 at 4pm on Wednesdays Nov 10, Dec 1 and Jan 19.
## Examples sheets

## Past
Exam Papers

Links to exam papers
since 2001 are: 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001.

Here also is a single file of all these examination papers (1.4Gb)

## Recommended
Books

The principle reference for the course is the set of notes that I have written and which have been the basis for the lectures.

**L.C. Thomas**, *Games,
Theory and Application*, Wiley, Chichester (1984).

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

## Archive

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

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.

- Lagrangian Methods
- Linear Programming
- The Simplex Algorithm
- Advanced Simplex Procedures
- Complexity of Algorithms
- Computational Complexity of LP
- Ellipsoid Method
- The Network Simplex Algorithm
- Transportation and Assignment Problems
- Maximum Flow and Shortest Path Problems
- Algorithms for Shortest Path Problems
- Semidefinite Programming
- Branch and Bound
- Travelling Salesman Problem
- Heuristic Algorithms
- Two-person Zero-sum Games
- Solution of Two-person Games
- Construction of a Nash Equilibrium
- Cooperative Games
- Coalitional Games
- Shapley Value and Market Games
- Auctions
- Auction Design
- Games and Mechanism Design

These are notes for the 2010 course.

2010 Lectures 1-24 in side-by-side A5 format

2010 Lectures 1-24 in full size A4 format

They are mostly complete, but I may make changes at the course progresses.

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 bargaining solution)
- 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.

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.

For **Rendezvous Problem** (Lecture 12) see seminar
Symmetric Rendezvous Search.

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.

Seminar slides on Disputed Garment Problem and Bargaining (used in Lectures 19-21: Cooperative and Coalitional Games)

Section 24.2 is taken from Games and Price Mechanisms for Distributed Control, by Anders Ratzner

Further material related to Section 24.3 can be found in my seminar slides

Incentivizing Participation in Resource-sharing Networks (2007)

I discussed in Lecture 24 pages 29-41 of the above talk - which contain similar content to section 24.3 of the notes.

See also,
Economic Issues in Shared Infrastructures (2009)

Here also is a single file of all these examination papers (1.4Gb)

**M.S. Bazaran, J.J. Harvis and H.D. Shara'i**,*Linear Programming and Network Flows*, Wiley (1988).**Bertsimas and J.N. Tsitsiklis**,*Introduction to Linear Optimization*, Athena Scientific (1997).

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

These are notes for the 2007-09 course:

2007-09 Lectures
1-24 in side-by-side A5 format

Notice
to external persons accessing this page

University
of Cambridge > Mathematics > Statistical
Laboratory > Richard
Weber > Mathematics of Operational Research

Last
modified: 02 December 2010