许香敏最优化方法PPT学习教案

1、会计学1 许香敏最优化方法许香敏最优化方法 2 动态规划是运筹学的一个分支，是求解多阶段决策过动态规划是运筹学的一个分支，是求解多阶段决策过 程最优化问题的数学方法。程最优化问题的数学方法。 动态规划在经济管理、工程技术、工农业生产及军事动态规划在经济管理、工程技术、工农业生产及军事 部门中都有着广泛的应用，并且获得了显著的效果。部门中都有着广泛的应用，并且获得了显著的效果。 学习动态规划，我们首先要了解多阶段决策问题。学习动态规划，我们首先要了解多阶段决策问题。 第1页/共63页 3 最短路径问题最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从：给定一个交通

2、网络图如下，其中两点之间的数字表示距离（或运费），试求从A A点到点到G G点的最短距离（总运输费用最小）。点的最短距离（总运输费用最小）。 1234 56 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 第2页/共63页 4 背包问题背包问题 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a a 公斤，设有公斤，设有n n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人

3、应如何选择携带的物品（各几件），使所起作用（使用价值）最大？种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品物品 1 2 j n 重量（重量（公斤公斤/ /件件） a1 a2 aj an 每件使用价值每件使用价值 c1 c2 cj cn 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 第3页/共63页 5 生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地：企业在生产过程中，由于需求是随时

4、间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。 机器负荷分配问题机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在每年开始时，决定如何重新分配每年开始时，决定如何重新分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。，使在五年内产品的总产量达到最高。 航天飞机飞行控制问题航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要

5、根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。 第4页/共63页 6 根据过程的特性可以将过程按空间、时间等标志分为根据过程的特性可以将过程按空间、时间等标志分为 若干个互相联系又互相区别的阶段。若干个互相联系又互相区别的阶段。 在每一个阶段都需要做出决策，从而使整个过程达到在每一个阶段都需要做出决策，从而使整个过程达到 最好的效果。最好的效果。 各个

6、阶段决策的选取不是任意确定的，它依赖于当前各个阶段决策的选取不是任意确定的，它依赖于当前 面临的状态，又影响以后的发展。面临的状态，又影响以后的发展。 当各个阶段的决策确定后，就组成了一个决策序列，当各个阶段的决策确定后，就组成了一个决策序列， 因而也就决定了整个过程的一条活动路线，这样的一因而也就决定了整个过程的一条活动路线，这样的一 个前后关联具有链状结构的多阶段过程就称为多阶段个前后关联具有链状结构的多阶段过程就称为多阶段 决策问题。决策问题。 多阶段决策过程的特点：多阶段决策过程的特点： 第5页/共63页 7 针对多阶段决策过程的最优化问题，美国数学家针对多阶段决策过程的最优化问题，美

7、国数学家BellmanBellman等人在等人在2020世纪世纪5050年代初提出了著名的最优化原理，年代初提出了著名的最优化原理，把多阶段决策问题转化为一系列单阶段最优化问题把多阶段决策问题转化为一系列单阶段最优化问题，从而逐个求解，从而逐个求解， 创立了解决这类过程优化问题的新方法：动态规划。创立了解决这类过程优化问题的新方法：动态规划。 对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是Bellman提出的著名的最优化原理。 简言之， 一个最优策略的子策略必然也是最优的。 Bellma

8、n在在1957年出版的年出版的Dynamic Programming是动态规划领域的第一本著作。是动态规划领域的第一本著作。 第6页/共63页 8 例1、从从A A 地到地到E E 地要铺设一条煤气管道地要铺设一条煤气管道, ,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？ A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 第7页/共63页

