# Math 340: Introduction to Linear Programming

Announcements

Jan 8:   Homework 1 (due on Thursday, Jan 16) is posted below.
Jan 21: Solutions of Homework 1 are posted below.
Jan 21: Homework 2 (due on Tue, Feb 4) is posted below.
Jan 29: Solutions of Quiz 1 are here.
Feb 4:   Solutions of Homework 2 are posted below.
Feb 4:   Homework 3 (due on Tue, Feb 11) is posted below.
Feb 6:   Example on complementary slackness (from today's lecture)
Feb 10: Info on the midterm: The midterm will be in class during our regular time on Feb 13. It will be closed book. As I mentioned in class, it will cover everything we did in class, reflected roughly in the homework problems in assignments 1-3. Specifically, we covered most of the material in Chapters 1-3, Chapter 5, and the beginning of Chapter 7 (matrix description of dictionaries).
Feb 11:  Here are the practice problems we discussed in class today and their solutions.
Feb 11:  Solutions of Homework 3 are posted below.
Feb 27:  Here are the solutions of the midterm.
Mar 4:   Here is an example where revised simplex method is used to solve an LP.
Mar 6:   Homework 4 (due on Th, Mar 13) is posted below.
Mar 17: Solutions of Homework 4 are posted below.
Mar 23: Homework 5 (due on Tue, Apr 1) is posted below.
Mar 27: Here is the sensitivity analysis example (full) we have started working on last time. This example was adopted from the Trucking Example by Prof. Anstee. Here is the link to another sensitivity analysis example by Prof. Anstee.
Apr 11: Solutions of Homework 5 are posted below.

Instructor Information
Instructor: Ozgur Yilmaz
Email : oyilmaz-at-math.ubc.ca
Office: Math Annex 1113
Hours:  By appointment
Phone: 822-5963

Course Information

Section: 202

Class times and location:
 Day Start Time End Time Building Room Tue-Th 11:00 12:30 Buchanan B213

Course web page: http://www.math.ubc.ca/~oyilmaz/courses/m340/m340.html will be updated throughout the term.

Text (Required):  Vasek Chvatal, "Linear Programming".

Other references:
• See the following webpages by previous instructors that have excellent handouts, practice materials, etc (though note that our coverage may not fully coincide with these past versions):
• There are various books on the subject -- check out the library.
• This article by Dantzig (inventor of the simplex method) gives a historical perspective on linear programming.

Material:
1. Linear programming: problems, motivation (Chapter 1)
2. The simplex method (Chapters 2-4,8)
3. Duality theory (Chapter 5)
4. Revised simplex method (Chapter 7)
5. Sensitivity analysis (Chapter 10)
6. Applications (we will decide together what to cover here -- potential applications: game theory, signal processing, geometry,...)

Resources:

• Math Learning Center: The Math Learning Centre (MLC) is a space for undergraduate students to study math together, with support from math tutors, who are graduate students in the math department. Please note that while students are encouraged to seek help with homework, the MLC is not a place to check answers or receive solutions, rather, its aim is aid students in becoming expert learners; to develop critical thinking and skills in a mathematical setting.

If you need help, or would like to discuss any aspect of this course, please make an appointment to see me in my office.

Homework:  15%
Midterm:  35%
Final:  50%

There will be one midterm exam, on Thursday, February 13 in class.

Missing a midterm normally results in a mark of 0.
Exceptions may be granted in two cases: prior consent of the instructor or a medical emergency. In the latter case, the instructor must be notified within 48 hours of the missed test, and presented with a doctor's note immediately upon the student's return to UBC. In such cases, there will be no make-up exam. Instead, the final exam mark will be adjusted to make up for the missed midterm mark.

Homework Assignments

Homework assignments will be posted on the course web site. Late homework will not be accepted. The lowest homework grade will be dropped.

Important Note: You may collaborate with fellow students on homework assignments, but you must write up your answers independently, in your own words. Any two or more homeworks with some essentially identical answers will be given 0! Please read UBC's Academic Integrity Code.

 Homework 1 (due on Th, Jan 16) Problems Solutions Homework 2 (due on Tue, Feb 4) Problems Solutions Homework 3 (due on Tue, Feb 11) Problems Solutions Homework 4 (due on Th, Mar 13) Problems Solutions Homework 5 (due on Tue, Apr 1) Problems Solutions

Calendar

 Tue, Jan 7 First lecture Th, Feb 13 Midterm Feb 17-21 Winter mid-term break Tue, Apr 8 Last lecture TBA Final Exam