Winter Session

2016/17 Term 2

Section 201:

Tue Thu 9:30-11:00 CSCI-200

Section 202:

Mon Wed Fri 12:00-13:00 BUCH-A103

Instructor: Ricardo Gómez, Mathematics Building 218, (604) 822 3262, rgomez at math dot ubc dot ca

Office hours: Classes ended.

Calendar:

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
1-4, 8
3
2. Duality
5,9
3
3. Simplex method revised
6-7
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

  • Linear Programming, Vašek Chvátal.
Additional
  • Linear Programming. Foundations and Extensions, Robert J. Vanderbei.
  • Understanding and Using Linear Programming, Matousek and Gartner.
  • Elementary Linear Programming with Applications, Kolman and Beck.

Grading

grading

Exams. There will be two exams (no books nor calculators):

  • Midterm. A 50min long exam in classroom, containing the main topics of the course.
  • Final. A 3hrs long exam (date and place to be announced), containing all the material covered in the course.

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)

Quiz 5A solved

Quiz 5B solved

More revised simplex samples

Thursday 23/03/17
Friday 24/03/17
* Dates may vary, please follow updates and announcements.

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
* Dates may vary, please follow updates and announcements.

Exams

Exams
Solutions

Date* and location (Section 1)

Date* and location (Section 2)

Midterm

Content may include any of the following:

  • Simplex algorithm: Phase 1 and 2, decision, slack, basic and non-basic variables, optimality, multiple solutions, feasibility, unboundedness, cycling, degeneracy.
  • Duality: Weak and strong duality, complementary slackness, theorem of the alternative, marginal values.
  • Revised simplex method: Matrix formulation.
  • Sensitivity.

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:

  • Simplex algorithm: Standard form, phase 1 and 2, decision, slack, basic and non-basic variables, optimality, multiple solutions, feasibility, unboundedness, cycling, degeneracy, geometric approach, particularly 2D.
  • Duality: Weak and strong duality, complementary slackness, theorems of the alternative, marginal values. Certificates of optimality. Dual and primal dictionaries.
  • Revised simplex method: Matrix formulation, duality.
  • Sensitivity. Coefficient perturbation, constraint perturbation, new constraints, new variables. Parametric self-dual simplex method.
  • Applications. Efficient allocation of scarce resources, cutting-stock, knapsack problem, marginal values, branch and bound, game theory, value of games and fairness, 2 x 2 matrix games, optimal strategies, minimax theorem, basics of portfolio diversification.

Previous term final

Other previous finals

Final Exam

(with solutions)

April 24th,

8:30 am

WOOD 2

April 24th,

8:30am

WOOD 2

* Dates may vary, please follow updates and announcements.

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

  1. Slide notes 1. Introduction, LP problems, software, LP problems in standard form.
  2. Slide notes 2. Slack variables, dictionaries, pivoting.
  3. Slide notes 3. Simplex algorithm in a nutshell, example of phase 1.
  4. Slide notes 4. Dual exarmples.
  5. Slide notes 5. Complementary slackness, reading solutions from final dictionaries, marginal values.
  6. Slide notes 6. Simplex method revised.
  7. Slide notes 7. Dual simplex method, sensitivity analysis.
  8. Slide notes 8. Cutting-stock, knapsack problem, branch and bound.
  9. Slide notes 9. Portfolio diversification.

Resources

Programs

Websites

Platforms

Other resources