Math 30210 - Introduction to Operations Research

Fall 2014

Instructor: David Galvin

NOTE: all course policies announced here are subject to change before the first day of semester! The date for the in-class midterm exam is tentative, and subject to change beyond the first day of semester (though plenty of notice will be given if it changes).

Fundamental to OR is programming, in which there is a finite collection of variables, collectively subject to some constraints, and a function of those variables (the objective function) that one wishes to maximize or minimize, without violating any of the constraints. When the constraints and objective are all linear functions of the variables (as is the case in many important examples), one has a linear programming problem. We will devote much of the semester to the study of linear programming, for which a beautiful mathematical theory has been developed over the last half century; unlike many mathematical theories, it is one which is applied the world over on a daily basis.

Towards the end of the semester, we will apply the theory of linear programming to the study of games, specifically to those games in which two people compete to capture as much as possible of a finite resource.

The rough plan is to cover Chapters 1 through 4, 7 and 9 of the textbook.

I will not consider requests for homework extensions, or make-up quizzes and/or exams, except in the case of legitimate, university-sanctioned conflicts. It is your responsibility to let me know the full details of these conflicts before they cause you to miss an assignment! Excepting university-sanctioned conflicts, it is your responsibility to be in class for all scheduled lectures.

Final exam: In 117 Hayes-Healy, Tuesday, December 16, 4.15-6.15pm. Here is the information that you need to know:

• The exam will be cumulative, but will lean heavily on material from after the midterm (probably 1/3 versus 2/3 before and after)
• you may use the textbook, your notes, printouts of course handouts, old homeworks, etc.
• here are the things that might appear on the final (not all will, of course):
  • Everything that was on the midterm (see below)
  • The various types of problems where integer constraints naturally arise; in particular the use of auxiliary integer variables
  • Gomory's cutting plane algorithm for solving pure integer programming problems: both the mechanism, and the justifications for why it works
  • The branch-and-bound algorithm for solving mixed integer/non-integer programming problems: both the mechanism, and the justifications for why it works
  • The following aspects of the transportation algorithm:
    • modifying a transportation problem appropriately to deal with supply not equally demand, and to deal with routes along which no goods are allowed to be shipped
    • finding an initial basic feasible flow using northwest corner rule
    • assigning u and v variables to a basic feasible flow, and the optimality criterion (including the reason the optimality criterion is correct)
    • finding an entering variable when the basic feasible solution is not optimal, and pushing flow around a loop to determining the entering value of the entering variable (including the reason why this decreases total cost)
  • Kruskal's minimum spanning tree algorithm: both the mechanism, and the justification for why it works
  • The following aspects of games (including all justifications):
    • Encoding two-person zero-sum perfect-information games as matrices
    • Finding and interpreting maximum security strategies and saddle points
    • Finding the security levels of mixed strategies, and the notion of optimal security
    • Converting the problem of finding optimal security into a linear programming program
    • The fundamental theorem of two-person zero-sum perfect-information games, and its interpretation
  • The notion of stability in a matching given preference lists, and running the Gale-Shapley algorithm to find a stable matching.
• This material is in the following sections of the book:
  • 1.1 through 1.2
  • 2.1 through 2.4, and 2.6
  • 3.1 through 3.7
  • 4.1 through 4.4
  • 6.1 through 6.4
  • 9.1 through 9.5
  • Class notes and handouts on Transportation algorithm, Kruskal's algorithm and the Gale-Shapley algorithm.

Midterm exam: In class on Wednesday, October 15. Here is the information that you need to know:

• you may use the textbook, your notes, old homeworks, etc.
• here are the things that might appear on the midterm (not all will, of course):
  • Setting up the variables, constraints and objective function for the various kinds of linear programming problems we have seen (blending problem, production problem, transportation problem, etc.)
  • Solving a two variable problem graphically, determining the optimum point from the cost ratio
  • Putting a general LP problem into standard form (in particular, using slack variables and dealing with unrestricted variables)
  • Putting a standard form problem into canonical form, when there is an obvious collection of basic feasible variables
  • Setting up an initial simplex tableau for a problem in canonical form
  • going back-and-forth between a simplex tableau and the linear equations that it encodes
  • Applying the optimality and unboundedness criteria to a simplex tableau, and explaining why these are correct
  • Deciding where to pivot in a simplex tableau, and explaining why
  • Running the full simplex method starting from a problem in canonical form
  • Introducing artificial variables to determine an initial basic feasible solution (if it exists); both the mechanics of this, and the reason that it works
  • Running the full simplex method, starting from an arbitrary LP problem
  • Using artificial variables to expose redundancy in an LP
  • Putting LP problems into Max form and Min form
  • Constructing the dual of a problem in Max form or Min form
  • Constructing the dual of an arbitrary LP problem, and using shortcuts to deal with equality constraints and unrestricted variables
  • Interpreting the dual problem in some simple cases
  • Applying and explaining the weak duality theorem
  • Applying the strong duality theorem and its consequences (the proof of strong duality won't appear)
  • Reading off a solution to the dual problem, from the final tableau of the simplex method applied to the primal problem, for a general primal LP.
• All this material is in the following sections of the book:
  • 1.1 through 1.2
  • 2.1 through 2.4 and 2.6
  • 3.1 through 3.7
  • 4.1 through 4.4.

Class conduct: The lecture room should be a place where you should feel free to engage in lively discussion about the course topic; don't be shy! But non course related interruptions should be kept to a minimum. In particular, you should turn off or switch to silent all phones, etc., before the start of class. If for some good reason you need to have your phone on during class, please mention it to me in advance.

A general comment: Like many other endeavors (such as driving a car or mastering a piece of software), mathematics is something that you learn by doing. Attending class and reading the appropriate sections of the textbook is very important, but isn't enough to do well. After each lecture you should work through every example and proof from your class notes. Don't be perturbed if you have to re-read and re-do some topics many times before you begin to feel that you are mastering them. That is just how mathematical learning goes. It's a slow process, but a worthwhile one.

If after struggling with a topic you still feel like you are making no headway, don't give up! Leave it aside for a while to let your unconscious brain work on it. Then go back to it, and talk it over with you colleagues, and come talk to me. It's what I'm here for!