Instructor: Nguyen Lam nlam "at" math "dot" ubc "dot" ca
Office Hours: (Please check back often for updates) at LSK 300C + Mon 12:40pm1:30pm + Tue 11am11:50am + Thu 11am11:50am + by appointment
TEXT: Linear Programming by Vasek Chvatal. The textbook is short of examples and is rather dense for novices but it has made the excellent choice of the dictionary format. I will be posting a significant amount of material on the web to supplement the text. The ‘extra’ chapters beyond the basics (Chapter 11 on) make good reading. It is a superb reference although not always the perfect text.
+ Another good reference is Linear Programming by Robert Vanderbei (electronic copy available to download through the UBC library!). Nearly any book on linear programming will cover the main topics below, but the notation used for the simplex method may be quite different (and take some effort to translate to the notation we'll use).
OUTLINE:
This course would be more properly called Linear Optimization, optimizing a linear objective function subject to linear constraints. The word 'programming' is not used in the sense of computer programming. My best reading of Dantzig's description of the term is that the word programming refers to the program of activities given by a solution. There will be no computer programming in this course although for certain assignments you will be asked to use LINDO, a fairly user friendly software package for Linear Programming.
The basic course material will be covered in about 9 weeks allowing 3 weeks to do applications and a topic of students choice (Game Theory? KarushKuhnTucker conditions useful in Economics and NonLinear Optimization? More Applications?)
+ Simplex Method (chapters 14, 8): 2 weeks
+ Duality Theory (chapters 5, 9): 2 weeks
+ Revised Simplex Method (chapters 6, 7): 2 weeks
+ Sensitivity Analysis (chapter 10): 2 weeks
+ Optional topics: (note: students can influence the choice of topics) Applications and some modelling techniques (chapters 1114), Branch and Bound, Game theory (chapter 15), Nonlinear Programming and the KarushKuhnTucker conditions, General Upper Bounding (chapter 25): 3 weeks
GRADING: The grade will be computed as 55% final; 15% midterm; 30% quizzes and assignments.
QUIZZES: Emphasis on computational problems. There will be 5 quizzes. They will be 25 minutes in length. Practice questions will be given in advance. Students, at the beginning of term, can opt out of quizzes if they wish and grades will be computed accordingly.
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. NOTE: You can get your Quizzes and Assignments back from the MLC (Math Learning Center)
MIDTERM: In class, scheduled for Thursday Feb 15
FINAL: 3 hours.
MISSED WORK: From time to time students may be unable to finish assignments or attend midterms or the final exam. In the case of the Final Exam, the students should contact the Faculty of Science office and the missed final will be handled in a formal way. In the case of assignments,please contact me before class time on the due date, and given your reasons for the missed work. Assuming the reasons are legitimate, I will note that you will be missing the assignment. A missed midterm/quiz can be handled in a similar way, if you contact me before the test time. In such circumstances your grade is computed out of a smaller number than 100 and then scaled appropriately to get a grade out of 100. For example, if a midterm counts 15% and a student informs me in advance of legitimate reasons for missing the midterm, the student would have a grade computed out of 85 and then this would be scaled to a grade out of 100 by multiplying by 100/85. Without advance notice (to me by email or phone message to Math Office etc) the default will be a grade of 0 in the missed work but you may contact me. A student must finish a significant amount of term work in order to pass.
Course Material
Computer Software:
+ 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.
+ There is a computer lab in LSK 310 (and maybe LSK 121) (LSK is the Klinck Building) whose doors are open at various hours during the day. You either should choose a time with no labs or, because we are fairly far through the term, you could 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. You want to 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:

Teaching >