2016/17 Term 2 
Tue Thu 9:3011:00 CSCI200 Mon Wed Fri 12:0013:00 BUCHA103 

Instructor: Ricardo Gómez, Mathematics Building 218, (604) 822 3262, rgomez at math dot ubc dot ca
Office hours: Classes ended.
Calendar:
Overview
Linear programming is the branch of mathematical optimization that focuses on linear constraints and linear objective functions. It is known under other aliases like linear optimization, operations research, etc. The course covers the basic theory, divided in four main topics, in approximately the first 8 weeks:
Chapters (main textbook) 
Weeks 

1.  Simplex method  14, 8 
3 
2.  Duality  5,9 
3 
3.  Simplex method revised  67 
1 
4.  Sensitivity  10 
1 
Optional topics will be coverd, they will be chosen among the following:
Chapters (main textbook) 
Vanderbei´s book 

6.  Efficient Allocation of Scarce Resources  11 

6.  Cutting and Stock and Branch and Bound  13 
23.5 
7.  Game Theory  15 
1 
8.  Parametric simplex and Portfolio Diversification  13 
Textbooks
Main 

Additional 

Grading
Exams. There will be two exams (no books nor calculators):
Making up exams policy strictly limmited to very serious reasons, previous notification (72 hrs in advance) and prooving documentation required. In the case of the final, contact Faculty of Science Office. 
Homeworks. There will be 5 assignments. Their emphasis will be on theory. Some will give computational questions and you will be able to use the available resoursers. Students may work together on assignments but must write up their solutions independently. They will be due at the beginning of class. No late homeworks will be accepted.
Quizes. There will be 5 quizes of 25 minutes in length maximum. Practice questions will be given in advance. These will be mostly computational problems. There will be no make up quizes.
Quizes
Samples 
Date* (Section 1) 
Date* (Section 2) 
Thursday 12/01/17 
Friday 13/01/17 

Thursday 26/01/17 
Friday 27/01/17 

Thursday 09/02/17 
Friday 10/02/17 

Thursday 02/03/17 
Friday 03/03/17 

Quiz 5 Revised Simplex Method (for practice, check 3 examples in slides notes 6) 
Thursday 23/03/17 
Friday 24/03/17 
Homeworks
Homeworks 
Solutions 
Due date* (Section 1) 
Due date* (Section 2) 
Tuesday 24/01/17 
Wednesday 25/01/17 

Thursday 16/02/17 
Friday 17/02/17 

Thursday 16/03/17 
Friday 17/03/17 

Tuesday 04/04/17 
Wednesday 05/04/17 

Thursday 04/06/17 
Wednesday 05/04/17 
Exams
Exams 
Solutions 
Date* and location (Section 1) 
Date* and location (Section 2) 

Midterm Content may include any of the following:
Previous midterms (some topics in these exams have not been covered in class and of course they will not be part of this exam). 
Classroom, Tuesday 07/03/17 
Classroom, Wednesday 08/03/17 

Final Content may include any of the following:

(with solutions) 
April 24th, 8:30 am WOOD 2 
April 24th, 8:30am WOOD 2 
Notes
We adapt the most recent scheme of the course in charge of Prof. Richard Anstee, in particular we will rely on Omar Antolín Camarena's Notes on Linear Programming. Additional slide notes and class material that complement the references will be posted:
Slides
 Slide notes 1. Introduction, LP problems, software, LP problems in standard form.

Slide notes 2. Slack variables, dictionaries, pivoting.
 Slide notes 3. Simplex algorithm in a nutshell, example of phase 1.
 Slide notes 4. Dual exarmples.
 Slide notes 5. Complementary slackness, reading solutions from final dictionaries, marginal values.
 Slide notes 6. Simplex method revised.
 Slide notes 7. Dual simplex method, sensitivity analysis.
 Slide notes 8. Cuttingstock, knapsack problem, branch and bound.
 Slide notes 9. Portfolio diversification.
Resources
Programs

Classic LINDO (Windows). You can obtain a free evaluation copy or use the compute lab in LSK 310 when available. 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. If you use Mac OS X, LINGO has a Mac version and it seems to understand LINDO commands.
Websites
 Onlineoptimizer
 Glpk.js
 A simple pivot tool and also an advanced pivot tool to verify computations (by Prof. R. Vanderbei).
Platforms
 The MixedLinearIntegerProgram class in SageMath. Sage can be used without installing any software at SageMathCell.
 The scipy.optimize.linprog function from SciPy.
Other resources
 Desmos An online graphing calculator.