Start/Finish Examples DP Data DP Models DP Solver

 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

Operations Research Models and Methods
Internet
by Paul A. Jensen