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.