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