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: Tuesdays and Thursdays 11am-12pm in LSK 300, or by appointment (email me with 340 somewhere in the subject line).
(There is another section, 202, taught by Professor Richard Anstee. You might want to check some of the materials on his course website.)
Assignment 1 is due on Thursday, January 28 at the start of class.
Assignment 2 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).
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.
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)
- 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:
An unbounded example (a slide show).
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.
Proofs of strong duality and complementary slackness. Also includes the marginal values interpretarion.
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).
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.↩