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.
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.
Spreadsheet programs such as Microsoft Excel also contain LP solvers that are good for up to about 200 variables.
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.University of Cambridge > Mathematics> Statistical Laboratory > Richard Weber > Optimization