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)