《运筹学》课程教学课件（PPT讲稿）第八章 动态规划

第八章动态规划$1多阶段决策最优化问题举例$2基本概念、基本方程与最优化原理$3离散确定性动态规划求解$4离散随机性动态规划求解s5一般数学规划模型的动态规划解法2023/1/20

第八章 动态规划 §1 多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解 §4 离散随机性动态规划求解 §5 一般数学规划模型的动态规划解法 2023/1/20 2

$1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最2B2短路径。10BBC2023/1/20

§1 多阶段决策过程最优化问题举例 例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的 最 短路径。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 3 7 5 1 2023/1/20 3

用穷举法的计算量：如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行（k+1）3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。2023/1/20

用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3 k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3 k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比较 的次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次， 比较 1.3726075472977×1014 次。若用1亿次/秒的计算机计 算需要约508天。 2023/1/20 4

讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从D；、Ci、B;A到E的最短路径问题。第四阶段：两个始点D,和D，，终点只有一个：表-1阶段4本阶段始点到E的最短距离本阶段最优终点本阶段各终点（决策）(状态)(最优决策)EDi10E10*66ED2分析得知：从D,和D,到E的最短路径唯一。2023/1/20

讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质 完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、 A到E的最短路径问题。 ￾￾￾￾￾￾￾￾第四阶段：两个始点D1和D2，终点只有一个； ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾表-1 分析得知：从D1和D2到E的最短路径唯一。 ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾阶段4 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 （最优决策) ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾E ￾￾￾￾￾￾￾￾￾D1 D2 ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾10* 6 ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾10 6 ￾￾￾￾￾￾￾￾￾￾￾￾￾E E 2023/1/20 5

第三阶段：有三个始点C，C,，C，终点有D,，D,，对始点和终点进行分析和讨论分别求Cj，C2，C,到Dr，D2的最短路径问题：表-2阶段3本阶段始点本阶段最优终点本阶段各终点（决策）到E的最短距离(状态)(最优决策)DiD2Ci12D28+10=186+6=12C211D27+10=175+6=11C311Di1+10=11 6+6=12分析得知：女如果经过C,则最短路为C,-D,-E;如果经过C2，则最短路为C-D2-E;如果经过C3，则最短路为C3-D,-E。2023/1/20

第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表-2 分析得知：如果经过C1，则最短路为C1 -D2 -E； 如果经过C2，则最短路为C2 -D2 -E； 如果经过C3，则最短路为C3 -D1 -E。 ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾阶段3 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 ￾￾￾￾￾￾D （最优决策) 1 ￾￾￾￾￾D2 ￾￾￾￾￾￾￾￾￾C1 C2 C3 ￾￾￾8+10=18 7+10=17 1+10=11 ￾￾￾￾6+6=12 5+6=11 6+6=12 ￾￾￾￾￾￾￾￾￾￾￾￾12 11 11 ￾￾￾￾￾￾￾￾￾￾￾￾￾D2 D2 D1 2023/1/20 6

第二阶段：有4个始点B,,B2,B3,B4，终点有C,C2,C3。对始点和终点进行分析和讨论分别求B,B,B,,B到C,C2,C，的最短路径问题：表-3阶段2本阶段各终点（决策）本阶段始点本阶段最优终到E的最点（最优决策（状态）C1C2C3短距离2Bi2+12=141+11=126+11=1712 C2B213Cs4+12=167+11=182+11=13CB3144+12=168+11=193+11=14B4127+12=195+11=16C31+11=12分析得知：如果经过B,，则走B,-C,-D,-E;如果经过B,，则走B,-C,-D,-E；如果经过B3，则走B3-C3-D-E;如果经过B4，则走B-C-D,-E。2023/1/20