9、9 解：解：整个计算过程分四个整个计算过程分四个阶段阶段，从最后一个阶段开始。，从最后一个阶段开始。 第四阶段（第四阶段（D E）：）： D 有两条路线到终点有两条路线到终点E 。 显然有显然有 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 2)(; 5)( 2414 DfDf 第8页/共63页 10 首先考虑经过首先考虑经过 的两条路线的两条路线 第三阶段（第三阶段（C D）：）： C 到到D 有有 6 条路线。条路线。 (最短路线为最短路线为 ) A B2 B1 B3 C1 C3

10、D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 8 29 53 min )(),( )(),( min)( 2421 1411 13 DfDCd DfDCd Cf EDC 11 1 C 第9页/共63页 11 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 7 25 56 min )(),( )(),( min)( 2422 1412 23 DfDCd DfDCd Cf (最短路线为最短路线为 ) EDC 22 考虑经过考

11、虑经过 的两条路线的两条路线 2 C 第10页/共63页 12 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 12 210 58 min )(),( )(),( min)( 2423 1413 33 DfDCd DfDCd Cf (最短路线为最短路线为 ) EDC 23 考虑经过考虑经过 的两条路线的两条路线 3 C 第11页/共63页 13 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C

12、2 20 1210 714 812 min )(),( )(),( )(),( min)( 3331 2321 1311 12 CfCBd CfCBd CfCBd Bf (最短路线为最短路线为 ) EDCB 111 第二阶段（第二阶段（B C）：）： B 到到C 有有 9 条路线。条路线。 首先考虑经过首先考虑经过 的的3条路线条路线 1 B 第12页/共63页 14 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 14 124 710 86 min )(),( )(),( )(),( mi

13、n)( 3432 2422 1412 22 CfCBd CfCBd CfCBd Bf (最短路线为最短路线为 ) EDCB 112 考虑经过考虑经过 的的3条路线条路线 2 B 第13页/共63页 15 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 19 1211 712 813 min )(),( )(),( )(),( min)( 3333 2323 1313 32 CfCBd CfCBd CfCBd Bf (最短路线为最短路线为 ) EDCB 223 考虑经过考虑经过 的的3条路线条

14、路线 3 B 第14页/共63页 16 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 19 191 145 202 min )(),( )(),( )(),( min)( 323 222 121 1 BfBAd BfBAd BfBAd Af (最短路线为最短路线为 ) EDCBA 112 第一阶段（第一阶段（A B）：）： A 到到B 有有 3 条路线。条路线。 （最短距离为（最短距离为19） 第15页/共63页 17 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，动态

15、规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个它可以把一个n 维决策问题变换为几个一维最优化问题维决策问题变换为几个一维最优化问题，从而一个一个地去解决。，从而一个一个地去解决。 需指出：需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 即在系统发展的不同时刻（或阶段）根据

16、系统所处的状态，即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策不断地做出决策； 动态决策问题的特点：动态决策问题的特点： 系统所处的系统所处的状态和时刻状态和时刻是进行决策的重要因素；是进行决策的重要因素； 找到找到不同时刻不同时刻的最优决策以及的最优决策以及整个过程的最优策略整个过程的最优策略。 第16页/共63页 18 动态规划方法的关键：在于正确地写出动态规划方法的关键：在于正确地写出基本的递推关系式基本的递推关系式和和恰当的边界条件恰当的边界条件（简称（简称基本方程基本方程）。）。 要做到这一点，就必须将问题的过程分成几个相互联系的要做到这一点，就必须将问题的过程分

17、成几个相互联系的阶段阶段，恰当的选取，恰当的选取状态变量状态变量和和决策变量决策变量及定义及定义最优值函数最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。 即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。 第17页/共63页 19 2、在多阶段决策过程中，动态规划方

18、法是既把当前一段和未来一段、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开分开，又把当前效益和未来效益，又把当前效益和未来效益结合结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的. 最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是

19、该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。 第18页/共63页 20 第19页/共63页 21 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 nix ax xgz i n i i n i ii .2.1 0 )( max 1 1 据此，有下式： 第20页/共63页 22 令：令：fk(x) 表示表示 以数量为以数量为 x 的资金分配给的资金分配给前前k 个个工厂，所得到的最

20、大利润值。工厂，所得到的最大利润值。 用动态规划求解，就是用动态规划求解，就是求求 fn(a) 的问题的问题。 当当 k=1 时，时， f1(x) = g1(x) （因为只给一个工厂）（因为只给一个工厂） 当当1kn 时，其递推关系如下：时，其递推关系如下： 设：设：y 为分给第为分给第k 个工厂的资金（其中个工厂的资金（其中 0y x ），此时还剩），此时还剩 x y（万元）的资金需要分配给前（万元）的资金需要分配给前 k1 个工厂个工厂,如果采取最优策略，则得到的最大利润为如果采取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润为：因此总的利润为： gk(y) fk1(xy) 第

21、21页/共63页 23 nk yxfygxf kk xy k . )()(max)( 32 1 0 其中 如果如果a 是以万元为资金分配单位，则式中的是以万元为资金分配单位，则式中的y 只取非负整数只取非负整数0，1，2，x。上式可变为：。上式可变为： )()(max)( , yxfygxf kk xy k 1 210 所以，根据动态规划的最优化原理，有下式：所以，根据动态规划的最优化原理，有下式： 第22页/共63页 24 例2：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资 利润 0102030405060 g1(x)

22、0205065808585 g2(x)0204050556065 g3(x)0256085100110115 g4(x)0254050606570 解：依据题意，是要求 f4(60) 。 第23页/共63页 25 按顺序解法计算。按顺序解法计算。 第一阶段：求第一阶段：求 f1(x)。显然有。显然有 f1(x) g1(x)，得到下表，得到下表 投资投资 利润利润 0102030405060 f1(x) g1(x)0205065808585 最优策略最优策略0102030405060 第二阶段：求第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。此时需考虑

23、第一、第二个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60( 12 60,10,0 2 yfygf y 第24页/共63页 26 120 065 2060 5055 6550 8040 8520 850 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0( max 12 12 12 12 12 12 12 fg fg fg fg fg fg fg 最优策略为（最优策略为（40，20），此时最大利润为），此时最大利润为120万元。万元。 同理可求得其它同理可求得其它 f2(x) 的值。的值。 )60

24、()(max)60( 12 60,10,0 2 yfygf y 第25页/共63页 27 105 )0()50( )10()40( )20()30( )30()20( )40()10( )50()0( )50()(max)50( 12 12 12 12 12 12 12 50,10,0 2 fg fg fg fg fg fg yfygf y 最优策略为（最优策略为（3030，2020），此时最大利润为），此时最大利润为105105万元。万元。 第26页/共63页 28 90 )40()(max)40( 12 40,10,0 2 yfygf y 最优策略为（最优策略为（20，20），此时最大利润

25、为），此时最大利润为90万元。万元。 70 )30()(max)30( 12 30,20,10,0 2 yfygf y 最优策略为（最优策略为（20，10），此时最大利润为），此时最大利润为70万元。万元。 第27页/共63页 29 50 )20()(max)20( 12 20,10,0 2 yfygf y 20 )10()(max)10( 12 ,10,0 2 yfygf y 最优策略为（最优策略为（10，0）或（）或（ 0 ， 10 ） ，此时最大利润为，此时最大利润为20万元。万元。 f2(0) 0。最优策略为（最优策略为（0，0），最大利润为），最大利润为0万元。万元。 得到下表得到下

26、表 最优策略为（最优策略为（20，0），此时最大利润为），此时最大利润为50万元。万元。 第28页/共63页 30 投资投资 利润利润 0102030405060 f2(x)020507090105120 最优策略最优策略(0,0)(10,0) (0,10) (20,0) (20,10) (20,20) (30,20) (40,20) 第三阶段：求第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60( 23 60,10,0 3 yfygf y 第29页/共

27、63页 31 155 0115 20110 50100 7085 9060 10525 1200 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0( max 23 23 23 23 23 23 23 fg fg fg fg fg fg fg 最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。 同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表 第30页/共63页 32 投资投资 利润利润 0102030405060 f3(x)0256085110135155 最

28、优最优 策略策略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 第四阶段：求 f4(60)。即问题的最优策略。 )60()(max)60( 34 60,10,0 4 yfygf y 第31页/共63页 33 160 070 2565 6060 8550 11040 13525 1550 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0( max 34 34 34 34 34 34 34 fg fg fg fg fg fg fg 最优

29、策略为（20，0，30，10），最大利润为160万元。 第32页/共63页 34 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品物品 1 2 j n 重量（重量（公斤公斤/ /件件） a1 a2 aj an 每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 第33页/共63页 35 设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下：

30、).( max njx axa xcZ j n ij jj n j jj 21 0 1 且为整数 用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a) 第34页/共63页 36 其递推关系式为： nk xayfxcyf kkkkk a y x k k k 2 1 0 其中 )(max)( 当 k=1 时，有： 的最大整数表示不超过其中 11 1 1 1 11 a y a y a y x a y cyf ,)( 第35页/共63页 37 例3：求下面背包问题的最优解 且且为为整整

31、数数0, 5523 1258max 321 321 321 xxx xxx xxxZ 物品物品( (xi ) x1 x2 x3 重量（重量（ai） 3 2 5 使用价值使用价值 8 5 12 解：a5 ，问题是求 f3(5) )55(12max)5( 323 5 0 3 3 3 3 xfxf x a x 整整数数 第36页/共63页 38 )( max)( 323 5 0 3 55125 3 3 3 xfxf x a x 整数 )( max 323 5 5 0 5512 3 3 xfx x x 整数 )( max 323 10 5512 3 xfx x ， )( )( )( ),(max 10

32、 22 33 01250 xx ff 物品物品( (xi ) x1 x2 x3 重量（重量（ai） 3 2 5 使用价值使用价值 8 5 12 第37页/共63页 39 5 5 )( 2)1()0( 111 212 2, 10 212 2 5 0 212 5 0 2 222 2 2 2 2 2 2 )1(10),3(5),5(0max )25(max )25(max )25(5max)5( xxx x x x x a x fff xfx xfx xfxf ， 整数整数 整数整数 物品物品( (xi ) x1 x2 x3 重量（重量（ai） 3 2 5 使用价值使用价值 8 5 12 )()(

33、)()(max )( 10 22 3 33 01250 5 x x f, f f 第38页/共63页 40 )0( )0(0max )20(5 max )20(5 max )20(5 max)0( 1 )0( 1 212 0 212 2 0 0 212 0 0 2 2 2 2 2 2 2 2 ff xfx xfx xfxf x x x x x a x 整数整数 整数整数 物品物品( (xi ) x1 x2 x3 重量（重量（ai） 3 2 5 使用价值使用价值 8 5 12 )1()0( 22 3 33 )0(12)5(0max )5( x x f, f f 第39页/共63页 41 )0(0

34、 3 0 8)0( )0(0 3 1 8)1( )1(8 3 3 8)3( )1(8 3 5 8)5( 1111 1111 1111 1111 xxcf xxcf xxcf xxcf ) 1, 1(1310, 85, 8max ) 1 (10),3(5),5(0max)5( 21 2)1()0( 1112 222 xx ffff xxx )( 第40页/共63页 42 )0, 0(0)0()0(0max)0( 211 )0( 12 2 xxfff x )0,1,1(13 012,130max )0(12),5(0max)5( 321 )1()0( 223 33 xxx fff xx 所以，最优

35、解为所以，最优解为 X（1 . 1 . 0），），最优值为最优值为 Z = 13。 总结：总结：解动态规划的一般方法解动态规划的一般方法:从终点逐段向始点方向寻找从终点逐段向始点方向寻找最小最小(大大)的方法。的方法。 第41页/共63页 43 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？ 14682023 交货日期（交货日期（d） 45173 加工时间（加工时间（t） 零件代号零件代号 2 j 1 j 3 j 4 j 5 j 例5.1 第42页/共63页 44 （1）平均通过设备的时间最小

36、按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可） 1 j 2 j 3 j 4 j 5 j 零件加工顺序零件加工顺序 工序时间工序时间 13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间 2 . 9)1481320( 5 1 x 延迟时间 = 13 6 = 7 第43页/共63页 45 （2）按时交货排列顺序 1 j 2 j 3 j 4 j5 j 零件加工顺序零件加工顺序 工序时间工序时间 13457 实际通过时间实际通过时间56101720 交货时间交货时间82314620 平均通过时间 6 .11)56101720(

37、 5 1 x 延迟时间 = 0 第44页/共63页 46 （3）既满足交货时间，又使平均通过时间最小 1 j 2 j 3 j 4 j 5 j 零件加工顺序零件加工顺序 工序时间工序时间 13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620 延迟时间 = 0 平均通过时间 8 .9)1691320( 5 1 x 第45页/共63页 47 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安排？种设备进行加工，如何安排？ 例5.2 49523 B 53786 A 零件零件 2 j 1 j 3 j 4 j 5 j 设备设备 A B T

38、第46页/共63页 48 经变换为 49523 B 53786 A 零件零件 2 j 1 j 3 j 4 j 5 j 设备设备 加工顺序图如下：加工顺序图如下： A B T 3 j 1 j 2 j 4 j 5 j 37568 95432 +2+2-5 加工周期加工周期 T = 3+7+5+6+8+2 = 31 小小 即即 BA tt i 第47页/共63页 49 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进行加工，如何安排？种设备进行加工，如何安排？ 例5.3 346 856 468 357 9310 CBA 1 j 2 j 3 j 4 j 5 j A B C T

39、第48页/共63页 50 A B C T 变换 4+36+4 5+86+5 6+48+6 5+37+5 3+910+3 B + C A+B 1 j 2 j 3 j 4 j 5 j 第49页/共63页 51 排序 4+36+4 5+86+5 6+48+6 5+37+5 3+910+3 B + C A+B 1 j 2 j 3 j 4 j 5 j 复原 346 856 468 357 9310 CBA 1 j 2 j 3 j 4 j 5 j 第50页/共63页 52 计算 T = 6+10+8+7+6+4+3 = 44 计算依据： ABcCBA BCBA tttttt tttt ii iiii 或即

40、可按下式计算 或maxminmaxmin 第51页/共63页 53 练习练习1 ： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18 求从求从A到到G的最短路径的最短路径 3 第52页/共63页 54 5 32 45 min , , min 26225 16125 25 FfFEd FfFEd Ef k=5k=5，出发点，出发点E1E1、E2E2、E3E3 7 3

41、5 43 min , , min 2621 1611 5 5 FfFEd FfFEd u5(E1)= F1 E1 F1 G A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 )( 15 Ef u5(E2)= F2 E2 F2 G 9 36 46 min , , min 26235 16135 35 FfFEd FfFEd Ef u5(E3)= F2 E3 F2 G k=6k=6,F1 G, f f6 6(F1)=4(F1)=4 F F2 2 G,f,f6 6(F2)=3(F2)=3 第53页/共63页 55 k=4，f4( D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D1 f3(C4)=12 u3(C4)=D3 k=3, = min f1(A)= min d1(A,B1)+ f2(