《运筹学》胡运权清华版-7-01动态规划

第七章动态规划多阶段决策问题动态规划的基本概念和基本原理动态规划模型的建立逆推解法与顺推解法动态规划应用举例

1ppt课件第一节多阶段决策问题2ppt课件多阶段决策问题在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的阶段，而每个阶段都需要做出决策，并且一个阶段的决策确定后，常影响下一阶段的决策，即多阶段决策问题。在这类多阶段决策问题中，整个问题的各个阶段所确定的决策构成一个决策序列，通称为策略。对应于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略，使在预定的标准下达到最好的效果。3ppt课件在多阶段决策问题中，阶段往往可用时段来表示，随着时间的推移，在每一时段上选择最恰当的决策，以期在整体上达到最优。动态规划是解决多阶段决策过程的方法。

R.Bellman50年代执教于普林斯顿和斯坦福大学，1957年发表“DynamicProgramming”一书，标识动态规划的正式诞生。

12n

状态决策状态决策状态状态决策4ppt课件AB1B2C1C2C3C4D1D2D3E1E2F542368778443548531356243123455阶段决策问题例4.最短路问题5ppt课件如何求解最短路问题？（1）最短路问题的特点：若A－>B1－>C2－>D2－>E2－>F

是从A到F的最短路，则必有B1－>C2－>D2－>E2－>F

是从B1到F的最短路，

C2－>D2－>E2－>F

是从C2到F的最短路，

D2－>E2－>F

是从D2到F的最短路，E2－>F

是从E2到F的最短路即：若某一点在最优路线上，那么从那一点到终点的最短路线也在最优路线上。6ppt课件（2）解决最短路问题的方法：

假设每一个点都在最优路线上，然后做相关计算。具体地：从最后阶段的两个始点E1和E2开始，由后向前，计算每一个点到F的最短路线，直到结点A，这时找到A到F的最短路。7ppt课件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485313562433

4

最短路问题的求解123458ppt课件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485313562433

4

5

7

5

123459ppt课件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485123

4

5

7

512

10

8

91234510ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54236877123

4

5

7

5

12

10

8

913

15

1234511ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54123

4

5

7

5

12

10

8

913

15

17

1234512ppt课件AB1B2C1C2C3C4D1D2D3E1E2F123

4

5

7

5

12

10

8

913

15

17

注：同时得到所有顶点到终点最短路。1234513ppt课件用动态规划求解最短路问题的思路将大问题分成结构相似的小问题，递推求解。14ppt课件最短路问题：AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题1——在第5阶段应怎样走，使得第5阶段初各起点E1、E2到终点F的路长最短？15ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题2——根据上一步的结果，在第4阶段应怎样走，使得第4阶段初各起点D1、D2、D3到终点F的路长最短？16ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题3——根据上一步的结果，在第3阶段应怎样走，使得第3阶段初各起点C1、C2、C3、C4到终点F的路长最短？17ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题4——根据上一步的结果，在第2阶段应怎样走，使得第2阶段初各起点B1、B2到终点F的路长最短？18ppt课件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题5——根据上一步的结果，在第1阶段应怎样走，使得第1阶段初起点A到终点F的路长最短？即为所求！19ppt课件例:W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。20ppt课件A3B14C13D14532B22C23D24E11234C34D35E2