Math 3272: Linear Programming (Fall 2022)

Mikhail Lavrov


Archiving note

This is an archived version of a class I taught at Kennesaw State University. For now, you can still find my course webpage on KSU's website, but I expect it to be taken down eventually. I think these are pretty okay, so I've decided to archive them on my personal webpage. If you spot any mistakes, please let me know.

I have another set of linear programming notes archived on this website: here is the linear programming class I taught at the University of Illinois Urbana-Champaign. The notes there are, broadly speaking, less polished but cover more material.


General information

D2L will be used to submit assignments (these will be posted both here and on D2L, for convenience) and to view grades. The syllabus will also be posted there.

During the scheduled office hours, you should feel free to show up with no notice if you have questions of any kind.

If you cannot make the scheduled office hours, begin by emailing me; if your questions are easy to answer by email, I will do that, and if not, we can find another time to meet. (Allow some time for me to check my email.).

Homework and Exams

There will be eight homework assignments, two midterm exams, and one final exam; the dates are marked below.

I will post the homework assignments here and on D2L; they are always due on Friday at 11:59pm, via D2L.

Exams will be given in person during our ordinary 75-minute class period.

Textbooks

Our official textbook for the course is Robert Vanderbei's Linear Programming: Foundations and Extensions. I will not go entirely in the same order, and sometimes I will cover topics this textbook does not cover. In any case, all the material covered will be in the lecture notes posted on this page.

Detailed Schedule

A label like RV 12.34 indicates that we will cover Chapter 12, section 34 of the textbook. (We might not always cover exactly the material in that section.)

Lecture notes will be available on the day of the lecture or earlier.

Some of you might be interested in the .tex source files for the lectures. (I've gotten several questions like: "How do you make these diagrams?" It's all TikZ.).

Date Topic covered Other Details
Tue 8/16 Intro to linear programs
Lecture notes
RV 1.1-1.2
Thu 8/18 Constraints in LPs
Lecture notes
RV 1.2, 2.1
Tue 8/23 Review of linear algebra
Lecture notes; Problems
Thu 8/25 Basic solutions and pivoting
Lecture notes
RV 2.1
HW 1 due Friday
Tue 8/30 Objective functions
Lecture notes
RV 2.1-2.2
Thu 9/1 The simplex method
Lecture notes
RV 2.4-2.5
Tue 9/6 Two-phase methods
Lecture notes
RV 2.3
Thu 9/8 Pivoting rules
Lecture notes
RV 3.1-3.4
HW 2 due Friday
Tue 9/13 Corner points
Lecture notes
RV 6.1
Thu 9/15 Revised simplex method
Lecture notes
RV 6.2-6.3
Tue 9/20 Worst cases
Lecture notes
RV 4.1-4.4
Thu 9/22 Simplex method review HW 3 due Friday
Tue 9/27 Exam 1
Thu 9/29 Duality
Lecture notes
RV 5.1-5.3, 5.8
Tue 10/4 Complementary slackness
Lecture notes
RV 5.4-5.5
Thu 10/6 The dual simplex method
Lecture notes
RV 5.6-5.7
HW 4 due Friday
Tue 10/11 Uses of dual simplex
Lecture notes
RV 5.6-5.7
Thu 10/13 Sensitivity analysis
Lecture notes
RV 7.1
Tue 10/18 Zero-sum games
Lecture notes
RV 11.1-11.3
Thu 10/20 Solving zero-sum games
Lecture notes
RV 11.1-11.3
HW 5 due Friday
Tue 10/25 Network flows and cuts
Lecture notes
RV 14.1, 15.5
Thu 10/27 The Ford-Fulkerson method
Lecture notes
Tue 11/1 The integral flow theorem
Lecture notes
Thu 11/3 Transversals
Lecture notes
HW 6 due Friday
Tue 11/8 Duality + network review
Thu 11/10 Exam 2
Tue 11/15 Integer programming
Lecture notes
RV 23.1, 23.3
Thu 11/17 Branch-and-bound
Lecture notes
RV 23.5
HW 7 due Friday
Tue 11/22 No class
Thu 11/24
Tue 11/29 Cutting planes
Lecture notes
Thu 12/1 The traveling salesman problem
Lecture notes
RV 23.2
HW 8 due Friday
Tue 12/6 Final exam (6:00pm to 8:00pm)

Last updated June 2, 2025. Mikhail Lavrov <misha.p.l@gmail.com>