第二阶段：有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