MATH 340 201 2020W Introduction to Linear Programming

This semester I'm teaching Introduction to Linear Programming MATH 340:201 at University of British Columbia. Here there are some informations about my section.

Exam: there will be one midterm (20% of the final mark each) and a final exam (40% of the final mark)

Office hours: office hours will be held on-line on zoom on Tuesday and Thursday, at the end of my lectures.

Assignments: there will be a total of 10 assignments throughout the term (40% of the final mark):

Jan 23th: HW1
Jan 29th: HW 2
Feb 5th: HW 3
Feb 12th: HW 4
March 5th: HW 5
March 12th: HW 6
March 19th: HW 7
April 4th: HW8
April 11th: HW 9
April 14th: HW 10 [For extra credit]

Note that:

I will assume students to be familiar with the material of MATH 152, 221, and 223
It is highly recommended that students have taken a multi-variable calculus course (e.g. Math 200, 253, etc.). Also, basic knowledge of mathematical proofs (e.g. Math 220) is highly recommended for taking this course.

Textbook: we are using Robert Vanderbei's Linear programming, fundations and extensions. There will be some mandatory readings.

Reference Textbooks:

Games Theory: "Lectures on the Theory of Games", by W. Kuhn
Calculus: CLP Calculus Textbook, the book you most probably used in your Calculus classes at UBC
Linear Algebra: Introduction to linear algebra, by Gilbert Strang

Course Syllabus: it follows an indicative syllabus. If time permits I will explore additional applications of linear programming. For sure I'm going to cover the material in Part One of Vanderbei's textbook.

Week one. Introduction to Linear programming. Some leading problems: the manager problem, and the diet problem. Toy theory in 2D: 1) drawing the solution set of a system of inequalities, 2) the minima/maxima of a linear function are on the vertices. Linear optimization problems in standard form.

Homework: HW1 (solutions)

Lecture notes: Notes Week 1

Suggested readings: for the first couple of lectures I assembled the class material myself, no suggested readings for this week.

Week two. The simplex method I. A leading example. The simplex method. Problems with multiple solutions. Unbounded problems. Intro to Python computer language.

Homework: HW2 (solutions)

Lecture notes: Notes Week 2

Suggested readings: this week we are covering Chapter 2 of the textbook, please carefully read sections 2.1 and 2.2.

Python/Jupyter: to use Jupyter follow this link and log in using your CWL credentials. Here there is the code I used during my class, and here a nice intro I found on you tube.

Week three. The simplex method II.

Review of the simplex method, and further examples. Deciding if the admissible region is non-empty: the associated auxiliary problem. The simplex algorithm in pseudocode.

Homework: HW3 (solutions).

Lecture notes: Notes Week 3

Week four. The simplex method III. Pivoting rules: Anstee's rule, and Bland's rule. Cycling and termination of the symplex algorithm. Time complexity of the simplex method. Matrix notation. Convexity.

Lecture notes: Pivoting and cycling

Suggested reading (optional): read the proof of Theorem 3.3 from the textbook.

Duality I. Estimating the maximum value: intro to duality. The weak duality theorem.

Lecture notes: Duality

Homework: HW4 (solutions).

Week five: Duality II. The dual problem in matrix notation. The dual simplex method. The dual of the dual problem is the primal problem. Interpretation of duality in a business problem: shadow prices and opportunity cost. Unboundness and feasibility of the dual problem (statement and proof). Complementary slackness.

Lecture notes: Notes Week 5

Week six: Duality III. Unboundness and feasibility of the dual problem (end of the proof). Complementary slackness (with proof). Midterm.

Lecture notes: Notes Week 6

Week seven: Matrix Notation. Complementary slackness (example). Networks flow optimization. The simplex algorithm in matrix notation. Example.

Homework: HW5.

Lecture notes: Notes Week 7

Week eight: Sensitivity Analysis I. Example about the simplex algorithm in matrix notation. Sensitivity analysis.

Homework: HW6 (solution)

Lecture notes: Notes Week 8

Week nine: Sensitivity Analysis II. Sensitivity analysis (continued). Application to a business problem. Parametric simplex method.

Homework: HW7 (solution)

Lecture notes: Notes Week 9

Week ten: Game Theory I. Intro to games. Equilibria by elmination of dominated strategies. Nash equilibria. Random variables: expectation. Zero-sum games. Equilibria in mixed strategies (part 1).

Homework: HW8 (solutions)

Lecture notes: Notes Week 10

Week eleven: Game Theory II. Equilibria in mixed strategies (part 1). The Nash-Von Neumann theorem. Random variables: variance. Applications to finance: portfolio managment (part one).

Homework: HW 9

Lecture notes: Zero-sum games, Portfolios.

Week twelve: Applications to Quantitative Finance.

Applications to finance: portfolio managment (part two). A linear model for pricing call options.

Lecture notes: Notes Week 12

Price is right yo