Return to Index
Operations Research Models and Methods
 
Computation Section
Subunit Dynamic Programming Collection
- Examples

The best way to learn about DP models is to review examples. I have created several examples that are described in the following pages. Download the data file for an example and click the link for a discussion. In many cases the worksheet contains formulas and numbers to implement the various model components. It is helpful to have the worksheet open and review cell contents with the formula bar of Excel.
 
Model Solution Data File Description
Cab Cab dp_cab.xls

A small model from Howard

Baseball Baseball dp_baseball.xls

A model of an inning of baseball (Howard )

Replacement Replacement dp_replace.xls

An equipment replacement problem (Howard )

Sequence Sequence dp_well_sequence.xls Sequencing well drilling (Bickel)
Birth-Death Birth-Death dp_birth_death.xls

Birth-Death Processes
Investment
(In DP Models) 		  dp_investment.xls

Investment Problem (Deterministic DP)
The discussion is in the Models section

Queue Queue dp_book.xls A MDP model to determine the optimum number of servers, where the decision depends on the state
Doors Doors doors.xls A MDP model structured on the random walk problem where the action is to block movement out of a state (Dimitrov and Morton)

Inventory
(in DP Data)

DDP

MDP

DTMC

CTMC

 dp_inventory_repl.xls An inventory problem with holding, backorder, excess inventory, shortage and replenishment costs. Lead time is 1 time unit. All four model types are illustrated.
Revenue Management MDP dp_revenue.xls A problem in revenue management
Resources
(in DP Data)
 DDP dp_resource.xls A deterministic DP model with stages
Log Gambler MDP dp_ln_gambler.xls A finite approximation of an infinite DP model. Uses noninteger steps and final values.
 

All except the Cab problem have models generated by the DP Models add-in. The model parameters are below.

 

 
Problem
State Variables
Action Variables
Event Variables
State Blocks
Decision Blocks
Transition Blocks
Cab - MDP
x
x
x
x
x
x
Baseball  - MDP
4
1
1
2
8
26
Replacement - MDP
1
1
1
1
1
5
Sequence - MDP
6
1
1
0
2
1
Birth-Death-MC
1
0
2
1
0
3
Birth-Death-MDP
1
1
2
1
3
3
Investment - DDP
2
1
0
2
0
1
Queue - MDP
2
1
1
0
2
2
Doors - MDP
2
1
1
3
0
0
Inventory - DDP
2
2
0
2
2
2
Inventory - MDP
1
2
1
0
2
2
Inventory - DTMC
1
0
1
0
0
2
  The parameters of the lists used by the DP Solver add-in are below.
 
Problem
States
Actions
Events
Decisions
Transitions
Cab - MDP
3
3
3
6
27
Baseball  - MDP
33
5
14
78
402
Replacement - MDP
40
41
2
1640
3239
Sequence - MDP
729
7
2
2188
3646
Birth-Death - DTMC
11
0
2
0
32
Birth-Death-MDP
11
2
2
16
47
Investment - DDP
100
5
0
372
372
Queue - MDP
55
3
3
143
416
Doors - MDP
17
5
4
73
227
Inventory - DDP
861
12
0
5706
5706
Inventory - MDP
26
12
8
202
1616
Inventory - DTMC
26
0
8
0
208
 
  
Return to Top
tree roots

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved