《管理运筹学整数规划ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学整数规划ppt课件（20页珍藏版）》请在金锄头文库上搜索。
1、第八章第八章 整数规划整数规划 1 整数规划的图解法 2整数规划的计算机求解 3整数规划的运用 4整数规划的分枝定界法1 1 整数整数规划的划的图解法解法例例1. 某工厂在方案期内要安排甲、乙两种某工厂在方案期内要安排甲、乙两种仪器器设备的消的消费，知消，知消费仪器器设备需求需求A、B两种材两种材料的耗料的耗费以及以及资源的限制，如右源的限制，如右表。表。问题：工厂：工厂应分分别消消费多少件甲、乙种多少件甲、乙种仪器器设备才才能使工厂能使工厂获利最多？利最多？解、解、目的函数：目的函数： Max z = x1 + x2 约束条件：束条件： s.t. 3 x1 + 2 x2 10 2 x2 5
2、x1，x2 0 为整数整数不思索整数不思索整数约束得到最束得到最优解：解： x1 =1.667， x2 = 2.5；z = 4.167思索整数约束得到最优解： x1 = 2， x2 = 2； z = 4整数规划的最优目的值小于相应线性规划的最优目的值(相当于附加一个约束)22整数整数规划的划的计算机求解算机求解例例2 2： Max z = 15x1 + 10x2 + 7x3 Max z = 15x1 + 10x2 + 7x3 s.t. s.t. 5x1 - 10x2 + 7x3 8 5x1 - 10x2 + 7x3 8 6x1 + 4x2 + 8x3 12 6x1 + 4x2 + 8x3 12
3、 -3x1 + 2x2 + 2x3 10 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 x1,x2,x3 0 为整数整数例例2 2： Max z = 15x1 + 10x2 + 7x3 Max z = 15x1 + 10x2 + 7x3 s.t. s.t. 5x1 - 10x2 + 7x3 8 5x1 - 10x2 + 7x3 8 6x1 + 4x2 + 8x3 12 6x1 + 4x2 + 8x3 12 -3x1 + 2x2 + 2x3 10 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 x1,x2,x3 0 x3 x3 为整数整数 x1 x1 为0-10-1
4、变量量用软件求解得： x1 = 0 x2 = 3 x3 = 0 z = 30用软件求解得： x1 = 1 x2 = 1.5 x3 = 0 z = 3033整数整数规划的运用划的运用(1)(1) 一、投资场所的选择 例4、京成畜产品公司方案在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，思索到各地域居民的消费程度及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多项选择择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 A
5、j 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示 (单位：万元)。但投资总额不能超越720万元，问应选择哪几个销售点，可使年利润为最大?解：解：设：0-1变量量 xi = 1 (Ai 点被点被选用或用或 0 (Ai 点没被点没被选用。用。 这样我我们可建立如下的数学模型：可建立如下的数学模型：Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x
6、4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 为0-1变量，量，i = 1,2,3,10二、固定本钱问题 例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如右表所示。不思索固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可运用的金属板有500吨，劳动力有300人月，机器有100台月，此外不论每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。如今要制定一个消费方案，使获得的利润为最大。 解：这是一个整数规划的问
7、题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的消费数量。 各种容器的固定费用只需在消费该种容器时才投入，为了阐明固定费用的这种性质，设 yi = 1(当消费第 i种容器, 即 xi 0 时) 或0当不消费第 i种容器即 xi = 0 时 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3
8、 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 为0-1变量，i = 1,2,333整数整数规划的运用划的运用(2)(2)例6有四个工人，要分别指派他们完成四项不同的任务，每人做各项任务所消耗的时间如右表所示，问应如何指派任务，才干使总的耗费时间为最少。 解：引入解：引入01变量量 xij，并令，并令 xij = 1(当指派第当指派第 i人去完成第人去完成第j项任任务时)或或0当不指派第当不指派第 i人去完成第人去完成第j项任任务时) 这可以表示可以表示为一个一个0-1整数整数规划划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22
9、+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一甲只能干一项任任务) x21+ x22+ x23+ x24= 1 (乙只能干一乙只能干一项任任务) x31+ x32+ x33+ x34= 1 (丙只能干一丙只能干一项任任务) x41+ x42+ x43+ x44= 1 (丁只能干一丁只能干一项任任务) x11+ x21+ x31+ x41= 1 ( A任任务只能一人干只能一人干) x12+ x22+ x32+ x42= 1 ( B任任务只能一人干只能一人干
10、) x13+ x23+ x33+ x43= 1 ( C任任务只能一人干只能一人干) x14+ x24+ x34+ x44= 1 ( D任任务只能一人干只能一人干) xij 为0-1变量，量，i,j = 1,2,3,4 * * * 求解可用求解可用软件中整数件中整数规划方法。划方法。 33整数整数规划的运用划的运用(3)(3)三、指派三、指派问题 有有 n n 项不同的不同的义务，恰好，恰好 n n 个人可分个人可分别承当承当这些些义务，但由于每，但由于每人人专长不同，完成各不同，完成各项义务的效率等情况也不同。的效率等情况也不同。现假假设必需指派每个人必需指派每个人去完成一去完成一项义务，怎，
11、怎样把把 n n 项义务指派指派给 n n 个人，使得完成个人，使得完成 n n 项义务的的总的效率最高，的效率最高，这就是指派就是指派问题。 四、分布系统设计例7某企业在 A1 地已有一个工厂，其产品的消费才干为 30 千箱，为了扩展消费，计划在 A2，A3，A4，A5地中再选择几个地方建厂。知在 A2 ， A3，A4，A5地建厂的固定本钱分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如右表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定本钱和总的运输费用
12、之和最小? b) 假设由于政策要求必需在A2，A3地建一个厂，应在哪几个地方建厂? 解：解： a) 设 xij为从从Ai 运往运往Bj 的运的运输量量(单位千箱位千箱)， yi = 1(当当Ai 被被选中中时)或或0当当Ai 没被没被选中中时) 这可以表示可以表示为一个整数一个整数规划划问题：Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53其中前其中前4项为固定投固定投资额，后面的，后面的项为运运输费用。用。s.t. x11
13、+ x12+ x13 30 ( A1 厂的厂的产量限制量限制) x21+ x22+ x23 10y2 ( A2 厂的厂的产量限制量限制) b添加添加约束：束：y2+y3=1 x31+ x32+ x33 20y3 ( A3 厂的厂的产量限制量限制) x41+ x42+ x43 30y4 ( A4 厂的厂的产量限制量限制) x51+ x52+ x53 40y5 ( A5 厂的厂的产量限制量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制地的限制) x13+ x23+
14、x33+ x43 + x53 = 20 ( B3 销地的限制地的限制) xij 0 yi为0-1变量，量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用求解可用软件中整数件中整数规划方法。划方法。 33整数整数规划的运用划的运用(4)(4)33整数整数规划的运用划的运用(5)(5)五、投五、投资问题 例例8 8某公司在今后五年内思索某公司在今后五年内思索给以下的工程投以下的工程投资。知：。知： 工程工程A A：从第一年到第四年每年年初需求投：从第一年到第四年每年年初需求投资，并于次年末回收本利，并于次年末回收本利115%115%，但要求第一年投，但要求第一年投资最低金最低
15、金额为4 4万元，第二、三、四年不限；万元，第二、三、四年不限； 工程工程B B：第三年初需求投：第三年初需求投资，到第五年未能回收本利，到第五年未能回收本利128128，但，但规定最低投定最低投资金金额为3 3万元，最高金万元，最高金额为5 5万元；万元； 工程工程 C C：第二年初需求投：第二年初需求投资，到第五年未能回收本利，到第五年未能回收本利140%140%，但，但规定其投定其投资额或或为2 2万元或万元或为4 4万元或万元或为6 6万元或万元或为8 8万元。万元。 工程工程 D D：五年内每年初可：五年内每年初可购买公公债，于当年末，于当年末归还，并加利息，并加利息6%6%，此，此
16、项投投资金金额不限。不限。 该部部门现有有资金金1010万元，万元，问它它应如何确定如何确定给这些工程的每年投些工程的每年投资额，使到第五年末，使到第五年末拥有的有的资金本利金本利总额为最大最大? ? 解：解：1) 设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分分别表示第表示第 i 年年初年年初给工程工程A，B，C，D的投的投资额； 设yiA， yiB，是，是01变量，并量，并规定取定取 1 时分分别表示第表示第 i 年年给A、B投投资，否那么取，否那么取 0 i = 1, 2, 3, 4, 5。 设yiC 是非是非负整数整数变量，并量，并规定：定：2年投年投资C工程工程8万
17、元万元时，取，取值为4； 2年投年投资C工程工程6万元万元时，取，取值为3； 2年投年投资C工程工程4万元万元时，取，取值为2； 2年投年投资C工程工程2万元万元时，取，取值为1； 2年不投年不投资C工程工程时， 取取值为0； 这样我我们建立如下的决策建立如下的决策变量：量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D 33整数整数规划的运用划的运用(6)(6)2 2约束条件：束条件：第一年：年初有第一年：年初有100000100000元，元，D D工
18、程在年末可收回投工程在年末可收回投资，故第一年年初，故第一年年初应把全部把全部资金投出去，于是金投出去，于是 x1A+ x1D x1A+ x1D = 100000= 100000；第二年：第二年：A A次年末才可收回投次年末才可收回投资故第二年年初的故第二年年初的资金金为1.06x1D1.06x1D，于是，于是x2A+x2C+x2D = 1.06x1Dx2A+x2C+x2D = 1.06x1D；第三年：年初的第三年：年初的资金金为 1.15x1A+1.06x2D 1.15x1A+1.06x2D，于是，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D x3A+x3B+x3D =
19、 1.15x1A+ 1.06x2D；第四年：年初的第四年：年初的资金金为 1.15x2A+1.06x3D 1.15x2A+1.06x3D，于是，于是 x4A + x4D = 1.15x2A+ 1.06x3D x4A + x4D = 1.15x2A+ 1.06x3D；第五年：年初的第五年：年初的资金金为 1.15x3A+1.06x4D 1.15x3A+1.06x4D，于是，于是 x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D；关于工程关于工程A A的投的投资额规定定: x1A 40000y1A : x1A 40000y1A ，x1A 200000y1A
20、 x1A 200000y1A ，200000200000是足是足够大的数；大的数； 保保证当当 y1A = 0 y1A = 0时， x1A = 0 x1A = 0 ；当；当y1A = 1y1A = 1时，x1A 40000 x1A 40000 。 关于工程关于工程B B的投的投资额规定定: x3B 30000y3B : x3B 30000y3B ，x3B 50000y3B x3B 50000y3B ； 保保证当当 y3B = 0 y3B = 0时， x3B = 0 x3B = 0 ；当；当y3B = 1y3B = 1时，50000 x3B 30000 50000 x3B 30000 。 关于工
21、程关于工程C C的投的投资额规定定: x2C = 20000y2C : x2C = 20000y2C ，y2C = 0y2C = 0，1 1，2 2，3 3，4 4。3 3目的函数及模型：目的函数及模型： Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000 s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.1
22、5x1A+ 1.06x2D x3A+x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D； x1A 40000y1A x1A 40000y1A ， x1A 200000y1A x1A 200000y1A ， x3B 30000y3B x3B 30000y3B ， x3B 50000y3B x3B 50000y3B ； x2C = 20000y2C x2C = 20000y2C ， yiA yi
23、A， yiB = 0 yiB = 0 或或 1 1，i = 1,2,3,4,5i = 1,2,3,4,5 y2C = 0 y2C = 0，1 1，2 2，3 3，4 4 xiA xiA ，xiB xiB ，xiC xiC ，xiD 0 ( i = 1xiD 0 ( i = 1、2 2、3 3、4 4、5 5 44整数整数规划的分枝定界法划的分枝定界法(1)(1)问题A Min z = c1 x1 + c2 x2 + + cn xn 记 问题B为去掉整数约束的问题A s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn =
24、 b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0 为整数在分枝定界法过程中求解问题(B)，应有以下情况之一： (B)无可行解，那么(A)亦无可行解，停顿对此问题 的计算； (B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z*同时是当前问题(A)最优目的值的上界和下界。停顿对这个问题的计算； (B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题(A)最优目的值的一个下界 z z ,于是经过以下判别可对此问题进一步计算。分枝定界法的计算过程： 1、对原问题(A)，求解松弛问题(B)。根据上面分析，假设出现情况，那么停机
25、。假设情况发生，得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解，那么对应的目的函数值是(A)最优值的一个上界 z 。即得到 z z* z。(注：找(A)问题的可行解往往需求较大的计算量，这时可简单记 z+，而先不用费很大力量去求较好的上界。从以下分析可以看到，找到一个好的最优目的值上界，将对算法的快速求得目的非常有效。)，转2，进展以下普通步的迭代； 44整数整数规划的分枝定界法划的分枝定界法(2)(2)2、对当前问题进展分枝和定界： 分技：无妨设当前问题为(A)，其松弛问题(B)的最优解不符合整数约束，任取非整数的分量 xr 。构造两个附加约束： xr xr 和 xr xr+
26、1 ，对(A)分别参与这两个约束，可得到两个子问题(A1)和(A2)，显然这两个子问题的可行解集的并是(A)的可行解集； 定界：根据前面分析，对每个当前问题(A)可以经过求解松弛问题(B)，以及找(A)的可行解得到当前问题的上、下界 z和 z 。 对普通迭代步，设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI )，i1，2，.，n 之和的分解。这里的同层子问题是指每个子问题(AI)都是(A)经过一样分枝次数得到的。 3、比较与剪枝： 对当前子问题进展调查，假设不需再进展计算，那么称之为剪枝。普通遇到以下情况就需剪枝： (B)无可行解； (B)的最优解符合整数约束； (B)的最优值 z
27、 z 。 经过比较，假设子问题不剪枝那么前往 2 。 分枝定界法当一切子问题都剪枝了，即没有需求处置的子问题时，到达当前上界 z 的可行解即原问题的最优解， 算法终了。44整数整数规划的分枝定界法划的分枝定界法(3)(3) 分枝定界法是求整数规划的一种常用的有效的方法，既能处理纯整数规划的问题，也能处理混合整数规划的问题。例：Min f = -5x1-4x2s.t. 3x1+4x2 24 9x1+5x2 45 x1,x2 0 整数44整数整数规划的分枝定界法划的分枝定界法(4)(4) 隐枚举法是求解01规划最常用的方法之一 对于 n 个决策变量的完全 01 规划，其可行点最多有 2n 个，当
28、n 较大时其计算量大得惊人。隐枚举法的根本思想是根据01规划的特点，进展分技逐渐求解。1、用于隐枚举法的01规划规范方式： 为了计算的方便，需求把普通的 01规划问题等价地化成以下规范方式 Min f = c1 x1 + c2 x2 + + cn xn cj 0 j = 1,2,n s.t. ai1 x1 + ai2 x2 + + ain xn bi i = 1,2,m x1 ，x2 ， ，xn = 0 或 1下面阐明一个完全的01规划问题可以化为等价的规范方式： (1)假设目的函数求最大：Max z，可令 f = - z，变为求最小 Min f ； (2)假设目的函数的系数有负值时，如 cj
29、 0。那么，可以令相应的 yj = 1- xj ； (3)当某个约束不等式是“时，只需两端同乘以 -1，即变为“ ； (4)当某个约束是等式约束时，可得到两个方向相反的不等式。44整数整数规划的分枝定界法划的分枝定界法(5)(5)隐枚枚举法的根本法的根本过程：程： 1、将、将01规划划问题化化为规范方式，范方式，设其最其最优解解为 x*，最，最优目的目的值为 f* 。显然然 x = 0 时，目的，目的值 f 0 是不思索是不思索线性不等式性不等式约束的最小解，于是束的最小解，于是 f* 0。假。假设 x = 0 是可行解，那末是可行解，那末 f 0是是该问题的最的最优解，解，终了了计算。否那么
30、，置一切分量算。否那么，置一切分量为自在自在变量。量。转2； 2、任、任选一自在一自在变量量 xk ，令，令 xk 为固定固定变量，分量，分别固定固定为 xk = 0 与与 xk 1，令一切，令一切自在自在变量取零量取零值，那么得到两个分枝。，那么得到两个分枝。对每个分枝的每个分枝的试探解探解进展展检验把自在把自在变量逐次定量逐次定为固定固定变量的量的顺序可以是恣意的，在不序可以是恣意的，在不进展先展先验调查时，常按目的，常按目的变量量从小到大的从小到大的顺序序进展。展。转3； 3、检验当前当前试探解探解时，遇到以下，遇到以下4种情况就剪枝，即不用再向下分枝，在剪枝的子种情况就剪枝，即不用再向
31、下分枝，在剪枝的子问题下方下方标志志“： 情况一：假情况一：假设子子问题的的试探解可行，即探解可行，即满足一切足一切线性不等式性不等式约束，那么此束，那么此问题的目的目的的值是原是原问题最最优目的目的值的一个上界的一个上界记为 f 即即 f* f 。把。把 f 的的值记在子在子问题框的旁框的旁边，并在下方，并在下方标志上志上“；44整数整数规划的分枝定界法划的分枝定界法(6)(6) 情况二：假设试探解不可行，且存在一个线性不等式约束，将一切固定变量值代入后，所得到的不等式中一切负系数之和大于右端项或假设无负系数时，最小的系数大于右端项，那么此问题的任何分枝都是不可行的问题。于是在此问题框的下方
32、标志“； 情况三：假设试探解不可行，且它的目的值与目的函数中对该当前自在变量的任一个系数之和大于一切已得到的上界中最小者时，阐明在当前问题的根底上，固定任何自在变量都不能够对目的函数有改善，于是在该问题框的下方标志“； 情况四：假设试探解不可行，但一切变量已被置为固定变量，也应剪枝，于是在该问题框的下方标志“。 把已标志“的子问题，称为已探明的枝。转4。 4、进一步调查。假设一切的枝均为已探明的枝，那么停机终了计算。找出一切子问题框边标志 f 值的问题，比较得到其中最小者，其对应的试探解即原问题的最优解，相应值即原问题的最优目的值 f*；假设没有标志 f 值的框，那么阐明原问题无最优解，实践上
33、原问题无可行解。 假设仍存在尚未探明的分枝，那么可任选一个未探明的分枝。转2。44整数整数规划的分枝定界法划的分枝定界法(7)(7)0-10-1规划的划的隐枚枚举法法例：例：Max z=100x1+30x2+40x3+45x4Max z=100x1+30x2+40x3+45x4s.t. 50x1+30x2+25x3+10x495s.t. 50x1+30x2+25x3+10x495 7x1+ 2x2+ 3x3+ 4x411 7x1+ 2x2+ 3x3+ 4x411 2x1+ x2+ x3+10x412 2x1+ x2+ x3+10x412 x4 x2+ x3 x4 x2+ x3 xj= 0 xj
34、= 0 或或 1 1 ，i = 1,2,3,4i = 1,2,3,4规范化：范化：取取f=-z=-100x1-30x2-40x3 -f=-z=-100x1-30x2-40x3 -45x445x4令令 y1=1-x1, y2=1-x2, y3=1- y1=1-x1, y2=1-x2, y3=1-x3, y4=1-x4x3, y4=1-x4f=100y1+30y2+40y3 +45y4-f=100y1+30y2+40y3 +45y4-215,215,记 f = f + 215, f = f + 215, 得到得到Min f=100y1+30y2+40y3 +45y4Min f=100y1+30y2
35、+40y3 +45y4s.t. s.t. -50y1-30y2-25y3 -10y4-20 -50y1-30y2-25y3 -10y4-20 - 7y1- 2y2- 2y3 - 4y4- 4 - 7y1- 2y2- 2y3 - 4y4- 4 - 2y1- y2- y3 -10y4- 2 - 2y1- y2- y3 -10y4- 2 y2+ y3 - y4 1 y2+ y3 - y4 1 yj= 0 yj= 0 或或 1 1 ，i = 1,2,3,4i = 1,2,3,4第九章第九章 动态规划动态规划 1 多阶段决策过程最优化问题举例 2 根本概念、根本方程与最优化原理 3 动态规划的运用见文本
36、1 多多阶段决策段决策过程最程最优化化问题举例例例例1 最短途径问题最短途径问题右右图图表表示示从从起起点点A到到终终点点E之之间间各各点点的的间间隔隔。求求A到到E的最短途径。的最短途径。 假设用穷举法，那么从A到E一共有332=18条不同的途径，逐个计算每条途径的长度，总共需求进展418=72次加法计算；对18条途径的长度做两两比较，找出其中最短的一条，总共要进展181=17次比较。假设从A到C的站点有k个，那么总共有3k-12条途径， 用穷举法求最短途径总共要进展(k+1)3k-12次加法，3k-12-1次比较。当k的值添加时，需求进展的加法和比较的次数将迅速添加。例如当k=10时，加法次数为433026次，比较39365次。 以上这求从A到E的最短途径问题，可以转化为三个性质完全一样，但规模较小的子问题，即分别从B1、B2、B3到E的最短途径问题。记从Bi (i=1, 2, 3) 到E的最短途径为S(Bi)，那么从A到E的最短间隔S(A)可以表示为：
