# MATH 340: Linear Programming

 Overview Textbooks Grading Quizes Homeworks Exams Notes Resources

 Winter Session 2016/17 Term 2 Tue Thu 9:30-11:00 CSCI-200 Mon Wed Fri 12:00-13:00 BUCH-A103 Solutions to final exam

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 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.

 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) Sample quiz 1 Thursday 12/01/17 Friday 13/01/17 Sample quiz 2 Thursday 26/01/17 Friday 27/01/17 Sample quiz 3 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

# Homeworks

 Homeworks Solutions Due date* (Section 1) Due date* (Section 2) Assignment 1 Solutions A1 Tuesday 24/01/17 Wednesday 25/01/17 Assignment 2 Solutions A2 Thursday 16/02/17 Friday 17/02/17 Assignment 3 Solutions A3 Thursday 16/03/17 Friday 17/03/17 Assignment 4 Solutions A4 Tuesday 04/04/17 Wednesday 05/04/17 Assignment 5 Solutions A5 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:

• 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

# 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

• 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

Platforms

Other resources

• Desmos An online graphing calculator.