管理运筹学（第三版）第十章.ppt

253管理运筹学第十章动态规划§1§2§3§4多阶段决策过程最优化问题举例基本概念、基本方程与最优化原理动态规划的应用(1)动态规划的应用(2)254管理运筹学§1 -1 表示从起点A 到终点E 之间各点的距离。求A 到E 的最短路径。图10-1255管理运筹学§1 多阶段决策过程最优化问题举例穷举法的计算量:如果从A 到E 的站点有k 个,包括A、E 两个站点,除A、E 之外每站有3 个位置则总共有3k?2 条路径;计算各路径长度总共要进行(k?1)3k?2 次加法以及3k?2?1 次比较。随着k 值的增加,需要进行的加法和比较的次数将迅速增加;例如当k=20 时,要做七亿二千五百多万次加法,要做三千八百多万次比较。256管理运筹学§1 多阶段决策过程最优化问题举例讨论:以上求从A 到E 的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从Di、Ci、Bi、A 到E 的最短路径问题。第四阶段:两个始点D1 和D2,终点只有一个。表10-1阶段4本阶段始点(状态)本阶段各终点(决策)E到E 的最短距离本阶段最优终点(最优决策)D1D2106106EE分析得知:从D1 和D2 到E 的最短路径唯一。257管理运筹学§1 多阶段决策过程最优化问题举例第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点和终点进行分析和讨论分别求C1,C2,C3 到D1,D2 的最短路径问题。表10-2阶段3本阶段始点(状态)本阶段各终点(决策)D1 D2到E 的最短距离本阶段最优终点(最优决策)C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1分析得知:如果经过C1,则最短路为C1-D2-E;如果经过C2,则最短路为C2-D2-E;如果经过C3,则最短路为C3-D1-E。258管理运筹学§1 多阶段决策过程最优化问题举例第二阶段:有四个始点B1, B2, B3, B4,终点有C1, C2, C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4 到C1,C2,C3 的最短路径问题。表10-3阶段2本阶段各终点(决策)本阶段始点到E 的最本阶段最优终点(状态)B1B2B3B4C12+12=144+12=164+12=167+12=19C21+11=127+11=188+11=195+11=16C36+11=172+11=133+11=141+11=12短距离12131412(最优决策)C2C3C3C3分析得知:如果经过B1,则走B1-C2-D2-E;如果经过B2,则走B2-C3-D1-E;如果经过B3,则走B3-C3-D1-E;如果经过B4,则走B4-C3-D1-E。259管理运筹学§1 多阶段决策过程最优化问题举例第一阶段:只有1 个始点A,终点有B1, B2, B3, B4。对始点和终点进行分析和讨论分别求A 到B1, B2, B3, B4 的最短路径问题。表10-4阶段1本阶段始点(状态)B1本阶段各终点(决策)B2 B3B4到E 的最短距离本阶段最优终点(最优决策)A4+12=163+13=163+14=172+12=1414B4最后,可以得到:从A 到E 的最短路径为A→B4→C3→D1→E 距离为14。260管理运筹学§1 多阶段决策过程最优化问题举例以上计算过程及结果,可用图10-2 表示,可以看到,以上方法不仅得到了从A 到D 的最短路径,同时,也得到了从图中任一点到E 的最短路径。图10-2以上过程,仅用了22 次加法,计算效率远高于穷举法。261管理运筹学§2 基本概念、基本方程与最优化原理一、:首先将问题的全过程适当地分成若干个互相联系的阶段,一般是根据时间与空间的自然特征去划分阶段。:状态是指每个阶段开始时所处的自然状况或客观条件,通常第n 阶段有若干个状态,我们用状态变量sn 来描述。:决策是某一阶段内的抉择,第n 阶段的决策与第n 个阶段的状态有关,通常用xn(sn)表示第n 阶段处于sn 状态时的决策变量,而这个决策又决定了第n +1 阶段的状态。:由所有各阶段的决策组成的决策函数序列成为全过程策略,记为P1, n (sk)从第k 阶段开始到最后第n 阶段的决策函数序列,称k 子策略,记为Pk,n (sk) 。:指标函数是衡量全过程策略或k 子过程策略优劣的数量指标,记为f1 (s1)或fk (sk)。终点条件:fn ?1 (sn ?1 ) ??§2 基本概念、基本方