APM236H1S
Applications of Linear Programming
Spring semester, 2004
Overview:
Introduction to linear programming including a rapid review of linear
algebra (row reduction, linear independence), the simplex method, the
duality theorem, and complementary slackness.
A selection of the following topics are covered: matrix games,
the transportation problem, the assignment problem, the maximal flow
problem, the shortest route problem, the critical path method.
Exclusion: APM261H, ECO331H
Prerequisite: MAT223H/240H (Note: no waivers of prerequisites will be
granted)
Course Outline:
information about tests and homework.
I've taught this course twice before. Here are the course webpages for
Spring 2002
and
Spring 2003
in case you find them of use.
Professor: Mary Pugh, mpugh@math. utoronto.ca
Office hours:
by appointment
Office location: room 3141, Earth Sciences Centre,
22 Russell Street
If you're going to send me email, please include "apm236" in the
subject line. Otherwise, there's a good chance my spam filter
will filter your email.
TA: Oliver Chen, ochen@math. utoronto.ca
Office hours: by appointment. Please email.
Dates of term tests
The first term
test
will be on Wednesday February 4 starting at 6:10, ending at 7:00. The second term test will be on
Wednesday March 10 starting at 6:10, ending at 7:00.
Information about first term test
The first term test will be on Wednesday February 4 starting at 6:10
and ending at 7:00. It will be held in our regular classroom. It
will cover all of Chapter 1; this includes the lecture of Wednesday
January 28. If you have any questions on the material, please email
me or come to my office hours (Tuesdays 4-6) or make an appointment
with your TA (see above).
First term tests from previous years:
You can find the term tests from 2002
here
and the term tests from 2003
here.
First Term Test Results
Here is the
yellow term test
and here is
its answer key.
Here is the
white term test
and here is
its answer key.
The average on the test was 57.63 and the standard deviation
was 15.86. I belled the exam to have an average of 69 with a standard
deviation of 10.
To determine your term test score on this test, do the following. If
you earned x
points on the test, let y = 32.67 + 0.6305*x. Your term test score is the maximum
of x and y. For example, if x = 65 then y = 73.65 and the term test
score is 73.65. This number will be 25% of your course mark.
Degenerate basic variables and Bland's rule Here are
two examples
of when Bland's rule is needed and how to use it.
Matlab routines for the simplex method
Familiar with matlab?
Here are some routines I wrote
along with a quick lesson on how to use them. You need to save
the three *.m files:
pivot.m,
LP_setup.m, and
LP_disp.m. Please look at the beginning of the
quick lesson to see where to save them and how to use them.
Also,
here is a matlab
diary
from a class last year. It includes an example of cycling,
an example showing how to start
phase 2 once you've finished phase 1, and an example where phase
2 doesn't terminate "properly".
If you don't have matlab, here is a free software which is very
very very similar to matlab:
octave by gnu.
A mistake in the book At the bottom of page 141, the righthand
side of the third equation should be 24, not 12. Thus making the third
equation consistent with the third row of Tableau 2.31.
In general, if you find mistakes in the book, please let me know!
Another mistake in the book On page 145, it's written "minimize
z' = y_1 + y_2 + y_3". It should be maximize, not minimize.
In general, if you find mistakes in the book, please let me know!
Information about second term test
The second term test will be on Wednesday March 10 starting at 6:10
and ending at 7:00. It will be held in our regular classroom. It
will cover all of Chapter 2.
Note: you're
not responsible for the Big-M method of pp 147-150.
If you have any questions on the material, please email
me or come to my office hours (Tuesdays 4-6) or make an appointment
with your TA (see above).
Second term tests from previous years:
You can find the term tests from 2002
here
and from 2003
here.
Second Term Test Results
Here is the
white term test
and here is
its answer key.
Here is the
yellow term test
and here is
its answer key.
The average on the test was 60.3 and the standard deviation was 20.2.
I belled the exam to have an average of 69 with a standard deviation
of 12. To determine your term test score on this test, do
the following. If you earned x points on the test, let y = 38.13 +
0.4953*x. Your term test score is the maximum of x and y. For
example, if x = 65 then y = 70.32 and the term test score is 70.32.
This number will be 25% of your course mark.
Game theory
Here are the game theory
lecture notes from class on Wednesday March 24, 2004
and March 31, 2004.
If you downloaded the notes before 6:30 pm on April 5, then you need
to download new versions of pages 21-24a.
Here are some game theory
practice problems for you to work through.
Here are the
solutions to the
practice problems.
For more problems and explanations, see chapter 5 of J.K. Strayer's
Linear Programming and its Applications and chapters 1 and 2 of
M. Drescher's The Mathematics of Games of Strategy. I've put
both books on reserve in the MathStat library in the basement of
Sidney Smith Hall. Its hours are M-F 9-5. Note: Strayer uses
Tucker tableaux rather than Dantzig tableaux in the simplex method, so
it's a little confusing to translate his tableaux to the ones you're
used to. Also, Drescher presents a way to solve these problems which
is basically the simplex method in disguise. Don't learn Drescher or
Strayer's versions of the simplex method, just look at them for games
and how to construct payoff matrices. Once you've constructed the
payoff matrix, you can do your usual method of removing the dominating
columns and rows and then applying the simplex method.
Also,
here
is a
website
that will solve the problem for you once you
have the pay-off matrix. Pity you can't bring the web into your
final exam! :-)
And here are two nice websites about the Prisoner's Dilemma:
site 1, and
site 2.
In your game theory notes and answer key, you simply declare the optimal
solution! How did you find it?
For the game theory the
hard part is finding the linear programming problem to solve.
Then you use your old friend the simplex method to solve it. Once
you've found an optimal strategy for the row player, you can use
complementary slackness to find an optimal strategy for the
column player. In general,
if your pay-off matrix has m rows then to find the optimal
strategy for the row player, you will have m inequalities and 1
equality. You'll have to introduce m slack variables and 1 artificial
variable. Also, since the variable u is unconstrained, you have to
write u = u1-u2. You are now in a position to apply the simplex
method. You have to do phase 1 and then phase 2 to find the optimal
solution.
Rock, Paper, Scissors This is a classic example of the type
of game theory problem we can analyse.
Need some practice? Here's
a
computer you can play against. Also, here's the
World Rock Paper Scissors Society.
Supply not equal to demand?
What happens when total supply is less than total demand in the
transport problem? See my
notes for a discussion of the situation, as well as some
exercises for you to do.
Information about the Final Exam
Date, Time, Place Your final exam will be held on Monday
April 26, from 7:00 pm to 9:00 pm. It will be in the third floor gym
of the Benson building. 320 Huron Street, on the southwest corner of
Huron and Harbord.
Final Exam Material
From Kolman & Beck: Chapter 1, Chapter 2, sections 3.1, 3.2, 3.3, and 5.1.
Also, you're responsible for the game theory we did
on zero-sum matrix games.
In section 3.3, you need only cover up to and including
the first paragraph on page 197. You are not responsible for
the portion that begins on page 197 with the sentence,
"Now let us consider..." and ends on page 201. Also, you're
not responsible for the Big-M method of pp 147-150.
You will not be able to pass the final exam if you
can't
set up and solve
game theory problems and transportation problems.
Also, you should understand that all the theorems in section 3.2
apply to primal/dual pairs where one of the problems is in standard form.
If you want to apply the ideas of section 3.2 to a primal/dual pair that
is not of this form (e.g. many of the examples in section 3.1) then you
have to relate the given primal/dual pair to a related
primal/dual pair for which the theory of section 3.2 applies.
For more information, click
here.
Since section 3.2 is only for primal/dual pairs
where one of the problems is in standard form, it's what you have to
do. Please note that in previous years I wasn't especially rigorous
in grading the complementary slackness problems. But this year I've
been careful in class and in class notes and am being careful above.
So don't hold the previous years' solutions as full, correct
solutions.
Extra office hours
Oliver Chen will be holding thirty hours of office hours before the final
exam. They will be in Sid Smith 1091.
If you cannot come during those hours, then you
may be able to arrange extra hours by email.
Mon., Apr. 19: 12:30pm - 4:30pm
Tue., Apr. 20: 12:30pm - 4:30pm
Wed., Apr. 21: 9am - 1pm
Thu., Apr. 22: 12:30pm - 4:30pm
Fri., Apr. 23: 10am - 1pm; 2pm - 5pm
Mon., Apr. 26: 10am - 1pm; 2pm - 7pm
(Advertisement)
If test-taking generally makes you nervous, have a look at the
test-taking brochure from the University of Illinois at
Urbana-Champaign. They also have brochures on
other aspects of student life
--- have a look --- they're soundly written.
For something more than brochures, the University of Toronto has a
counselling and learning skills centre.
(Advertisement)