文档介绍：Session 10 运筹学Operations Research 10-1
运筹学运筹学
Operations Research Operations Research 10 Dynamic Programming
A Prototype example for dynamic
programming
10 Dynamic Programming Characteristics of dynamic programming
Deterministic Dynamic Programming
Probabilistic Dynamic Programming
Conclusions
江西财经大学信息管理学院©2006 江西财经大学信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006 1 School of Information Technology, JiangXi University of Finance & Economics©2006 2
运筹学运筹学
Operations Research 10 Dynamic Programming Operations Research A Prototype example
A Prototype example for dynamic B 3 E
programming 4 1
6 4
Example 1----The Stagecoach Problem
2 H
There was a mythical fortune seeker in Missoui who decided 3 6 3
to go west to join the gold rush in California during the mid-19th 2 F
4 C
century. The journey would require traveling by marauders. A 4 3
Although his starting point and destination were serious danger of J
attack by marauders. Although his starting point and destination 3 4
were fixed, he had considerable choice as to which states to travel
4 I
through en route. The possible routes are shown , where each 1 3
state is represented by a circled letter and the direction of travel is 3
always from left to right in the diagram. Thus four stages were D 5 G
required to travel from his point of embarkation in sate A to his
destination in state J.
江西财经大学信息管理学院©2006 江西财经大学信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006 3 School of Information Technology, JiangXi University of Finance & Economics©2006 4
运筹学运筹学
Operations Research A Prototype example Operations Research A Prototype example
¾ The cost for the standard policy on the stagecoach run from
This fortune seeker was a prudent man who was quite state I to state j, which will be denoted by cij.
¾ We shall now focus