第二阶段：有4个始点B1 ,B2 ,B3 ,B4，终点有C1 ,C2 ,C3。对始点和 终点进行分析和讨论分别求B1 ,B2 ,B3 ,B4到C1 ,C2 ,C3 的最短路 径问题： 表-3 分析得知：如果经过B1，则走B1 -C2 -D2 -E； 如果经过B2，则走B2 -C3 -D1 -E； 如果经过B3，则走B3 -C3 -D1 -E； 如果经过B4，则走B4 -C3 -D1 -E。 ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾阶段2 本阶段始点 （状态） ￾￾￾￾￾￾￾￾￾￾￾￾￾￾本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点（最优决策 ) ￾￾￾￾￾￾C1 ￾￾￾￾￾C2 ￾￾￾￾￾￾C3 ￾￾￾￾￾￾￾￾￾B1 B2 B3 B4 ￾￾￾2+12=14 4+12=16 4+12=16 7+12=19 ￾￾￾1+11=12 7+11=18 8+11=19 5+11=16 ￾￾6+11=17 2+11=13 3+11=14 1+11=12 ￾￾￾￾￾12 13 14 12 ￾￾￾￾￾￾￾￾￾￾C2 C3 C3 C3 2023/1/20 7

第一阶段：只有1个始点A，终点有B,,B,,B,,B。对始点和终点进行分析和讨论分别求A到B,,B,,B,,B,的最短路径问题：表10-4阶段1本阶段各终点（决策）本阶段始本阶段最优终到E的最点(状态)点(最优决策)短距离BiB2B3B4A12C24+12=163+13=163+14=172+12=14最后，可以得到：从A到E的最短路径为ABC,D,□E2023/1/20

第一阶段：只有1个始点A，终点有B1 ,B2 ,B3 ,B4 。对始点和终 点进行分析和讨论分别求A到B1 ,B2 ,B3 ,B4的最短路径问题： 表10-4 最后，可以得到：从A到E的最短路径为A￾ B4￾ C3￾ D1￾ E ￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾￾阶段1 本阶段始 点(状态) ￾￾￾￾￾￾￾￾￾￾￾￾￾￾本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点(最优决策) ￾￾￾￾￾￾B1 ￾￾￾￾￾B2 ￾￾￾￾￾￾B3 ￾￾￾￾￾B4 ￾￾￾￾￾￾￾A 4+12=16 3+13=16 3+14=17 2+12=14 ￾￾￾￾￾12 ￾￾￾￾￾￾￾￾￾￾C2 2023/1/20 8

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。12]国B8101014[13o11AB2?B?8GB?614B12以上过程，仅用了22次加法，计算效率远高于穷举法。2023/1/20

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 4 8 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 12 7 5 1 2 2023/1/20 9

例2资源分配问题设有某种机器数台，用于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的；A、B两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最大？假设第k年年初完好机器数是Sk，用于A生产的机器数是Xk，则用于B生产的机器数是（Sk-Xk）；用于A工作的设备的完好率是：a%，用于B工作的设备的完好率是：b%。则下一年初的完好机器数是Sk+i= a% Xk+ b% (Sk- Xk)第k年的收益：h(Xk)+ g(Sk- Xk)2023/1/2010

例2 资源分配问题 设有某种机器数台，用于完成两类工作A，B。由于机 器使用后有一定的损坏率，所以每年初的机器数量是变化 的；A、B两项工作产生的收益也不同。如何合理的分配机 器的使用，可使得三年的总收益最大? 假设第k年年初完好机器数是SK，用于A生产的机器数 是XK，则用于B生产的机器数是（SK - XK）； 用于A工作的设备的完好率是：a%，用于B工作的设备 的完好率是：b%。则下一年初的完好机器数是 SK+1= a% XK+ b% （SK - XK） 第k年的收益： h(XK )+ g(SK - XK ) 2023/1/20 10

例3背包问题设有n种物品，每一种物品数量无限。第种物品每件重量为w公斤，每件价值c元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设x为第种物品装入背包的件数（i=1,2，.，n），背包中物品的总价值为z，则Max z = CiX,+C2X2+ ... +CXns.t. Wix+w2x+...+w.x.WX,×2，….,X,0且为整数。2023/1/201

例3 背包问题 设有n种物品，每一种物品数量无限。第i种物品每件 重量为wi公斤，每件价值ci元。现有一只可装载重量为W 公斤的背包，求各种物品应各取多少件放入背包，使背 包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种 物品装入背包的件数（i =1, 2, ., n），背包中物品的总 价值为z，则 Max z = c1 x1 +c2 x2 + . +cn xn s.t. w1 x1 +w2 x2 +.+wn xn ≤W x1 , x2 , ., xn￾ 0且为整数。 2023/1/20 11