The University of Iowa 56:171 O perations R esearch Fall Semester 2002

The Hypercard stacks 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.

Note: The notations (1)pdf, (2)pdf and (8)pdf indicate ONE, TWO and EIGHT screens per page, respectively.

(NOTE: It is unlikely that all of these stacks will be presented in lectures! Those which have presented will be highlighted in green. )

• Course organization, text, etc. (1).pdf
• Solving Systems of Linear Equations (1).pdf, (2).pdf or (4).pdf
• 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 (1).pdf, (2).pdf, or (8).pdf
  • More LP Formulations (1).pdf, (2).pdf, or (8).pdf
  • Introduction to the Simplex Method (1).pdf, (2).pdf, or (8).pdf following a path, vertex to vertex
  • The Simplex Method (1).pdf, (2).pdf, or (8).pdf
  • Initial BFS (basic feasible solution) for Simplex Method (1).pdf, (2).pdf, or (8).pdf
  • Further Simplex Examples (1).pdf, (2).pdf, or (8).pdf
  • Revised Simplex Method (1).pdf, (2).pdf, or (8).pdf maintains inverse of basis matrix, not full tableau
    • Example #1 (phase II only) (1).pdf or (4).pdf
    • Example #2 (both phases I & II (1).pdf or (4).pdf
    • Efficiency of the Revised Simplex Method (1).pdf, (2).pdf, or (8).pdf
  • Linear Programming Duality Theory (1).pdf, (2).pdf, or (8).pdf
  • Short quiz on LP (1).pdf, (2).pdf, or (8).pdf
  • Sensitivity Analysis, Part 1 (1).pdf, (2).pdf, or (8).pdf effect of rhs or cost coefficient changes
  • Sensitivity Analysis, Part 2 (1).pdf, (2).pdf, or (8).pdf examples with LINDO
  • Parametric Programming on the Right-hand-side (1).pdf, (2).pdf, or (8).pdf
  • Example:Lizzie's Dairy (LP model) (1).pdf, (2).pdf, or (8).pdf
  • Data Envelopment Analysis (DEA), LP-based technique for evaluating unit efficiencies (1).pdf, (2).pdf, or (8).pdf
  • Upper-Bounding Technique , handles upper bound on variables without adding rows (1).pdf, (2).pdf, or (8).pdf
  • Dual Simplex Method (1).pdf, (2).pdf, or (8).pdf
  • LP with Multiple Objectives (1).pdf, (2).pdf, or (8).pdf
  • Interior-point method (Path-following) unlike simplex method, follows path through interior(1).pdf, (2).pdf, or (8).pdf
  • Example: Path-following method (1).pdf, (2).pdf, or (8).pdf
    
