APM236H1
Applications of Linear Programming
Spring semester, 2002

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: the revised simplex method, sensitivity analysis, integer programming, the transportation algorithm.

Exclusion: APM261H, ECO331H

Prerequisite: MAT223H/240H (Note: no waivers of prerequisites will be granted)

Course Outline: information about quizzes, tests, and and homework

Office hours: Apr 30: 12-1, May 1: 11-1
Office location: SS 4058
email address: mpugh@math. toronto.edu

TA for the course: Joon Song, song@math. toronto.edu, (416) 978-3201. His office hour is on Tuesdays 10-11 in 1 Spadina Circle, room 209. (You know the building in the circle that interrupts Spadina between College and Harbord? His office is in that building.)

General information about the midterm exams The midterms will be one hour long and held in class starting at 6:10. The first midterm will be on February 6 and the second one will be on March 20.

Specific information about the first midterm exam The first midterm will cover all of chapters 0 and 1.

Here is the blue/yellow test. Here is the the answer key. Here is the white/green test. Here is the answer key.

The midterm grades are ready. Please excuse my slowness in getting them done. You can pick up your exam in class or at my office hours. If you are very curious, send me email. The class average was 22. The grade distribution is: 0-9 = F, 10-13 = D, 14-16 = C-, 17-18 = C, 19-20 = C+, 21-23 = B-, 24-26 = B, 27-28 = B+, 29-30 = A-, 31-33 = A, 34-35 = A+. In terms of percentages: A's = 21%, B's = 39%, C's = 28%, D's = 6%, F's = 6%.

Here is how to find your "mark" on the first midterm. First you have to compute two numbers. For the first number, take the points you got on the exam and multiply it by 1.5102. Now add 37.8107. For the second number, take the points you got on the exam and multiply by 100/35. Your mark is the maximum of these two numbers. For example, if you got 12 points then your mark is 55.9 (the maximum of 55.9 and 34.3). There is one exception to this rule: if you got 14 points then your mark is 60.

Matlab routines for the simplex method Here are the routines I used in class on Wednesday Feb 27, 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. There's a starter example in which a simple example is solved and a more advanced example in which the two-phase method is needed. Both files start with a quick lesson on where to save the files and how to use them.

Here is the diary of what I did in class. It includes information on how to start phase 2 once you've finished phase 1. In class, I just said "do Gaussian elimination and you'll get... Here're the details.

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!

Specific information about the second midterm exam The second midterm will be in class on March 20. It will cover everything up to and including section 3.3, but will focus on chapter 2 and sections 3.1-3.3. This includes section 2.2 even though the author of the book marked that as "optional". You will not be tested on the "big M method" (pp 147-150). Section 3.2 has five theorems and their proofs. You will not be tested on the proofs of theorems 3.7 and 3.8. But you should understand the proofs of theorems 3.4, 3.5, and 3.6. Also, you should understand the ramifications of all five theorems even if you can't prove them.

Here is the the yellow test. Here is the answer key.
Note The answer in #5 has a mistake in it. The "-2/5" in the objective row should be "-3/5".
Also, the full answer to #6b is as follows:
For the incoming variable x1, the candidates for exiting variables are x3, x2, x5, and x8. x2 and x8 are excluded because they'll never exit as you increase x1 (since the coeffecients in the matrix aren't positive). x3 is excluded because by the time it exits, x5 will have already exited. (The theta ratio for x3 is 2, while it's 1 for x5.) So the only possible exiting variable is x5.
For the incoming variable x4, the candidates for exiting variables are x3, x2, x5, and x8. x3 and x5 are excluded because they'll never exit as you increase x4 (since the coeffecients in the matrix aren't positive). x2 and x8 have equal theta ratios (they're both zero) so they're both legitimate choices for exiting variables.
For the incoming variable x6, the candidates for exiting variables are x3, x2, x5, and x8. x2 and x8 are excluded because they'll never exit as you increase x6 (since the coeffecients in the matrix aren't positive). x3 and x5 have equal theta ratios (they're both 1/3) so they're both legitimate choices for exiting variables.
For the incoming variable x7, the candidates for exiting variables are x3, x2, x5, and x8. x3, x2, and x5 are excluded because they'll never exit as you increase x7 (since the coeffecients in the matrix aren't positive). x8 is the only one left and is a legitimate choice for an exiting variable.

