运筹(第八章动态规划)素材.ppt

《运筹(第八章动态规划)素材.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/7/221运筹学OPERATIONSRESEARCH2021/7/222第八章动态规划多阶段决策最优化问题举例基本概念、基本方程与最优化原理离散确定性动态规划求解离散随机性动态规划求解一般数学规划模型的动态规划解法2021/7/223§1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110637512021/7/224用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路

2、径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。2021/7/225讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶

3、段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D2106106EE2021/7/226第三阶段：有三个始点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的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111

4、D2D2D12021/7/227第二阶段：有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的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+

5、11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C32021/7/228第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1412B42021/7/229以上计算过程及结果，可用图2表示，可以看到，以

6、上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314141275122021/7/2210例2资源分配问题设有某种机器数台，用于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的；A、B两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最大?假设第k年年初完好机器数是SK，用于A生产的机器数是XK，则用于B生产的机器数是（SK-

7、XK）；用于A工作的设备的完好率是：a%，用于B工作的设备的完好率是：b%。则下一年初的完好机器数是SK+1=a%XK+b%（SK-XK）第k年的收益：h(XK)+g(SK-XK)2021/7/2211例3背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第I种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2

8、x2+…+wnxn≤Wx1,x2,…,xn0且为整