1、管 理 运 筹 学第十章 动态规划1 多阶段决策过程最优化问题举例2 基本概念、基本方程与最优化原理3 动态规划的应用 (1)4 动态规划的应用 (2)1管 理 运 筹 学1 多阶段决策过程最优化问题举例例 1 最短路径问题下图表示从起点 A到终点 E之间各点的距离。求 A到 E的最短路径。BACBDBCDEC412312312322164724 8386756110637 512管 理 运 筹 学1 多阶段决策过程最优化问题举例用穷举法的计算量 :如果从 A到 E的站点有 k个，除 A、 E之外每站有 3个位置则总共有 3k-12条路径；计算各路径长度总共要进行 (k+1) 3k-12次加法
2、以及 3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加；例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。若用 1亿次 /秒的计算机计算需要约 508天。3管 理 运 筹 学1 多阶段决策过程最优化问题举例讨论：1、以上求从 A到 E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从 Di 、 Ci、 Bi、 A到 E的最短路径问题。第四阶段：两个始点 D1和 D2， 终点只有一个；表 10-1分析得知：从 D1和 D2到 E的最短路径唯一。阶 段 4本 阶 段始点
3、（状 态 ）本 阶 段各 终 点（决策） 到 E的最短距离 本 阶 段最 优终 点（最 优 决策 ) ED1D210*6106EE4管 理 运 筹 学第三阶段：有三个始点 C1， C2， C3，终点有 D1， D2，对始点和终点进行分析和讨论分别求 C1， C2， C3到 D1， D2 的最短路径问题：表 10-2分析得知：如果经过 C1， 则最短路为 C1-D2-E；如果经过 C2， 则最短路为 C2-D2-E；如果经过 C3，则最短路为 C3-D1-E。1 多阶段决策过程最优化问题举例阶 段 3本 阶 段始点（状 态 ）本 阶 段各 终 点（决策） 到 E的最短距离 本 阶 段最 优终 点
4、（最 优 决策 ) D1 D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D15管 理 运 筹 学第二阶段：有 4个始点 B1,B2,B3,B4，终点有 C1,C2,C3。对始点和终点进行分析和讨论分别求 B1,B2,B3,B4到 C1,C2,C3 的最短路径问题：表 10-3 分析得知：如果经过 B1，则走 B1-C2-D2-E；如果经过 B2，则走 B2-C3-D1-E；如果经过 B3，则走 B3-C3-D1-E；如果经过 B4，则走 B4-C3-D1-E。1 多阶段决策过程最优化问题举例阶 段 2本 阶 段始点（状 态 ）
5、本 阶 段各 终 点（决策） 到 E的最短距离本 阶 段最 优终 点（最 优决策 ) C1 C2 C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C36管 理 运 筹 学第一阶段：只有 1个始点 A，终点有 B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求 A到 B1,B2,B3,B4的最短路径问题：表 10-4最后，可以得到：从 A到 E的最短路径为 A B4 C3 D1 E1 多阶段决策过程最优化问题举例阶 段 1
6、本 阶 段始点 (状 态 )本 阶 段各 终 点（决策） 到 E的最短距离本 阶 段最 优终 点 (最 优 决策 ) B1 B2 B3 B4A 4+12=16 3+13=16 3+14=17 2+12=14 12 C27管 理 运 筹 学以上计算过程及结果，可用图 2表示，可以看到，以上方法不仅得到了从 A到 D的最短路径，同时，也得到了从图中任一点到 E的最短路径。以上过程，仅用了 22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724 83867516106010612111112131414127 5 121 多阶段决策过程最优化问题举例8管 理 运
7、筹 学一、基本概念：1、阶段 k： 表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态 sk： 能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策 xk： 从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为 xk(sk)。决策允许集合 Dk(sk)： 在状态 sk下，允许采取决策的全体。4、策略 Pk,n(sk)： 从第 k阶段开始到最后第 n阶段的决策序列，称 k子策略。 P1,n(s1)即为全过程策略。5、状态转移方程 sk+1=Tk(sk, xk)： 某一状态以及该状态下的决策，与下一状态之间的函数关系。2
8、 基本概念、基本方程与最优化原理9管 理 运 筹 学6、 阶段指标函数 vk(sk, xk)： 从状态 sk出发，选择决策 xk所产生的第 k阶段指标。过程指标函数 Vk,n(sk, xk, xk+1, xn)： 从状态 sk出发，选择决策xk,xk+1, , xn所产生的过程指标。动态规划要求过程指标具有可分离性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)称指标具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1,xk+1, , xn)称指标具有可乘性。二、基本方程：最优指标函数 fk(sk)： 从状态 sk出发，对所有的策略 Pk,n， 过程指标 Vk,n的最优值，即2 基本概念、基本方程与最优化原理10
