Optimization IB
1998

This is home page for a course of 12 lectures to first and second year Cambridge mathematics students in spring 1998.

Lectures are M,W,F at 11am in the Cockcroft Lecture Theatre.

Each lecture is as self-contained as possible and has course notes amounting to four or five A4 pages. Click here for the table of contents.

I have also made additional notes about things I said in lectures and questions students have asked.

There is a single examples sheet and a file of exam questions. Students should receive two supervisions on the examples sheet. There are two recommended books. If you enjoy this course then you should consider related courses in Part II and other items of interest.

Feedback

Click here to send me email with comments or corrections on my lectures, the notes or the examples sheet.

Course notes

The notes are formatted as two side-by-side pages per A4 sheet. So to view the notes properly you may need to go to the ghostview menus and set the display for A4 paper in landscape mode. Each lecture begins on a new page.

There are individual files for each lecture. This may be more convenient for you if you do not have the ability to run ghostscript from your computer, but are able to print a postscript file.

Each of these files is about 300Kb in size.

• toc.ps, L01.ps, L02.ps, L03.ps, L04.ps, L05.ps, L06.ps, L07.ps, L08.ps, L09.ps, L10.ps, L11.ps, L12.ps.

• notes.ps (119K) has all the above in a single file

• notes.ps.gz (443K), notes.zip (221K): compressed versions (use gunzip or unzip or pkunzip to decompress)

Some people like to print copies of the notes in non-reduced form, i.e., one page per A4 page. You can download these here.

• A00.ps, A01.ps, A02.ps, A03.ps, A04.ps, A05.ps, A06.ps, A07.ps, A08.ps, A09.ps, A10.ps, A11.ps, A12.ps.

Some people want the notes as a .dvi file. These are here in full page form. However they do not include diagrams, since these are added only when the .dvi file is converted to postscript.

• notes.dvi (222K)

Corrections: Whenever I find an error in the notes the files above are corrected and a note is added to this list of corrections.

Where to collect photocopies of the notes: You can find copies of notes by using this map to locate the Statistical Laboratory pigeonholes.

Examples sheet

There is a single examples sheet, available as a postscript file of 6 pages. The topics that the questions cover appear in the same order as topics are covered in lectures and you will find a recommendation on the sheet concerning the work you should do for your supervisions. Viewing and printing is identical as for the notes above.
• exsheet.ps (417K)

Corrections:

Overhead Slides and Digressions

I include a small (non-examinable) digression half way through each lecture.

Topics I have covered are:

1. set partitioning
2. job scheduling
3. optimal electricity generation and distribution
4. insects as optimizers
5. project assignment in CUED
6. examples of very large LPs
7. how large an LP can we solve?
8. on-line bin packing
9. airline luggage
10. MacDiet problem
11. hanging chain
12. hanging springs puzzle
13. string covering (an open problem)
14. Braess's paradox
15. more examples of very large LPs
16. rendezvous problem
These examples and other material are included in this file of overhead projector slides.
• oheads.ps (610K), oheads.ps.gz (123K).

Additional material

Here are some additional notes which summarise things I said in lectures and which do not appear in the printed notes. I have also made notes about questions that students asked, either in lectures or by coming up to me afterwards.

Exam questions

This file has exam questions from 1985-1997.

• tripos.ps (357K)

Recommended books

1. Bazaraa, M., Jarvis, J. and Sherali, H., Linear Programming and Network Flows. second edition, 1990, Wiley.
2. Luenberger, D., Introduction to Linear and Non-Linear Programmings, second edition, 1984, Addison-Wesley.

Related courses in Part II

There are two courses in Part II that build on what students learn in this course. In Part IIA there is Algorithms and Networks. In Part IIB there is Optimization and Control.

Other items of interest

• A Pascal program implementing the simplex algorithm.

• 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 like Microsoft Excel and Quattro Pro also contain LP solvers that are good for up to about 200 variables.

• A neat interactive LP solver on the Web. Enter your data and it sends back the answer. (Good for checking you have the right answers to examples sheet questions!)

• An interactive diet solver that will find your "optimal" diet based on a list of foods you tell it you are willing to eat.

  The goal of the diet problem is to find the cheapest combination of foods that will satisfy all the daily nutritional requirements of a person. The problem is formulated as a linear program where the objective is to minimize cost and meet constraints which require that nutritional needs be satisfied. We include constraints that regulate the number of calories and amounts of vitamins, minerals, fats, sodium and cholesterol in the diet. The mathematical formulation is simple, but you will find out by running the model that people do not actually choose their menus by solving this model. 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 Guide to Optimization including an overview of optimization, case studies, test problems, and much, much more. Well worth looking at!
• If you are interested in learning about modern interior point methods for solving LP problems, read here.
• Here are some biographical notes about George Dantzig, the originator of the simplex method, on the occasion of his 80th birthday.

• Here is what the Occupational Outlook Handbook says about careers in operations research.
• Here are some pointers to files of frequently asked questions on the internet about Linear Programming and Non-linear Programming.

• miscellaneous things in OR/probability/statistics that I find amusing.

• A two-person, zero-sum repeated game, demonstrating paradoxical effects due to giving or not giving away information.

• Sex difference in use of computer-based teaching resources.
  Some people have suggested that male and female students may differ in their use of computer-based teaching material. A preliminary finding for pre-university students is that females actually read the information and use it, whereas males are often content merely to revel in the process of locating and downloading the data. This issue was explored by a questionnaire survey.ps of students during the sixth lecture in 1995. The results.ps are quite interesting. You may like to read the article in the Times Education Supplement by Angela MacFarlane which discusses these issues.
• My current favorite music CD is still Reactivate 10.

Notice to external persons accessing this page

Please click here.

home page

---

Richard Weber ( r.r.weber@statslab.cam.ac.uk )

Last modified: Mon Apr 27 10:23:58 1998