## 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

- Email: mtait at cmu dot edu
- Office: Wean Hall 7124
- Office hours: Tuesday 2-4 pm or by appointment

### Teaching Assistant

- C.J. Argue
- Email: cargue at andrew dot cmu dot edu
- Office Wean Hall 6207
- Office Hours: Monday afternoon by appointment and Thursday 3-5 pm