Teaching‎ > ‎

MATH 340 Introduction to Linear Programming Section 201 TTh 9:30-11 LSK200

Instructor: Nguyen Lam nlam "at" math "dot" ubc "dot" ca
Office Hours: (Please check back often for updates) at LSK 300C
    + Mon 12:40pm-1:30pm 
    + Tue 11am-11:50am
    + Thu 11am-11: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? Karush-Kuhn-Tucker conditions useful in Economics and Non-Linear Optimization? More Applications?)
+ Simplex Method (chapters 1-4, 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 11-14), Branch and Bound, Game theory (chapter 15), Non-linear Programming and the Karush-Kuhn-Tucker 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
 Th 04/01- Tu 09/01 + Course overview; introduction to linear programming (Aviation fuel blending problem): What is LP? (Ch. 1)
Standard form for linear programming problems (Obtaining Standard Inequality form) (Ch. 1)
+ Matrix formalism for linear programs, and geometric interpretation in 2 dimensions.
Introduction to the simplex method (examples by Richard Anstee) (Ch. 2)
 Th 11/01- Tu 16/01 Quiz 1: (Tuesday Jan 16 starting at 10:20am to the end of class) will be similar to Practice 1.  Practice 1 + Practice 2 (Soln)
Multiple optimal solutions (Ch. 3) 
Unbounded linear programs (An unbounded example (a slide show)) (Ch. 3)
+ The 2-phase Simplex Method and infeasible linear programs (Ch. 3) (Another example of 2-phase Method + Another example of Infeasibility)
Degenerate pivots and cycling (Degenerate Pivots and why not to fear them + Chvatal`s example of cycling (slides) which has the virtue of being an exact computation in binary. No numerical errors can result) (Ch. 3)
 Th 18/01-
Tu 23/01
Quiz 2: (Tuesday Jan 23 starting at 10:20am to the end of class) will be similar to Practice 1.
Practice 1 + Practice 2 + Practice 3
Matrix formulas for dictionaries (Ch. 7, first section)
Bland’s Rule guarantees termination (Ch. 3, Theorems 3.1 & 3.3)
Recap of the Simplex Method (Two Phase Method with an example)
Duality theorems (Ch. 5)
 Th 25/01-
Tu 30/01
Assignment 1: due Tuesday Jan 30 at the beginning of class
Duality theorems (Ch. 5)
Complementary Slackness (Ch. 5)
Coffee stain problem (by Richard Anstee)
 Th 01/02-
Tu 06/02
Quiz 3: Thursday Feb 1 Practice 1
Theorem of the Alternative
Marginal values
 Th 08/02-
Tu 13/02
Assignment 2: Thursday Feb 8
Quiz 4: Tuesday Feb 13
The Revised Simplex Method
Th 15/02 MIDTERM
Mo 19-
Fri 23
MIDTERM BREAK
Tu 27/02-
Th 01/03 



 
 


 

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: 
  • Glpk.js and online-optimizer. These are websites, you don’t need to install anything on your own computer! The second also does sensitivity analysis (for the constraints). 
  • The MixedLinearIntegerProgram class in SageMath. Sage can be used without installing any software at SageMathCell. If you chose the GLPK solver, it can also do sensitivity analysis. 
  • The scipy.optimize.linprog function from SciPy.


Ċ
Nguyen Lam,
Jan 20, 2018, 11:44 AM
Ċ
Nguyen Lam,
Jan 3, 2018, 6:23 PM
Ċ
Nguyen Lam,
Jan 13, 2018, 5:29 PM
Ċ
Nguyen Lam,
Jan 13, 2018, 5:23 PM
Ċ
Nguyen Lam,
Jan 18, 2018, 3:15 PM
Ċ
Nguyen Lam,
Jan 19, 2018, 1:57 PM
Ċ
Nguyen Lam,
Jan 3, 2018, 6:23 PM
Ċ
Nguyen Lam,
Jan 3, 2018, 6:23 PM
Ċ
Nguyen Lam,
Jan 3, 2018, 6:23 PM
Ċ
Nguyen Lam,
Jan 4, 2018, 7:15 PM
Ċ
Nguyen Lam,
Jan 4, 2018, 7:15 PM
Ċ
Nguyen Lam,
Jan 4, 2018, 7:15 PM
Ċ
Nguyen Lam,
Jan 13, 2018, 5:29 PM
Ċ
Nguyen Lam,
Jan 11, 2018, 5:01 PM
Ċ
Q1P2.pdf
(50k)
Nguyen Lam,
Jan 10, 2018, 7:12 PM
Ċ
Q2P2.pdf
(477k)
Nguyen Lam,
Jan 18, 2018, 3:03 PM
Comments