APM236H1S
Applications of Linear Programming
Spring semester, 2003
Overview:
Introduction to linear programming including a rapid review of linear
algebra (row reduction, linear independence), the simplex method, the
duality theorem, complementary slackness, and the dual simplex
method. 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
Professor: Mary Pugh, mpugh@math. utoronto.ca
Office hours:
Mondays, 2:30-3:30, Tuesdays, 2:30-3:30 (until Tues April 8)
Office location: room 3141, Earth Sciences Centre,
22 Russell Street
TA: Joon Song, song@math. utoronto.ca
Office hours
by appointment: (416) 978-3201 or email.
Office location:
1 Spadina Crescent, room 209.
(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 has a
counselling and learning skills centre.
(Advertisement)
Specific information about the first midterm exam
It will cover chapter 1 of Kolman and Beck.
You should read and understand chapter 0 as well but you won't
be asked "purely linear algebra" questions.
It will be in class on Wednesday February 5. It will be
one hour long, from 6:10 to 7:10.
The first midterm, answer keys, grades
Here is the
yellow term test and its
solution key.
Here is the
white term test and its
solution key.
NOTE! The answer to problem 3 on the white test is wrong. There are three
basic feasible solutions and they are:
(1/3, 5/3, 0, 0, 5/3, 0) and
(1/8, 0, 0, 5/8, 10/8, 0) and
(1/8, 0, 5/64, 0, 85/64, 0).
In problem 4b) for both tests
there are ten integer pairs in the region of
feasible solutions. Seven of them easy to find (one or both components
are zero) and three require either being good with fractions, a calculator, or
plotting carefully on graph paper or with a ruler.
The average on the white test was 55.81 and the standard devation was 16.63. To
compute your post-belled mark, take your score, subtract 55.81, multiply by 10,
divide by 16.63, and add 69. Take the maximum of this number and your original
score. This number is 20% of your course mark.
The average on the yellow test was 56.93 and the standard devation was 13.00. To
compute your post-belled mark, take your score, subtract 56.93, multiply by 10,
divide by 13.00, and add 69. Take the maximum of this number and your original
score. This number is 20% of your course mark.
After belling, the average score is 69 with a standard deviation of 10.
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!
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.
Game theory
Here are the game theory
lecture notes .
Here are some game theory
practice problems for you to work through.
Here are the
solutions to the
practice problems.
One of you found three mistakes in the solutions --- they've been fixed now. If you already downloaded the (old, partially wrong) solutions, print pages 8, 12-16 of the new solutions and replace the respective ones. Also, at the bottom of page 6, correct the last row of the matrix A to be "2 1 0"
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.
Note: 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. I didn't present this
in class or in the notes or in the solutions because we had already
discussed the simplex method at length. 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.
Specific information about the second midterm exam
The test will be cumulative, but will focus on chapter 2 and sections
3.1 to 3.3 of chapter 3. In section 3.3, you need only cover up to and including
the first paragraph on page 197. (I.e., you are not responsible for
the portion of section 3.3 that begins on page 197 with the sentence,
"Now let us consider...")
It will be in class on Wednesday March 19. It will be
one hour long, from 6:10 to 7:10.
The second midterm, answer keys, grades
Here is the
white term test
and its
solution key.
Here is the
green term test
pand its
solution key. There is a mistake in the answer to problem three. The objective
row of the first tableau should be "2 -1 0 1 0 -3" and the objective row
of the second tableau should be "4 0 1 1 0 -2".
The white and green tests were statistically indistinguishable. The average
score was 67.16 and the standard deviation was 19.24.
To
compute your post-belled mark, take your score, subtract 67.16, multiply by 10,
divide by 19.24, and add 69. Take the maximum of this number and your original
test score. This number is 20% of your course mark. (Note to students who had
scores below 50 before the belling --- you need help with this material! Please
come see me or your TA for help. Or find a study buddy and work much harder.)
After belling, the average score is 69 with a standard deviation of 10.
problem set 7: p 325, #8, #10, #11, #12.
Here are the
solutions
to problem set 7.
Old exams for you to use to test your understanding of the material
You can find
old final exams online. Use the "select a department" pulldown menu and
choose "A&S Applied Mathematics". Hit "go". Follow the link "A&S-APM236H".
Also, here are
term tests and final exam from the last time I taught the course.
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.
problem set 8: p 338-9, #1-7.
Here are the
solutions
to problem set 8.
Information about the final exam
Date, Time, Place
The final exam will be on Monday April 28 from 7 pm to 9 pm. It will
be held in "BN2S" (Large Gymnasium, South End, Benson Building, 320
Huron Street (south of Harbord Street), Second Floor)
Final Exam Material
From Kolman & Beck: Chapter 1, Chapter 2, sections 3.1, 3.2, 3.3, 5.1,
and 5.2.
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 hopefully solve)
game theory problems, transportation problems, and
assignment problems.
Extra office hours before final exam
Joon Song will have twenty hours of office hours the week before the
exam. His office is 1 Spadina Crescent, room 209. His office hours will be:
Tuesday Apr 22 9am-1pm,
Wednesday Apr 23 9am-1pm,
Thursday Apr 24 9am-11am and 2pm-4pm,
Friday Apr 25 9am-1pm, and
Monday Apr 28 9am-1pm.
I will have office hours on Monday April 28 1pm-4pm.
Here is the
final exam and here are the
answers
to the final exam.
NOTE: the answer to 3b is incomplete. The only
The only way to know that a basic feasible solution is optimal is to
compute the objective row. Take x_22 entering and x_24
departing, resulting in a basic feasible solution with basic
variables x_11, x_12, x_22, x_23, x_32, and x_34. Solving the dual
problem,
you find:
v1=0, v2=1, v3=3, w1=3, w2=4, w3=4, and w4=1. Using these values
to compute the objective row, you find:
obj_13 = -1, obj_14 = -3, obj_21 = -2, obj_24 = -4, obj_31 = 0, and
obj_33 = -1.
Since the objective row is nonpositive, the basic
feasible solution *is* optimal, as claimed.