Optimization IB 1998
This material is provided for students, supervisors (and others) to
freely use in connection with this course. Copyright remains with the author.
Constraints for problem P
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
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.
To provide this information via this WWW page is an
experiment. I welcome your feedback as to whether it a useful
addition to the lecture course.
Click here to
send me email with comments
or corrections on my lectures, the notes or the examples sheet.
How to view and print:
There are 56 pages of notes available as a postscript file. When you
click on a file name below, the file will appear on your screen to be
viewed with ghostview. You can mark and print the specific pages you
need, rather than waste paper by printing all the pages. Ideally, you
will want to print to a 600 dpi laser printer, but 300 dpi will do.
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.
(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.
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.
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.
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.
Overhead Slides and Digressions
I include a small (non-examinable) digression half way through each lecture.
Topics I have covered are:
These examples and other material are
included in this file of overhead projector slides.
- set partitioning
- job scheduling
- optimal electricity generation and distribution
- insects as optimizers
- project assignment in CUED
- examples of very large LPs
- how large an LP can we solve?
- on-line bin packing
- airline luggage
- MacDiet problem
- hanging chain
- hanging springs puzzle
- string covering (an open problem)
- Braess's paradox
- more examples of very large LPs
- rendezvous problem
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.
This file has exam questions from 1985-1997.
Bazaraa, M., Jarvis, J. and Sherali, H.,
Linear Programming and Network Flows. second edition, 1990, Wiley.
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!)
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.
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
- 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
Notice to external persons accessing this page
Please click here.
Richard Weber ( firstname.lastname@example.org )
Last modified: Mon Apr 27 10:23:58 1998