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).
About the course
Operations Research (OR) is the application of mathematical ideas to decision making. In a typical decision-making problem tackled by OR, one has some (usually limited) resources, some ways of deploying those resources, and some objective, and one asks how the resources should be deployed in order to reach the objective, or get as close to it as possible. For example, the resources might be a fleet of trucks, and the objective might be to send a collection of packages to some addresses across the state, at low cost (this is an OR problem that UPS has to solve everyday); the resources might be classrooms on campus, and the objective might be to schedule a semester's worth of classes with as few time-conflicts as possible for students and professors (this is a problem ND has to solve twice a year); or the resource might be time, and the objective might be to spend it in a fulfilling way (this is a problem one spends a lifetime solving).
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.
Back to the top of the page
Basic information
- Meeting times: Monday, Wednesday, Friday, 3.00pm to 3.50pm, Hayes-Healy 117, August 27 to December 10.
- Instructor: David Galvin, 248 Hayes-Healy (dgalvin1 at nd.edu). Feel free to email me anytime. I try to respond quickly to any question or comments.
- Office hours: Tuesday 2-3pm and Friday 4-5pm
- Textbook: An introduction to linear programming and game theory by Paul Thie and Gerard Keogh, third edition, published by Wiley, ISBN: 0470232862,
ISBN-13: 9780470232866. The bookstore will not have any copies of this, so I suggest getting it from someplace like Barnes and Noble, Amazon or ABE books.
Back to the top of the page
Assessment
- Homework: Written homework will be assigned roughly every week; in total, homework will count for 100 points out of 450 (each homework equally weighted). Specific homework policies will be announced with the first homework.
- Quizzes: In-class quizzes will be given roughly every second week; in total, quizzes will count for 100 points out of 450 (each quiz equally weighted). Detailed information about each quiz (the material being covered, and when it will be given) will be announced in class a few days before each one.
- Midterm exam: There will be one in-class midterm, tentatively planned for Wednesday, October 15; this will count for 100 points out of 450. Detailed information about the midterm (such as the material being covered) will be announced in class in early October.
- Final exam: The (cumulative) final exam for this course will take place as follows:
- Tuesday, December 16, 4.15pm-6.15pm,
and will count for 150 points out of 450. Specific information about the final exam, such as where it will be held, and what to do in the case of a conflict, will be announced in class during the final week of the semester.
- Final grade: A total of 414 out of 450 will earn you an A/A-; a total of 360 out of 450 will earn you a B+/B/B-; a total of 292.5 out of 450 will earn you a C+/C/C-.
- Sakai: Your marks on each of the graded components will be periodically updated on Sakai.
Back to the top of the page
Late assignments
All homework must be done by the due date to receive credit, and all quizzes and exams must be taken at the assigned times.
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.
Back to the top of the page
Homework
Homework assignments are posted here, in a single file that will be updated throughout the semester. For homework solutions, see the end of this section.
The weekly homework is an important part of the course; it gives you a chance to think more deeply about the material, and to go from seeing (in lectures) to doing. It's also your opportunity to show me that you are engaging with the course topics.
Homework is an essential part of your learning in this course, so please take it very
seriously. It is extremely important that you keep up with the homework, as if you do not, you may quickly
fall behind in class and find yourself at a disadvantage during exams.
You should treat the homework as a learning
opportunity, rather than something you need to get out of the way. Reread, revise, and polish
your solutions until they are correct, concise, efficient, and elegant. This will really deepen your
understanding of the material. I encourage you to talk with your colleagues about homework problems, but your final write-up must be your own work.
Homework solutions should be complete (and in particular presented in complete sentences), with all significant steps justified.
Homework solutions:
- Homework 10
- Homework 9
- Homework 8
- Homework 7. Correction: In my solution to question 5 I at one point mis-transcribed one of the constraints. So in my final answer, the constraint ``-x2+x3 less than or equal -50 + 200(1-w2)'' should have been ``-x2+2x3 less than or equal -50 + 350(1-w2)''.
- Homework 6. Correction: For the last question, I gave the solution to part e) instead of part b). Here is the solution to part b).
- Homework 5
- Homework 4. Corrections: in problem 4, parts a) and d), I transcribed data incorrectly into the initial tableau. The corrected tableau, and associated correct answers, are here.
- Homework 3
- Homework 2. Corrections: in the solution to problem 2, part g, the ``-x_4'' in the second constraint in the standard form should be removed. In the solution to problem 3, part b, the second constraint should be ``x_1 + 6 - x_4 >= 11 or x_1 - x_4 >= 5''. Once the correct line is graphed, it turns out that the only feasible point is x_1=5, x_4=0.
- Homework 1. Correction: in the solution to problem 4, the line ``=2.6x + 6.1y +5z'' should be removed.
Back to the top of the page
Quizzes
Quizzes will be posted here, in a single file that will be updated throughout the semester.
Quiz solutions:
Back to the top of the page
Exams
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.
Back to the top of the page
Supplementary material
Here is where I will post any supplementary material for the course, such as slides that I go over in class.
In-class slides
Example of greed not being good:
Worksheet on Solver:
Back to the top of the page
Conduct
Honor code: You have all taken the Honor Code pledge, to not participate in or tolerate
academic dishonesty. For this course, that means that although you may (and should) discuss assignments
with your colleagues, you must write the final version of each of your assignments on your own; if you use
any external sources to assist you (such as other textbooks, computer programmes, etc.), you should cite
them clearly; your work on the mid-semester exam and the final exam should be your own; and you will adhere
to all announced exam policies.
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!
Back to the top of the page