Here is the white test. Here is the answer key. Please see above for what a full answer to 6b would look like.

The second midterm is graded. You can pick up your exam in class or at my office hours. If you are very curious, send me email. The class average was 36. The grade distribution is: 0-9 = F, 10-19 = D, 20-24 = C-, 25-29 = C, 30-33 = C+, 34-36 = B-, 37-38 = B, 39-40 = B+, 41-43 = A-, 44-46 = A, 47-48 = A+. In terms of percentages: A's = 23%, B's = 42%, C's = 33%, D's = 2%, F's = 0%.

Here is how to find your "mark" on the second midterm. First you have to compute two numbers. For the first number, take the points you got on the exam and multiply it by 1.1024. Now add 35.0602. For the second number, take the points you got on the exam and multiply by 100/48. Your mark is the maximum of these two numbers. For example, if you got 39 points then your mark is 81.3 (the maximum of 78.1 and 81.3). There is one exception to this rule: if you got 21 points then your mark is 60.

Matlab routines for using the simplex method on the transport problem Here are the matlab subroutines I used in class on Wednesday April 3, along with a quick lesson on how to use them. You need to save the three *.m files: pivot_transport.m, LP_setup_transport.m, and LP_disp_transport.m. Please look at the beginning of this file to see where to save them. Here is the diary of how to use them and what I did in class.

We finished section 3.3 on March 13. On March 27, we will start section 5.1 and will spend the last three lectures (3/27, 4/3, and 4/10) covering sections 5.1-5.2, as well as discussing additional aspects of transportation and assignment problems.

an obfuscation in the book On page 297, the authors write "We will say the model is infeasible if demand exceeds supply". In fact, the problem can still be solved (see excercise 13, just use the same idea as if supply exceeds demand).

What if demand exceeds supply, like in problem 13? See my notes for a discussion of the situation, as well as some exercises for you to do.

What will the final exam cover? It will cover everything in the textbook up to and including section 3.3, as well as sections 5.1 and 5.2, and any material covered in the lectures. This means you will be responsible for material in section 2.2 (the author may consider it "optional," but this course does not). You will not be tested on the "big M method" (pp 147-150). In section 3.2, there are five theorems and their proofs; you will not be tested on the proofs of theorems 3.7 and 3.8, but you should understand the proofs of theorems 3.4, 3.5 and 3.6. (You should understand the ramifications of all five theorems, even if you can't do the proofs.) As for the lecture material, not all of it is in the book. If you missed classes, consider borrowing notes from a classmate.

Old exams for you to use to test your understanding of the material You can find old exams online. Use the "select a department" pulldown menu and choose "A&S Applied Mathematics". Hit "go". There are three links that lead to exams: APM236F, APM236H, and APM236S.

Information about the final exam The final exam will be on Wednesday May 1 from 7 to 9 pm. It will be held in the south end of the varsity arena: 275 Bloor street west, first floor.

New!!
Your course marks The final exam had an average of 51 and standard deviation of 14.5. I belled the exam to have an average of 69 and standard deviation of 10. (The number 69 was chosen by looking at the average course marks from the previous six times the course was taught: it is the average average course mark.) I then used your belled exam score to compute your grade: 60% final exam, 20% first midterm, 20% second midterm.

If you look only at the course marks of the students who showed up to the final, the average course mark is 71. If you include the five students who didn't show up to the exam but were registered for the course, the average course mark is 69. A's: 17%, B's: 32%, C's: 41%, D's: 3%, F's: 8%.

If you are curious to find out your exam grade and your course mark, send me email.

Here is the final exam. Here is the answer key. NOTE: there are some mistakes in the answer to problem #2. Specifically, on page 7, the objective function should be "1/2 x2 - 7". The objective row of the tableau with basic variables x3, x1, and x5 should be "0 -1/2 0 0 0 -7". On page 8, the objective row of the tableau with basic variables x2, x1, and x5 should be "0 0 1 -1 0 -6". The objective function can still go to infinity --- there is on optimal solution.