《《运筹学》胡运权清华版-7-01动态规划.ppt》由会员分享，可在线阅读，更多相关《《运筹学》胡运权清华版-7-01动态规划.ppt（23页珍藏版）》请在三一办公上搜索。
1、第七章 动 态 规 划,多阶段决策问题动态规划的基本概念和基本原理动态规划模型的建立逆推解法与顺推解法动态规划应用举例,第一节 多阶段决策问题,多阶段决策问题,在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的阶段，而每个阶段都需要做出决策，并且一个阶段的决策确定后，常影响下一阶段的决策，即多阶段决策问题。,在这类多阶段决策问题中，整个问题的各个阶段所确定的决策构成一个决策序列，通称为策略。对应于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略，使在预定的标准下达到最好的效果。,在多阶段决策问题中，阶段往往可用时段来表示，随
2、着时间的推移，在每一时段上选择最恰当的决策，以期在整体上达到最优。动态规划是解决多阶段决策过程的方法。,5阶段决策问题,例4.最短路问题,如何求解最短路问题？,（1）最短路问题的特点：若 A B1 C2 D2 E2F 是从A到F的最短路，则必有 B1 C2 D2 E2F 是从B1到F的最短路，C2 D2 E2F 是从C2到F的最短路，D2 E2F 是从D2到F的最短路，E2F 是从E2到F的最短路 即：若某一点在最优路线上，那么从那一点到终点的最短路线也在最优路线上。,（2）解决最短路问题的方法：假设每一个点都在最优路线上，然后做相关计算。具体地：从最后阶段的两个始点E1和E2开始，由后向前，
3、计算每一个点到F的最短路线，直到结点A，这时找到A到F的最短路。,最短路问题的求解,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,5,4,2,3,6,8,7,7,1,2,4,5,7,5,12,10,8,9,注：同时得到所有顶点到终点最短路。,用动态规划求解最短路问题的思路 将大问题分成结构相似的小问题，递推求解。,最短路问题：,子问题1在第5阶段应怎样走，使得第5阶段初各起点E1、E2到终点F的路长最短？,子问题2根据上一步的结果，在第4阶段应怎样走，使得第4阶段初各起点D1、D2、D3到终点F的路长最短？,子问题3根据上一步的结果，在第3阶段应怎样走，使得第3阶段
4、初各起点C1、C2、C3、C4到终点F的路长最短？,子问题4根据上一步的结果，在第2阶段应怎样走，使得第2阶段初各起点B1、B2到终点F的路长最短？,子问题5根据上一步的结果，在第1阶段应怎样走，使得第1阶段初起点A到终点F的路长最短？即为所求！,例:W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。,A 3 B1 4 C1 3 D1,4 5 3 2,B2 2 C2 3 D2 4 E1,1 2 3 4,C3 4 D3 5 E2 2 F,A,B1,B2,C1,C2,C3,D1,D2,D3,E1,E2,F,4,1,5,4,4,4,4,5,3,3,3,3,3,2,2,2,2,A,B,C,D,E,F,第一节 结束,
