Operations Research Lecture Slides

The University of Iowa

O perations R esearch

Instructor: Dennis L. Bricker

The slides used in presentation of the lectures are available for downloading in .pdf (Portable Document Format). These were produced by Adobe Acrobat. You may read them using an Adobe Acrobat Reader on either Macintosh, PC, or UNIX platform, which may be freely downloaded from Adobe's web site. Each set of slides is available as one slide per page (denoted by One/Page) or as several slides per page (HANDOUT).

List of Lecture Slides

Course organization, text, etc. One/Page
Solving Systems of Linear Equations One/Page or HANDOUT
Linear Programming: optimization of a linear function of several variables, with the restriction that these variables satisfy certain linear equations or inequalities.
- Formulating LP Models One/Page or HANDOUT
- More LP Formulations One/Page or HANDOUT
- Introduction to the Simplex Method One/Page or HANDOUT following a path, vertex to vertex
- The Simplex Method One/Page or HANDOUT
- Initial BFS (basic feasible solution) for Simplex Method One/Page or HANDOUT
- Further Simplex Examples One/Page or HANDOUT
- Revised Simplex Method One/Page or HANDOUT maintains inverse of basis matrix, not full tableau
  - Example #1 (phase II only) One/Page or HANDOUT
  - Example #2 (both phases I & II One/Page or HANDOUT
  - Efficiency of the Revised Simplex Method One/Page or HANDOUT
