Optimization
A graphical representation of a linear program
This is web page for a course of 12 lectures to first and second year Cambridge mathematics students in the Easter Term 2010.
This material is provided for students, supervisors (and others) to freely use in connection with this course. Copyright remains with the author.
Notes and examples sheets
Course notes (A4 size)
also available in 2 per page size
Examples sheet 1
Note. Students find question 5 to be the most difficult. For further practice on this type of question look at tripos 2007, Paper 3, 20.
Note. Pedacologically the questions on Example Sheet 2 would be better arranged in a different order. I suggest 12 before 11 (since the way you are guided to the answer in 12 will help you to see how to do 11). Also do 15 last. The assignment problem in 15 is a special case of both 14 and 16. It is harder than 14 or 16 because of degeneracy. Unlike 14 (minimum cost circulation problem) and 16 (transportation problem) the node numbers (dual variables) are not uniquely determined up to an additive constant, but must be found from a set of inequalities to which there are many solutions. (This comment added 27 Oct 2011).
Overheads (A4 size, used in lectures for illustrations of examples and digressions) 4 per page
Other lecturers have also given this course and have nice notes and resources
available. See, Dr Tehranchi's optimization page
(and in particular, look at his Ford-Fulkerson and Transportation Algorithm slideshows) and
Dr Kennedy's optimization page.
Recommended books
- Bazaraa, M., Jarvis, J. and Sherali, H. Linear Programming and Network Flows, fourth edition, 2010, Wiley.
- Luenberger, D., Introduction to Linear and Non-Linear Programming, second edition, 1984, Addison-Wesley.
- Vanderbei, R. J., Linear programming: foundations and extensions, 2001, Kluwer. See related lecture notes and materials.
Exam questions
Here is single file of all Tripos questions on Optimization for the years 2001 to present.Other items of interest
- Simple2x is
a small program written by Doug Kennedy 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, to set up Phase I
etc., or to solve problems automatically. I recommend it.
Download it here (right click. save as).
- An executable program lp_solve
that you can easily run on a PC under DOS to compute the solution to
linear programming problems and integer linear programming problems.
Click here
for an explanation of how to use the program and instructions on downloading it to your
computer.
Spreadsheet programs such as Microsoft Excel also contain LP solvers that are good for up to about 200 variables.
- The diet problem is one of the first optimization problems to be studied back in the 1930's and
40's. It was first motivated by the Army's desire to meet the
nutritional requirements of the field GI's while minimizing the cost.
Read more about the amusing history
of the diet problem.
- NEOS wiki - an online source for optimization including an
overview of optimization, case studies, test problems, and much, much
more.
- Here is the Wikipedia entry about George Dantzig, the originator of the simplex method.
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.
This material is provided for students, supervisors (and others) to freely use in connection with this course. Copyright remains with the author.
University of Cambridge > Mathematics> Statistical Laboratory > Richard Weber > OptimizationRichard Weber ( rrw1@cam.ac.uk )
Last modified: 16 April 2010