Teaching‎ > ‎

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

Instructor: Nguyen Lam nlam "at" math "dot" ubc "dot" ca
+ 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.

Course Material
 Th 04/01- Tu 09/01 + Course overview; introduction to linear programming ( +  + Matrix formalism for linear programs, and geometric interpretation in 2 dimensions. + 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) + 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 Matrix formulas for dictionaries (Ch. 7, first section)Bland’s Rule guarantees termination (Ch. 3, Theorems 3.1 & 3.3) Duality theorems (Ch. 5) Th 25/01- Tu 30/01 due Tuesday Jan 30 at the beginning of classDuality 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 1Theorem of the AlternativeMarginal values Th 08/02- Tu 13/02 Assignment 2: Thursday Feb 8Quiz 4: Tuesday Feb 13The 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 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