Math Models of OR, Fall 2008.

MATP4700/DSES4770

Contents of this page:

Course basics:

• Course outline.
• Intended schedule.
• The course books will be on reserve in the library. You can borrow the materials for up to an hour. Further, you can borrow the books overnight if you check them out less than an hour before closing time and return them early the following day. Homework and exam solutions will be available online.
• Grade spreadsheet including the first exam and the sum of the first two parts of the project.

Homeworks:

• Homework 1.
• Solutions to homework 1: chapters 1, 2, 3, and 4.
• Homework 2.
• Solutions to problems in Chapter 5.
• Homework 3.
• Solutions to problems in Chapter 7.
• Homework 4.
• Solutions to problems in Chapter 10.
• Homework 5.
• Solutions to all problems in Chapter 11.
• Solutions to all problems in Chapter 12.

Exams:

• An optional quiz on the material from Exam 1.
• Exam 1:
  • Solutions to Exam 1, versions A, B, and C. (Note that the solutions to question 2(b) don't give the new basic feasible solutions.) Mean: 67%. Median: 61%. Min: 30%. Max: 99%.
  • Exam 1 is on Tuesday, September 30, in class. It will cover parts of chapters 2-5; more specifically, the sections covered in class. You can bring one 8.5x11 sheet of handwritten notes; you can write on both sides.
  • Exam 1 from Fall 2005 along with its solution. Mean: 78%. Median: 82%. Standard deviation: 18.
  • Exam 1 from Fall 2004 along with its solution. The mean on this exam was 73%.
  • Exam 1 from Fall 2003 along with its solution.
  • Exam 1 from Fall 2002 along with its solution. The mean on this exam was 75%.
• Exam 2:
  • Exam 2 is in class on Friday November 21. It will cover parts of chapters 7 and 10; more specifically, the sections covered in class. You can bring one 8.5x11 sheet of handwritten notes; you can write on both sides.
  • Exam 2 from Fall 2005, along with its solution. The mean on this exam was 69%, with a median of 72% and a standard deviation of 23%. This exam will be discussed in class on Tuesday November 18.
  • Exam 2 from Fall 2004, along with its solution. The mean on this exam was 74%, with standard deviation 22.
  • Exam 2 from Fall 2003, along with its solution. The mean on this exam was 78%.
  • Exam 2 from Fall 2002, along with its solution. The mean on this exam was 80%. (Note: the question 5 in the solutions is the `real' question 5. The one in the sample exam is from an earlier draft.)

Project:

• The first part of the project is due on September 26 October 7. Here is a printer-friendly pdf version of the project.
• Information about AMPL.
• Displaying all variables simultaneously.
• Here are the model and data files for the Fall 2003 course project discussed in class on September 23.
• The AMPL website has an example of a model and data file for a problem with a three-dimensional array.
• Here is a snippet of my model and data file, showing how to use the within command and one way to input a 3-dimensional array.
• The sensitivity analysis part of the project is due on November 4. If you prefer to use them, my model and data file are available on the course website.
• Solution to the senstivity analysis questions.
• The third part of the project is due on December 5.

Notes:

• Introductory examples. Improving search.
• The simplex algorithm.
• More on the simplex algorithm.
• The Klee-Minty cube.
• Duality. Dual simplex. Sensitivity analysis.
• Network flows.
• Integer programming. Here is information on modeling piecewise linear functions.
• Interior point methods.
• Dynamic programming, part 1 and part 2.

Handouts:

• Modeling piecewise linear functions.
• The crew scheduling example taken from J. G. Ecker and M. Kupferschmid: Introduction to Operations Research.
• The Fall 1994 DSES DQE question on complementary slackness.
• Solving a knapsack problem using the dual simplex method.
• An example of the dual simplex method.
• Handling upper bounds in simplex.
• The brewery problem formulated as an AMPL example with sets. Data files can be found in this directory.
• AMPL tutorial, from Gabor Pataki.
• An interactive formulation of the diet problem is available from the Optimization Technology Center at Argonne National Lab. The link also includes the ampl code for the diet problem.
• Applications of Optimization
• A comment from Irv Lustig from 2000 discussing the performance of various algorithms for linear programming.

Other Resources:

• Information about AMPL.
• Optimization Models for Decision Making, a webbook by Katta Murty that covers similar material to that in this class. The same author also has available a webbook on algorithmic linear algebra.
• Linear Programming FAQ
• Myths and counterexamples in linear programming. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in linear programming.
• A list of operations research sites.
• RIOT: Baseball Playoff Races. This site uses linear programming to determine when a baseball team is eliminated from contention.

RPI Math