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