文档介绍：Approximate Dynamic Programming for
Operations Research:
Solving the curses of dimensionality
Warren B. Powell
May 2, 2005
(c) Warren B. Powell, 2005 All rights reserved.
Department of Operations Research and Financial Engineering
Princeton University, Princeton, NJ 08544
Contents
1 The challenges of dynamic programming 1
A dynamic programming example: a shortest path problem . . . . . . . . . . 2
The three curses of dimensionality . . . . . . . . . . . . . . . . . . . . . . . . 3
Some real applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Problem classes in asset management . . . . . . . . . . . . . . . . . . . . . . 8
What is new in this book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
The many dialects of dynamic programming . . . . . . . . . . . . . . . . . . 12
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Some illustrative applications 15
Deterministic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
The budgeting problem . . . . . . . . . . . . . . . . . . . . . . . . . . 15
The shortest path problem . . . . . . . . . . . . . . . . . . . . . . . . 17
Stochastic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
The gambling problem . . . . . . . . . . . . . . . . . . . . . . . . . . 19
The batch replenishment problem . . . . . . . . . . . . . . . . . . . . 21
The secretary problem . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Optimal stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Modeling dynamic programs 32
Notational style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
i
CONTENTS ii
Modeling time . . . . . . . . . . . . . . . . . . . . . . . . . .