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