Instructor: Anatolii Grinshpan

Office hours: MTR 2 – 3, Korman
249, or by appointment, Korman 253.

Course
information
Academic
Calendar
Some links: Ferguson,
Vanderbei, Tutoring center

Sep 24. Introduction to the course.
Examples of problems.

Sep 26.
The simplex method.

Reading:
Chapters 1, 2. Problems.

Oct
1. Initialization.
Unboundedness.

Oct
3. Quiz 1 (Chapters 1, 2). Degeneracy.

Reading:
Chapter 3. Problems.

Oct
8. Cycling.
Perturbation method. Bland’s
rule. Example.

Oct 10.
Quiz 2 (Chapter 3). Proof of Bland’s
theorem.

Reading:
Chapters 3, 4. Problems.

Oct
15. Fundamental theorem of Linear
Programming. Efficiency of the simplex method.

Oct
17. Midterm
1 (Chapters 1-4). Problems.

Oct 22.
Convocation (no class).

Oct 24.
Duality theory.

Reading:
Chapter 5. Problems.

Oct 29.
Strong duality theorem. Dual-based
simplex method.

Oct 31.
Dual-based simplex method. Quiz 3 (Chapter 5).

Reading:
Chapter 5. Problems.

Nov
5. Resource
allocation. Matrix notation.

Nov
7. Matrix
notation. Example. 2-by-2 case.

Reading:
Chapter 6. Problems.

Nov 12.
Quiz 4 (Chapter 6). Convex sets.

Nov 14.
Convex hull. Carathéodory’s theorem. Farkas’ lemma. Illustration.

Reading:
Chapter 10. Problems.

Nov 19.
Quiz 5 (Chapter 10). Separation of polyhedra.
Strict complementarity.

Nov 21.
Midterm 2 (Chapters 5, 6, 10).

Nov 26.
Matrix games. The minimax theorem.

Reading:
Chapter 11. Problems.

Dec 3. Network flow problems (Chapter 14). Example.

Dec 5.
Quiz 6 (Chapter 11). Integer programming: the traveling salesman problem
(Chapter 23).

*Dec 9. Questions session: 1:30-3:20, Lebow
133.*

Dec 10.
Final exam (all lectures): 10:30-12:30, GL 48.