Operations Research

The course will introduce fundamental topics in operations research at the undergraduate level. Some specific topics to be covered are: Formulations, Linear Programming, Simplex Method, Duality, Sensitivity Analysis, Transportation, Assignment Problems, Network Optimization Problems, Integer Programs, Nonlinear Optimization, and Game Theory.

Pre-requisites: Mathematical maturity at the level of a junior undergraduate student will be assumed. Prior coursework in Linear Algebra, Calculus and familiarity with Matrices is required.

Homeworks, Exams

  • Midterm and Final will be in-class written exams. No cheat sheets.
  • We will have about 10 to 12 homeworks (one per week).
  • Homeworks will be assigned on Wednesdays. Solutions will be due the following week before the beginning of the lecture. Strict due dates will be enforced.
  • Homework submisions should have each problem starting in a fresh page. State the problem number clearly. The problems should appear in order.
  • Staple and write your name in your submission. Unstapled/unnamed submissions will not be graded.
  • Electronic submission will be accepted provided it is in a "single file pdf" format. Submissions should be through the Compass2g website. Email submissions will NOT be accepted.
  • You are encouraged to discuss the course material, especially the practice problems and the review problems, with each other, but no collaboration or other solution sources are allowed on the problems assigned for homework, midterm or final.
  • Write clearly. Illegible submissions will not be graded.
  • Plagiarism will be dealt with severely. No credit for the homework, midterm or final.

Lectures

The following is a tentative list of lectures. Subject to change.
Lecture slides will be posted a day before the lecture in Compass2g.
  • Week 1
    • Aug 22: Introduction, Formulations
    • Aug 24: Linear Programming, Standard Form
    • Aug 26: Graphic Method, Corner Points
  • Week 2
    • Aug 29: Simplex Method: Augmented LP, Basic Variables
    • Aug 31: Simplex Method: Basic Feasible Solution, Intuition and Overview
    • Sep 2: Simplex Method: Initialization, big M method, Iteration Steps, Termination
  • Week 3
    • Sep 5: Labor day
    • Sep 7: Simplex Method: Degeneracy, Bland's rule, Algebraic form
    • Sep 9: Simplex Method: Tabular form
  • Week 4
    • Sep 12: Shadow prices
    • Sep 14: Dual linear program, Primal-Dual connections
    • Sep 16: Strong and Weak Duality, Complementary Slackness
  • Week 5
    • Sep 19: Dual solution from Simplex tableau, Dual Simplex Method
    • Sep 21: LP in matrix form, Simplex method in matrix form
    • Sep 23: Simplex method: Connections between matrix form and tabular form, Sensitivity Analysis: changing objective
  • Week 6
    • Sep 26: Sensitivity Analysis: changing RHS, addition of a constraint
    • Sep 28: Sensitivity Analysis: addition of a variable, Game Theory: 2-person 0-sum games
    • Sep 30: Game Theory: Maxmin, Minmax problems, Dominant strategies, Saddle point
  • Week 7
    • Oct 3: Game Theory: Graphical Method, LP method
    • Oct 5: Game Theory: Duality interpretations, Minmax theorem, Nash equilibrium, Review, Transportation Problem: LP formulation
    • Oct 7: Transportation Problem: Initial Basic Feasible Solution, Northwest rule, Vogel and Russell rules
  • Week 8
    • Oct 10: Transportation Simplex Method: Loop, Degeneracy, Iterations
    • Oct 12: Transportation Simplex Method: Reasoning for optimality, integral solutions property, unbalanced transportation problem
    • Oct 14: Assignment Problem: Formulation, Unbalanced case, Intro to the Hungarian Method
  • Week 9
    • Oct 17: Midterm, Time: 1-1:50pm (usual class hours)
      Venue: 103 Transportation Building and 217 Noyes Lab (seating chart posted in Compass2g)
    • Oct 19: Assignment Problem: Hungarian Method, Network Terminologies, Minimum Spanning Tree Problem: Prim's Algorithm
    • Oct 21: Shortest Path Problem: Dijkstra's Algorithm
  • Week 10
    • Oct 24: Max Flow Problem: Augmenting Path Algorithm
    • Oct 26: Dynamic Programming: backward induction
    • Oct 28: Dynamic Programming: Bellman's principle
  • Week 11:
    • Oct 31: Dynamic Programming: Continuous states and decision variables
    • Nov 2: Dynamic Programming: Probabilistic
    • Nov 4: Dynamic Programming: Probabilistic, Nonlinear Optimization: Convex functions
  • Week 12
    • Nov 7: Nonlinear Optimization: Convex functions, Unconstrained single variable: Bisection Search
    • Nov 9: Nonlinear Optimization: Unconstrained single variable: Newton Search
    • Nov 11: Nonlinear Optimization: Unconstrained single variable: Golden Section Search, Unconstrained multi-variable: Gradient Search
  • Week 13
    • Nov 14: Midterm solutions
    • Nov 16: Nonlinear Optimization: Unconstrained multi-variable: Newton Search, Constrained multi-variable: Lagrangian
    • Nov 18: Nonlinear Optimization: Constrained multi-variable: KKT Conditions
  • Week 14: Thanksgiving Break (Nov 21, 23, 25)
  • Week 15
    • Nov 28: Integer Programming: Formulations, Integer Variables
    • Nov 30: Integer Programming: Combinatorial Explosion, Variable Fixing, Branch and Bound
    • Dec 2: Integer Programming: LPs with Integral Solutions
  • Week 16
    • Dec 5: Discrete Optimization and Integer Programming
    • Dec 7: Review
  • Week 17
    • Final Exam
      Date: Wed, 14 Dec
      Time: 7--8pm
      Venue: 151 Loomis Laboratory