Optimization IB
1997

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

Lectures are M,W,F at 11am in the Cockcroft Lecture Theatre, beginning April 25 and ending 21 May.

The course is very similar to the 1996 course, and the 1996 home page remains in existence for the use of students who did the course then.

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.

There is a preliminary home page for Statistics IB, which I shall be lecturing next year. If you have any suggestions for this course, please let me know.

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 8-12Kb 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 (60K) has all the above in a single file

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

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

• exsheet.ps

Corrections:

Overhead Slides and Digressions

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

1. optimal coding
2. option pricing

• oheads.ps (60K), oheads.ps.gz (12K).

Exam questions

Here is a file of past exam questions. Presently this file has 33 questions in total (from 1985-1996).

• tripos.ps (175K)

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.

• 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

home page