- Linear Programming Duality Theory One/Page or HANDOUT
- Short quiz on LP One/Page or HANDOUT
- Sensitivity Analysis, Part 1 One/Page or HANDOUT effect of rhs or cost coefficient changes
- Sensitivity Analysis, Part 2 One/Page or HANDOUT examples with LINDO
- Parametric Programming on the Right-hand-side One/Page or HANDOUT
- Example:Lizzie's Dairy (LP model) One/Page or HANDOUT
- Data Envelopment Analysis (DEA), LP-based technique for evaluating unit efficiencies One/Page or HANDOUT
- Upper-Bounding Technique , handles upper bound on variables without adding rows One/Page or HANDOUT
- Dual Simplex Method One/Page or HANDOUT
- LP with Multiple Objectives One/Page or HANDOUT
- Interior-point method (Path-following) unlike simplex method, follows path through interiorOne/Page or HANDOUT
- Example: Path-following method One/Page or HANDOUT
Transportation & Assignment Problems: special cases of linear programming, which may be solved more efficiently than by using a standard LP solver. They have the very desirable feature that (under certain conditions) the optimal solutions are guaranteed to have only integer values of the variables!
- Transportation problem One/Page or HANDOUT
- Assignment Problem One/Page or HANDOUT
- Airline Crew Assignment One/Page or HANDOUT (example of assignment problem)
Project Scheduling: finding the shortest completion time of a large and complex project requiring the completion of many tasks, some of which require the completion of other tasks before they can be begun.
- Project Networks One/Page or HANDOUT activity-on-arrow (AOA) and activity-on-node (AON)
- Critical Path Method (CPM) One/Page or HANDOUT assumes task durations to be known with certainty
- Project Evaluation & Review Technique (PERT) One/Page or HANDOUT allows random durations
- "Crashing" a Project One/Page or HANDOUT allocating additional resources to reduce completion time
Decision Analysis
- Part One One/Page or HANDOUT
- Part Two One/Page or HANDOUT introduction to decision trees
- Part Three One/Page or HANDOUT incorporating new information in a decision tree: Bayes' Rule
- Example: the "Mole" One/Page
Integer Programming Model Formulation: Often, in linear programming problems, it is necessary that some or all of the variables have discrete values in the optimal solution.
- Introduction One/Page or HANDOUT
- ILP Models Part I One/Page or HANDOUT
- ILP Models Part II One/Page or HANDOUT
Stochastic Processes One/Page or HANDOUT
- Bernouilli & Related Processes One/Page or HANDOUT random events occur at discrete points in time
  - Bernouilli Distribution (Xn=0 or 1)
  - Binomial Distribution (# events in n stages)
  - Geometric Distribution (time until first event)
  - Pascal Distribution (time until k-th event)
- Poisson Process One/Page or HANDOUT random events, e.g., arrivals, may occur at any point in time
  - Poisson Distribution (# events in interval [0,T] )
  - Exponential Distribution (time until first event, e.g., interarrival time)
  - Erlang-k Distribution (time until k-th event)
  - Exercises
- Discrete-Time Markov Chains
  - Introduction One/Page or HANDOUT
  - (Another introduction) One/Page or HANDOUT
  - Classification of Markov Chains One/Page or HANDOUT
  - Examples of Markov Chain Models
    - Failure & Repair of Parallel Machines One/Page or HANDOUT (steady-state analysis)
    - Geriatric Ward One/Page or HANDOUT (absorption analysis)
    - (s,S) Inventory System One/Page or HANDOUT
    - (s,S) Inventory System steady-state analysis One/Page or HANDOUT
    - Labatt Brewery One/Page or HANDOUT (pallet repair policy)
    - Summer weather One/Page or HANDOUT (multiple state variables)
    - Mfg. System with scrap & rework One/Page or HANDOUT (absorption analysis)
    - Rat in a maze One/Page
    - Auto insurance premium One/Page
    - Monopoly--the game One/Page
    - Miscellaneous Markov Chain Examples One/Page or HANDOUT
- Continuous-Time Markov Chains One/Page or HANDOUT
  - Birth-Death Processes (see previous stack)
  - Markovian Queueing Models One/Page or HANDOUT
    - M/M/1 One/Page or HANDOUT (single server)
    - M/M/c One/Page or HANDOUT (# servers=c>1, i.e., multi-servers but single queue)
    - M/M/1/N One/Page or HANDOUT (single server, finite capacity)
    - M/M/1/N/N One/Page or HANDOUT (single server, finite source)
    - M/G/1 One/Page or HANDOUT (general service-time distribution)
    - Non-exponential queues(inter-arrival time &/or service times
      having non-exponential distributions) One/Page or HANDOUT
    - Queue with "removable" server One/Page or HANDOUT
    - Erlang-k service time One/Page or HANDOUT
    - Queue with bulk arrivals One/Page or HANDOUT
    - Tandem servers with blocking One/Page or HANDOUT
    - Networks of queues Part 1 One/Page or HANDOUT
    - Networks of queues Part 2 One/Page or HANDOUT
    - Quiz: One/Page or HANDOUT
  - Modeling exercises One/Page or HANDOUT
Dynamic Programming
- Index One/Page or HANDOUT
- Deterministic DP Models
  - Prototype DP Model One/Page or HANDOUT (transitions & payoffs given in tabular form)
  - Knapsack problem One/Page or HANDOUT
  - Deterministic production planning One/Page or HANDOUT
  - Powerplant capacity planning One/Page or HANDOUT
  - Nim "game of matches" One/Page or HANDOUT (remove matches from pile, avoid last match)
  - Deterministic machine replacement One/Page or HANDOUT
  - Optimal redundancy to achieve reliability One/Page or HANDOUT
  - Political redistricting One/Page or HANDOUT (assign multiple representatives to districts)
  - Two-dimensional Knapsack Problem One/Page or HANDOUT (includes both weight & volume constraints, requiring two state variables)
- Stochastic DP Models
  - Stochastic machine replacement One/Page or HANDOUT
  - Stochastic production planning One/Page or HANDOUT (single product with production setup cost, random demand, & backordering)
  - Casino problem One/Page or HANDOUT (maximizing the probability of an outcome)
  - Lotsize problem One/Page or HANDOUT (determine lotsize when excessive defects may require re-ordering)
  - Quiz show problem One/Page or HANDOUT (should the quiz show contestant continue to the next stage, or quit and keep her earnings?)
  - Stochastic production planning with two products One/Page or HANDOUT (single machine is devoted to one product each day)

to O.R. main page.

http://www.engineering.uiowa.edu/~dbricker/or_slides.html

dennis-bricker@uiowa.edu

Last modified: 22 November 2010