• 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 (1).pdf, (2).pdf, or (8).pdf
  • Assignment Problem (1).pdf, (2).pdf, or (8).pdf
  • Airline Crew Assignment (1).pdf, (2).pdf, or (8).pdf (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 (1).pdf, (2).pdf, or (8).pdf activity-on-arrow (AOA) and activity-on-node (AON)
  • Critical Path Method (CPM) (1).pdf, (2).pdf, or (8).pdf assumes task durations to be known with certainty
  • Project Evaluation & Review Technique (PERT) (1).pdf, (2).pdf, or (8).pdf allows random durations
  • "Crashing" a Project (1).pdf, (2).pdf, or (8).pdf allocating additional resources to reduce completion time
    
• Decision Analysis
  • Part One (1).pdf, (2).pdf, or (8).pdf
  • Part Two (1).pdf, (2).pdf, or (8).pdf introduction to decision trees
  • Part Three (1).pdf, (2).pdf, or (8).pdf incorporating new information in a decision tree: Bayes' Rule
  • Example: the "Mole" (1).pdf
    
• 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 (1).pdf, (2).pdf, or (8).pdf
  • ILP Models Part I (1).pdf, (2).pdf, or (8).pdf
  • ILP Models Part II (1).pdf, (2).pdf, or (8).pdf
    
• Stochastic Processes (1).pdf, (2).pdf or (8).pdf
  • Bernouilli & Related Processes (1).pdf, (2).pdf or (8).pdf 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 (1).pdf, (2).pdf or (8).pdf 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 (1).pdf, (2).pdf, or (8).pdf
    • (Another introduction) (1).pdf, or (4).pdf
    • Classification of Markov Chains (1).pdf, (2).pdf, or (8).pdf
    • Examples of Markov Chain Models
      • Failure & Repair of Parallel Machines (1).pdf, (2).pdf, or (8).pdf (steady-state analysis)
      • Geriatric Ward (1).pdf, (2).pdf, or (8).pdf (absorption analysis)
      • (s,S) Inventory System (1).pdf, (2).pdf, or (8).pdf (steady-state analysis)(1).pdf, or (4).pdf
      • Labatt Brewery (1).pdf, (2).pdf, or (8).pdf (pallet repair policy)
      • Summer weather (1).pdf, (2).pdf, or (8).pdf (multiple state variables)
      • Mfg. System with scrap & rework (1).pdf, (2).pdf, or (8).pdf (absorption analysis)
      • Rat in a maze(1).pdf
      • Auto insurance premium (1).pdf
      • Monopoly--the game (1).pdf
      • Miscellaneous Markov Chain Examples (1).pdf, (2).pdf, or (8).pdf
        
  • Continuous-Time Markov Chains (1).pdf, (2).pdf, or (8).pdf
    • Birth-Death Processes (see previous stack)
    • Markovian Queueing Models (1).pdf, (2).pdf or (8).pdf
      • M/M/1 (1).pdf, (2).pdf, or (8).pdf (single server)
      • M/M/c (1).pdf, (2).pdf, or (8).pdf (# servers=c>1, i.e., multi-servers but single queue)
      • M/M/1/N (1).pdf, (2).pdf, or (8).pdf (single server, finite capacity)
      • M/M/1/N/N (1).pdf, (2).pdf, or (8).pdf (single server, finite source)
      • M/G/1 (1).pdf, (2).pdf, or (8).pdf (general service-time distribution)
      • Non-exponential queues(inter-arrival time &/or service times
        having non-exponential distributions) (1).pdf, (2).pdf, or (8).pdf
      • Queue with "removable" server (1).pdf, (2).pdf, or (8).pdf
      • Erlang-k service time (1).pdf, (2).pdf, or (8).pdf
      • Queue with bulk arrivals (1).pdf, (2).pdf, or (8).pdf
      • Tandem servers with blocking (1).pdf or (8).pdf
      • Networks of queues Part 1 (1).pdf, (2).pdf, or (8).pdf
      • Networks of queues Part 2 (1).pdf, (2).pdf, or (8).pdf
      • Quiz: (1).pdf, (2).pdf, or (8).pdf
    • Modeling exercises (1).pdf or (8).pdf
      
• Dynamic Programming
  • Index (1).pdf, (2).pdf or (8).pdf
  • Deterministic DP Models
    • Prototype DP Model (1).pdf, (2).pdf or (8).pdf (transitions & payoffs given in tabular form)
    • Knapsack problem (1).pdf, (2).pdf or (8).pdf
    • Deterministic production planning (1).pdf, (2).pdf or (8).pdf
    • Powerplant capacity planning (1).pdf, (2).pdf or (8).pdf
    • Nim "game of matches" (1).pdf, (2).pdf or (8).pdf (remove matches from pile, avoid last match)
    • Deterministic machine replacement (1).pdf or (4).pdf
    • Optimal redundancy to achieve reliability (1).pdf, (2).pdf or (8).pdf
    • Political redistricting (1).pdf, (2).pdf or (8).pdf (assign multiple representatives to districts)
    • Two-dimensional Knapsack Problem (1).pdf or (8).pdf (includes both weight & volume constraints, requiring two state variables)
  • Stochastic DP Models
    • Stochastic machine replacement (1).pdf, (2).pdf or (8).pdf
    • Stochastic production planning (1).pdf, (2).pdf or (8).pdf (single product with production setup cost, random demand, & backordering)
    • Casino problem (1).pdf, (2).pdf or (8).pdf (maximizing the probability of an outcome)
    • Lotsize problem (1).pdf or (4).pdf (determine lotsize when excessive defects may require re-ordering)
    • Quiz show problem (1).pdf, or (4).pdf (should the quiz show contestant continue to the next stage, or quit and keep her earnings?)
    • Stochastic production planning with two products (1).pdf or (4).pdf (single machine is devoted to one product each day)

to 56:171 home page.

Last modified: 2 December 2002