Linear Programming means maximizing or minimizing linear functions of variables subject to linear equations or inequalities (so maybe “Linear Optimization” would be a more descriptive name).
- Section: 201
- Classes: Tuesdays and Thursdays 9:30am-11am in MATH 104.
- Office Hours: Mondays 5-6pm, Wednesdays 12-1pm in LSK 300, or by appointment (email me with 340 somewhere in the subject line).
- Special Office Hours during Reading Week: Friday, February 19 from 11am to 12:30pm in LSK 300.
(There is another section, 202, taught by Professor Richard Anstee. You might want to check some of the materials on his course website.)
Assignment 2 (Solutions) is due on Thursday, February 11 at the start of class (ignore the Wednesday due date in the file: that’s for the other section). For problem 2, you will need the final dictionary to your Quiz 2 problem, those are available here.
Each of the following topice will take approximately 2 weeks (the chapters listed are from Chvátal’s book):
- Simplex Method (chapters 1–4 & 8)
- Duality Theory (chapters 5,9)
- Revised Simplex Method (chapters 6,7)
- Sensitivity Analysis (chapter 10)
After that we will have time to cover some additional topics and students can influence the choice:
- Applications and some modelling techniques (chapters 11-14)
- Branch and Bound
- Game theory (chapter 15)
- Non-linear Programming and the Karush-Kuhn-Tucker conditions
- General Upper Bounding (chapter 25)
I recommend Linear Programming by Vašek Chvátal. This text explains the simplex method using the dictionary format that we will use in class.1
I will ocasionally post some supplementary material on this website, too.
- George Dantzig, who invented the Simplex method died May 13, 2005 at age 90. If you’re curious, you can read his obituary.
Supplementary notes written by Prof. Anstee:
- Aviation fuel blending problem.
- Obtaining Standard Inequality form.
- Our first pivoting example.
- An unbounded example (a slide show).
- Overview of Simplex two phase method..
- Pivots preserve the set of solutions, a direct proof.
- Degenerate Pivots, and why not to fear them.
- Chvátal’s example of cycling, which has the virtue of being an exact computation in binary. No numerical errors can result.
- Matrix multiplication. This has a refresher on matrix multiplication.
- Statements of the main theorems.
- Proofs of strong duality and complementary slackness. Also includes the marginal values interpretarion.
- A proof of the theorem of the alternative.
- An example of the Revised Simplex Method.
- The Simplex Method is guaranteed to terminate if you use Bland’s rule.
- Solutions to the midterm.
- Examples of Sensitivity Analysis.
- The trucking company example.
- Branch and bound.
- Cones in Linear Programming.
Several LPs in LINDO format:
Practice questions for quizzes
- Practice for Quiz 1 (Thursday January 14 from 10:25am to the end of class).
- Practice for Quiz 2 (Thursday January 21 from 10:25am to the end of class).
- Practice for Quiz 3 (Thursday February 3 from 10:25am to the end of class).
- Practice for Quiz 4 (Tuesday February 23 from 10:25am to the end of class).
- Practice for Quiz 5 (Thursday March 17 from 10:25am to the end of class).
- Sample midterm. Expect about 70% computation (like the quizzes) and 30% theoretical questions (like the assignments).
Sample final exams
- December 2010 final exam.
- December 2011 final exam.
- Copies of old Math340 from the Math department archives. Note that some of those years the course covered a different selections of topics than we did so some of those final exams might not be as relevant as others (use your judgement and recollection of the course).
On some problems you will be asked to use computer software to solve linear programming problems. I recommend the Classic LINDO application for Microsoft Windows. You can obtain a free evaluation copy from that link to install on your own computer, or use the computer lab in LSK 310. You either should choose a time with no labs or, you can work quietly at the back of the lab even if a lab is scheduled (assuming there are some empty computers). Your ID is the first 8 characters in lower case of your name as recorded first name, middle name (if you have one), final name. The password is set to capital
S followed by the first 7 numbers of your student ID. You can change your password. Access the Windows system and click on LINDO.
You don’t need to use LINDO, specially if you have prior programming experience. Other options include:
scipy.optimize.linprogfunction from SciPy.
The grade will be computed as 55% final; 15% midterm; 30% quizzes and assignments.
Quizzes: These will be mostly computational problems. There will be 5 quizzes of 25 minutes in length. Practice questions will be given in advance.
Assignments: There will be 5 assignments. They will have an emphasis on theory. Some assignments will give computational questions and you will be able to utilize the computer Lab and the LINDO and LINGO software for Linear programming (available in the computer lab in LSK 310; you will be given accounts) or software of your choosing. Students may work together on assignments but must write up their solutions independently. Copying is forbidden. Any 2 (or more) assignments with some virtually identical answers deemed the result of copying will be given 0 total credit. The students are reminded of the plagiarism policies of the University.
Midterm and Final: There will be one hour long midterm, it will be during class on Thursday February 25. The final will be 3 hours long.
Feel free to look at any other comparable text, but beware that the simplex method might look fairly different, even while it performs the same computations.↩