MATH 21-292: Operations Research

Announcements

Here is the course syllabus.
*******Midterm 1 will be held on Friday February 23 in class*******
Here is a list of topics that you should know for the first midterm. Here is the first midterm from 2016 with solutions
These are videos giving examples of how to show a set is convex and how to set up the Big M method.
*******Midterm 2 will be held Monday April 9 in lecture******
Here is a list of topics that you should know for the second midterm. Here is the second midterm from a previous version of this course (number 1 not applicable for our midterm).
Here are videos giving examples of sensitivity analysis, of the transportation simplex method, and of the Hungarian algorithm.
Solutions for homeworks 5-7 are posted below to help you study for the midterm.
***********The final will be held on Monday May 14**********
Here is a final from a previous semester. In this course they covered convex programming at the end rather than integer programming, so you should skip question 2.
Here is a list of topics that you should know for the final.
I've uploaded videos on using the network simplex method and branch and bound algorithm

Schedule

Week 1: Hillier and Lieberman 3.1-3.4
Week 2: The simplex method. Hillier and Lieberman 4.1-4.4 along with some theory.
Week 3: Mathematical theory of the simplex method, pitfalls of the simplex method, big M method. Hillier and Lieberman 4.5-4.6
Week 4: Two-phase method, postoptimality analysis. Hillier and Lieberman 4.6-4.7
Week 5: The simplex method via matrices. Hillier and Lieberman chapter 5
Week 6: The fundamental insight and midterm 1
Week 7: The dual problem, dual-primal relationships, symmetry by the dual of the dual. Hillier and Lieberman 6.1, 6.3
Week 8: Fundamental duality theorem, Chvatal's Linear Programming Chapter 5, and Sensitivity analysis, Hillier and Lieberman 7.1-7.2
Week 9: Spring Break
Week 10: Sensitivity analysis. Hillier and Lieberan 7.1 and 7.2
Week 11: The transportation and assignment problems. Hillier and Lieberman 10.1-10.4
Week 12: Graph theory introduction, minimum vertex cover and maximum matching problems
Week 13: Exam 2, shortest path problem, minimum spanning tree problem, max flow-min cut theorem
Week 14: The network simplex method, Hillier and Lieberman 10.7
Week 15: Integer programming, Hillier and Lieberman Chapter 12

Homework

All homework exercises are from Hillier and Lieberman 10th edition unless otherwise noted. If you have a different edition of the book, the exercises may be different! Please check with me or a colleague to make sure you have the correct problems.

Homework 1 (due Friday January 26 in lecture): 3.1-5, 3.1-9, 3.1-13, 3.4-14(a), given a linear optimization problem with 2 decision variables and a non-empty and bounded feasible region use the graphical method to sketch a proof that an optimal solution lies on a corner point.
Homework 2 (due Friday February 2 in lecture): 4.1-6, 4.3-4, 4.3-7, 4.5-8
Homework 3 (due Friday February 9 in lecture): 4.6-2 (a) and (c)-(e), 4.6.5 (a) and (c), 4.6-9 (a)-(c)
Homework 4 (Due Friday February 23 before the exam): 5.3-1, 5.3-2, 5.3-3, 5.3-4, prove that if a linear optimization problem has 2 optimal solutions then it has infinitely many optimal solutions.
Homework 5 (Due Wednesday March 7 in lecture): Problem set. Solutions
Homework 6 (Due Friday March 23 in lecture): 7.1-1, 7.2-2, 7.2-6. Solutions.
Homework 7 (Due Friday March 30 in lecture): Problem set. Solutions.
Homework 8 (Due Friday April 6 in lecture): 9.2-3(a), 9.2-6, 9.2-7(a), 9.4-4, 9.4-6
Homework 9 (Due Monday April 23 in lecture): 10.3-4, 10.4-1, 10.5-1, 10.5-3(a)-(b)
Homework 10: (Due the last day of lecture) 10.7-1, 10.7-7, 12.4-9, 12.5-2, 12.6-2 but remove x_4 from the problem entirely (hint: to save time, solve LP relaxations geometrically)

Contact Information

Teaching Assistant