钢管订购和运输问题的数学模型

1钢管订购和运输问题的数学模型摘要 本文根据问题的条件和要求，建立了两个模型，模型一为单目标非线性规划模型；模型二为双容量最小费用循环流模型，并通过求解这两个模型，完整地解决了问题。由于铁路运输费用函数具有不可加性，不能直接应用现有的最短路算法来求铁路和公路交通网中任意两点间最小费用路问题。本文采用了一种启发式递推算法，巧妙地解决了这一问题。在单目标非线性规划模型中，将管道铺设分为两个过程。先将钢管从钢管厂运到管道和路道交叉口，再从交叉口铺设到管道线上。这样，总的运输费用就化为两个过程的运输费用之和。由于本模型的目标函数是非线性的，这里采用遗传算法对其求解。所得问题（1）的最小费用为 127.9661 亿元。问题（2）的结果为 的钢管销售价格的1S变化对购运计划及总费用影响最大，而 的钢管产量的上限变化对购运计划及费用影1S响最大。把 5171 公里长的主管道线路按每公里划分一段，分为 5171 个点，每个点对应一个单位的钢管。从钢管厂运送 5171 个单位的钢管到 5171 个点，每个钢厂的容量有上、下限，由此可以将该问题转化为图论中的一个双容量最小费用循环流模型。文中设计了一个近似有效的算法，对该模型进行求解，所得问题（1）的最小费用为 128.025 亿元；问题（2）的结果与模型一得结果相同，问题（3）的费用为 130.9840305 亿元。文中对两个模型都作了一定的理论分析，具有较广泛的适应性。由于模型二将连续的管道线简化分成了 5171 个点，求解所得到的结果稍劣于模型一得结果，但模型二具有较高的理论价值。对于实际中，将一些实际问题抽象简化为数学问题来解决，从方法上具有一定的启发性。最后，对该问题进行了深刻探讨，不仅解决了管道线为树形图的情况，还解决了管道线为一个网络的情况，同时将此问题推广到了一个更一般的网络图问题。对于n=1,n=2 的情形已完全解决，对于 问题提出了它是一个 NP 完全问题的猜想。3n关键词：运输问题 非线性规划 双容量最小费用循环流 效益问题1 问题的重述要铺设一条 的输送天然气的主管道，入附图 6-1 所示。15321AA经筛选后可以生产这种主管道的钢管厂有 。图中粗线表示铁路，单线条732,S2表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路） ，圆圈表示火车站（图中的 T （ ） ，每段铁路、公路和管道旁的数字表i 18,2示里程（单位 km） 。1km 主管道成为 1 单位钢管。如果一个钢管厂承担制造这种钢管任务，至少需要生产 500 个单位。钢管厂 S 在i指定期限内能生产该钢管的最大数量为 s 个单位，钢管出厂销售 1 个单位的钢管为 pi万元，具体数据如表 6-1 所示。1 个单位钢管的铁路运价如表 6-2 所示，1000km 以上i每增加 1 至 100km 运价增加 5 万元。表 6-1 钢管厂的销售单价i 1 2 3 4 5 6 7s i800 800 10002000200020003000p i160 155 155 160 155 150 16表 6-2 钢管的铁路运输单价里程/km300301350 351400 401450 451500运价/万元20 23 26 29 32里程/km501600 601700 701800 801900 9011000运价/万元37 44 50 55 60公路运输费用为 1 单位 0.1 万元/km（不足整公里部分按整公里计算） 。钢管可由铁路、公路运往铺设地点（不只是运送到 ,而是管道全线） 。需要解决的问1521,A题是：（1） 制定一个主管道的订购和运输计划，使总费用最小（给出总费用） 。（2） 就问题（1）的模型进行分析，哪个钢管厂的钢管销售价格变化对购运计划和总费用影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，对这种更为一般的情形给出一种解决办法，并对于附图 6-2 按问题（1）的要求给出模型结果。32.模型的假设(1)在制定订购钢管计划时，数据加精确到 0.001 个单位，即精确到米。此假设保证在理论上得到精确的结果。（2）在运输和铺设的过程中钢管数量无损耗。不需要考虑钢管运输过程中除运费外的其他费用。3.符号及文字说明A 表示住管道树型图的第 j（ ）个顶点；j 15,2S 表示第 个钢铁厂；i )7,21(ic 表示从 S 运送一个单位的钢管到 A 得最小费用；iji jT 表示铁路树形图除 S 外的顶点（具体标号见附图 6-1）;i iU 表示钢厂 S （ ）生产这种钢管的数量；i i 7,21t 表示第第 k（ ）段管道的长度；k 4,v 表示铁路、公路和管道构成网络的所有节点；iV 表示所有 v 的集合；i（y ）表示 y 的小数部分；iiy 表示不超过 y 的整数部分；i i“最小费用路”表示从 S (i=1,2, )运输 1 个单位钢管道 A （ ）运i7, j 21,输费用最小的路。44.问题的分析无论采用哪一条运输路线，最终铺设到主管线上的每单位钢管均要经过与它所在位置相邻的一个主管道顶点（即运输路线上经过的最后一个主管道顶点） 。因此，可将管道的铺设分成两个过程，即可形象地认为先将钢管堆积到主管道顶点 A 处，再将堆j积在 A 处的钢管沿与其邻接的主管道线进行铺设。j4.1 对公路和铁路运输费用函数的分析定义 6.1 运输费用 Y 为线路长度 d 的函数，对任意三点 A,B,C,设 d 为 A,B 之间的1线路长度，d 为点 B,C 之间的线路长度。若 Y（d ）+Y（d ）=Y（d + d ） ，则称该2 122费用函数具有可加性。否则，即存在 d 和 d ，使得 Y（d ）+Y （d ） Y（d + d ） ，121212则称该费用函数具有不可加性。由此定义可得如下的三个结论：结论 1 公路运输费用函数 Y （d）为线性函数，具有可加性；铁路运输费用函数1Y （d）为分段函数，具有不可加性。2结论 2 铁路与公路组成交通网的费用函数具有不可加性。如图 6-1 所示是由公路与铁路组成一段运输线路（细线表示公路，粗线表示铁路） ，则Y(AB)=100 0.1+20=30,Y(BC)=20+50 0.1=25,Y(BC)=100 0.1+23+50 0.1=38。显然有 Y(AB)+Y(BC) Y(AC)。5图 6-1 公路与铁路运输线路示意图结论 3 在公路与铁路交通网中，两点间距离最短不一定运输费用最少。一个单位的钢管从 S 运到 A 总是存在一条运输费用最小的路，但是由结论 3，不ij能直接应用求两点间最短的算法求 S 运到 A 最小费用路径。ij4.2 对公路运输费用需安公里取整计算的分析题目要求公路运输费用不足整公里部分按整公里计算。附图 6-1 中各段公路均为整数，因此，运输钢管到顶点 A 的过程中存在不足整公里的问题。而将钢管从 Aj沿主管道线路铺设，铺设的长度等于钢管的总长度，可能会出现非整公里的情况，因j此，需要从 A 铺设过程中出现不足整公里的问题，设从顶点 A 向右沿主管道线铺设j jy 单位（km）钢管。i情形一 当 y 为整数时，铺设费用为iy 1 0.1+（y 1） 1 0.1+ +1 1 0.1= 。ii 20)1(iy情形二 当 y 为非整数时，铺设费用为iy 1 0.1+（y 1） 1 0.1+ +1 1 0.1=+ii 10)(iiy在实际计算中，对 y 为非整数的情况不容易处理，但注意到i= = ，0 y 1.jP10)(20)(20)1( iiiii yy 2iii6当 y =0.5 时， 最大为 0.0125，其数值非常小，同样课分析从顶点 A 向左沿i jP j主管道铺设 =t y 所花铺设费用。其总误差为i1jj+ =0.3375(万元).142iiP205.7152jj而铺设管道费用是一笔相当大的资金，相比之下此误差也微不足道，所以为简化计算，在后面做具体计算时不考虑小数部分影响，即无论 y 是否为整数，都将铺设费i用为 。20)1(iy4.3 对钢厂是否承担制造这种钢管的分析由题意，如果一个钢厂承担制造这种钢管，则该厂至少需要生产 500 个单位。考虑一个特列，假如该厂 S 到各顶点 A 的最少费用均比该厂 S 的费用低，若该钢厂i k i承担制造这种钢管任务，且在 S 生产上限允许的条件下，这 500 个单位的钢管完全由iS 生产，总费用将会降低，否则该厂 S 不承担制造这种钢管的任务，总费用将会减少，i i因此，为使总费用最少，要充分考虑应由哪些钢厂承担制造这种钢管的任务，哪些钢厂不承担制造任务，根据题意的要求，建立如下两个模型：模型一：单目标非线性规划模型；模型二：双容量最小费用循环流模型。5模型的建立5.1 模型一：单目标非线性规划模型因为钢厂数目较少，不妨设 7 个钢厂都承担制造这种钢管任务，在这种情况下，分析所得结果，再决定哪些钢厂不应承担制造这种钢管的任务。用变量 x 表示由钢厂 S 运往 A 点的钢管数量。变量 y （j 2）为从 A 沿主管ij ij ij道线向右铺设的钢管数量。针对问题（1） ，根据问题的条件和要求，我们可以的得到：7钢厂生产这种钢管数量上下限的约束为， ijisx150.7,21对于 （ ）的约束为jy，jjty0.14,32由于堆积在 A 处的钢管必须全部铺设到与其邻接的主管道线上，于是对于节点jA 有2；271204yxi对于其他节点 A （ ）有j 5,3，jjjij ytx171 ;14,3对于节点 A 有15.147150yxi问题的总费用 Q 由三部分费用组成，即包括购买钢管的费用 M，从钢厂到主管道线上各节点处的运输费用 Y 和从各节点向与其邻接的主管道线铺设钢管的费用 P，即 Q=M+Y+P.事实上，这三部分费用分别为,715),(ijiixpM715ijijxcY8. 142 2)1)()(0j jjjj yttyP综上所述，得到问题一的目标非线性规划模型; 142715715 2)1)()(0)(min j jjjjijiiijji yttyxpxcQ711451712215.0,14,3,04143, ,7,.iii jjjijiijj iijyxtyxtysts 问题 （2） 是在此优化模型中对销售价格 和产量上限 作灵敏度分析。ipis问题 （3） 的优化模型为;2)1)(2)1(2104)(min 1712712 j jjjiijiiiji yttyxpxcQ9s.t. 71 1718191971 2021212071 1101717717171 ,1452288711171 ,2221 .,0, ,1,43,04,1,3,0 ,7,2,5iiiiii i iiiii jjjijiijjj iij ytytxt ytytx yxxyytxtysx 该模型对问题（3）主管道为树形图的情形完全适用，只需增设变量 （参附表 6-jy2） ，其实树形图只是增加了一些叶和节点，对叶 与 A 的约束分析问题（2）中叶 A 的分析，对节点 A ，A ，A 的约束分析同问题（1）中其他节点的分析。 2 模型二：双容量最小费用循环流模图5.2.1 理论准备定义 6.2 设 D=（ V,A）是一个有向图，l,c 是定义在 A 上的两个非负实函数，并且对一切 a A,有 l(a) c（a),则称 l(a)与 c(a）为弧 a 的下容量与上容量，称 D 为双容量网络，记 D=（V， A；l,c) 。定义 6.3 设 f 为双容量网络 D=（v，A；l,a) 的弧集 A 上的一个实值函数，10记 f= ,则称 f 为 D 上的一个循环流。如果对任意给定的 v A，f 满 ）， （ 足0， ）， （ ）， （ 则称 f 为 f 通过(v ,v )的流量，对每个流量定义一个费用函数 w，这时 D 称为双 容量费用网络，记 D=(V,A;l,c,w).定义 6.4 如果 D 上循环 f 还满足 l(a) ，对任意 , ， 则称 f 是 D 的可行循环流。5.2.2 模型的实现将钢管运输到铺设地点本来是一个连续的过程，但可以将其离散化，即视为钢管是一个单位接一个单位地运送到铺点地点，每单位的钢管对应于它所要铺设的 1km长的主管道。这样在附表图 6-1 中吧 5171km 长的主管道线按单位公里来划分，即可分成 5171 个点 任意点 到钢厂 均有一条最小费用路相连，而一个， ， 单位的钢管从 出厂的价格为 万元，所以，一个单位的钢管从 运到任意点 的最 小费用为“最消费用+一个单位钢管的售价” ，记为 。 由于题目要求知，要从钢厂 订购钢管则至少需订购 500 个单位，且对最大订购量均有限制，由此，可得到了一个有向图，其顶点集为V=，； ， ， ； ， ， ； ， ， 其弧集为 ， ； ， ， ， ，）， （ =A 。7,21,(517,2), igsiv）（ 132A定义在弧集 A 上的函数 l,c 为11.517,21,( ,1,;,0),: ivjgisiliji，） ）.517,2,),( ,;,: ivjgscijii弧集 A 上的费用函数 w 定义为的 流 量 时 。为 弧 （当 中 弧 的 流 量 时 ，或为当 331),0)( Avgnwjiij则有函数 l 的定义可知，D=（v,A；l,c,w) 为双容量费用网络，此网络的任一可行流 f 均可应用于问题（1）的一种方案，则问题(1)转化为在此双容量费用网络中求一个费用最小的可行循环流，即求双容量最小费用循环流问题。问题（2）的钢厂钢管销售价格变化对应于 D=（V,A;l,c,w)中上容量函数 c 的变化，由此，通过分别改变费用函数 w 与上容量函数 C 来观察对购运计划和总费用的影响。对问题（3） ，同问题（1)的分析方法一样，也可将其转化为双容量最小费用循环流问题，亦即不管铺设的管道是线，还是树形图，甚至管道本身就是一个网络，均可同样的转化为最小费用循环流问题，而无本质上的区别。6 模型的求解6.1 对求解任意两点间的最小费用路对于附表图 6-1 和附表图 6-2，一个最简单的方法就是用穷举法来实现，即便两点间的所有路，比较其费用，就可以求出最小费用，从而可以求出其最小费用路，但是一个指数时间算法，为寻找公路与铁路网中任意两点之间最小费用路问题，设计提出了一个可行的启发算式 递推法，在这里先给出两个概念。定义 6.5 一条路中从公路转到铁路或由铁路转到公路的点称为这条路上的转折点。定义 6,6 从一点到另一条路中，最后一个中间点称为这条路的前继节点。6.1.1 算法思想首先分别求出任何两点间只经过公路和只经过铁路的最短路径，进而求出任何两点间只经过铁路和只经过公路的最小费用，其次，以此为基础，求出任一两点之间先12经过铁路，且只有一个转折点（先铁路后公路）的最小费用路，以及所需费用值，然后，在已知不超过 个转折点的最小费用路相比较，即求出任意两点之)2,10(nk间的最小费用路，以及最小费用值。6.1.2 算法的基本步骤步骤 1 将铁路和公路网看成一个图 G=（V，E） ， ,并针对铁路和公路分别定n义矩阵 A=（a ) 和 B=（ ） 为ijnmijbnm.0vvji jijiij， 当 之 间 无 铁 路 直 接 连 接和， 当 之 间 有 铁 路 直 接 连 接和之 间 的 铁 路 长 度 ， 当和 点点.0vVvVj jjjibi iiij， 当 之 间 无 公 路 直 接 相 连和 点， 当 点 之 间 有 公 路 直 接 相 连和 点之 间 公 路 长 度 ， 当 点和 点点步骤 2 利用 Floyd 算法 求出任意两点之间只经过铁路的最短距离矩阵 A 及前继3 1节点矩阵 ，同理，求出任意两点之间只经过公路的最短距离矩阵 B 及前继节点矩阵1A 1。1B步骤 3 由矩阵 A 求出任意两点之间只经过铁路的最小费用矩阵 A 及前继节点矩1 ）（ 1阵 ，同理，求出任意两点之间只经过铁路的最小费用矩阵 B 及前继节点矩阵 。1）（ ）（ 1B）（步骤 4 对于任意的 V ， v ，记 ，并记 为最小值得 t,ij）（）（）（ 12(mintjijVvij ba)1(ija构成矩阵 A 和 ，即为从点 v 先经过公路再经过铁路到 v 的最小费用矩阵和前继）（ 2）（ i j节点矩阵。记 ，并记 B 和 从点 v 先经过公路再经过铁路到 v 的最）（ 1)()2(mintjtvij babt)2（ ()i j小费用矩阵和前继节点矩阵。13步骤 5 步骤 5 以知 A )(k和 B ，对任意的 v ，v V,记)(kija)1(kij=为 奇 数 。当） 为 偶 数 ，当 k,(min)1()()(tjktVvtjitbatt并记 a 为最小值时的 t，从而构成矩阵 A 和 ，即点 v 先以铁路开始经)1(ijk )1(k)1(kik+1 个转折点后到达点 v 的最小费用矩阵和前继节点矩阵。j注意到，当 k 为偶数时，第 k 条边仍为铁路，故为（a)1(kit+a ）; 当 k 为奇数时，(tj第 k 条边为公路，故为（a +b ） 。并且可以证明，对任意给定的 l,其值)(kit1(tj相等。)(min1()tjtVvt步骤 6 若 kn-2,则 k=k+1，返回步骤 5。若 k ,则执行步骤 3。2n步骤 7 比较 A , A ,。 。 。 ，A 和 B ，B ， 。 。 。B 的最小值，即为从 v 到)0()1()2(n)0()1()(n iv 的所有路中的最小费用路的费用。利用前继节点矩阵即可以求出最小费用路的路径。j6.2 模型一得求解要确定一个单位钢管从 S 到 A 的最少费用路径及最小费用 c .由上一节中给ij ij出的算法编程进行求解可以得到 c ，由于模型一所建立的是一个非线性规划模型，而ij遗传算法是解决非线性规划的一种比较有效的方法，因此这里采用遗传算法对模型一进行求解，编程实现可得到结果。6.2.1 问题（1）的解选择种群规模 POP SIZE=30，交叉概率 pc=0.3，变异率 0.5，评价函数中参数a=0.05,经过 10000 代后得到问题（1）的最优值为 128.6201 亿元。而且可以得到各钢厂的制造钢管的数量分别为 U =800,U =800,U =1000,U =500,U =861,U =710,U =500.123456714这是 7 个钢厂均承担制造这种钢管时的最小费用，事实上，分析可知，此解并不一定是问题（1）的最优解，实际中可能是在某些钢厂不承担制造钢管的情况下得到问题（1）的解更优。显然 U ，U ，U 均已达到上限 ，说明钢厂 S ,S ,S 的钢管供不应求，故 S ,S ,S123 123 12在最优方案中不一定能去掉，而 U ，U 达到了下限，说明钢厂 S ,S 的钢管运往主3 47 47管道上各顶点费用较高，因而可考虑在 S ,S 或二者均不承担制造钢管任务的情况下，来求问题（1）的最优解。将以上三种情况继续对模型一利用遗传算法求解，则可得到在 S 不承担制造钢管任务的条件下，最小总费用为 127.96661 亿元，而且各钢厂的制4造数量为U =800,U =800,U =1000,U =0,U =1361,U =710,U =500.1234567具体的订购及运输计划建附表 6-1 和 6-3。6.2.2 问题（2）的求解令钢厂的销售价格在一定范围（ ）内变化，可知钢厂 S 的钢管销售405价格 p 变化对购运计划和总费用影响最大，具体情况如表 6-3。5表 6-3 S 的销售价格变化影响结果5变化值 10 1040 40总费用变化量71785 138600 221785 654735订购计划的变化U =5005U =15716U =14115U =6606U =5005U =15716U =5523U =20005U =519615另一方面，从问题（1）结果可知，在总费用最少时，U ，U ，U 远没有达到上567限。分别与其上限相差 639,1290,2500，所以在较大范围（639）内对 S ，S ,S 的上限567作变动，对购运计划和总费用不会造成影响，于是只需分别对 S ,S ,S 在一定范围（123）内作变动，可知 S 的产量上限的变化对购运计划和总费用影响最大，具体情%1501况如表 6-4 所示。表 6-4 S 的产量上限影响结果1产量上限 1200 1600 2000最小总费用 123.84161 亿元120.0820 亿元117.9616 亿元订购计划 U =1200，1U =948， U5=7236U =925，3U =500， U5=8466U =200，U =58612，U =739，U =63635，U =71066.2.3 问题（3）的求解对于模型一。另一遗传算法来求解，同样在 S 不承担制造钢管的情况下得到问4题（3）的最优解，其最小总费用为 130.9840 亿元。而且各钢厂的制造数量为 U =800,U =800,U =1000,U =772,U =1501,U =500,U =500.1234567具体订购计划及运输计划见附表 6-2 和附表 6-4 所示。6.3 模型二的求解对于最小费用循环流问题，在这里设计了一种简单有效的算法。其主要思想是：首先给出一个初始可行流，然后通过转移操作与交叉操作逐渐向最优解逼近。6.3.1 求解算法步骤步骤 1 初始化，先给出 D 的一可行流；16步骤 2 转移操作，从弧（S,g1） ， （S ，g2）， （S,g7）中选出未达到容量上限的弧。改变这些弧的流值，使其向费用最小的目标靠近。步骤 3 交叉操作，设有弧（gi ，vs）与（gj ，vt）流量均为 1，则执行交叉操作，置（gi ，vs）与（gj ，vt）流量为 0，置（gi ， vt）与（gi ，vs）流量为 1，比较两者的费用，选择其最少的。遍历所有这样流量均为 1 的弧对，执行交叉操作。步骤 4 反复执行转移，交叉操作，直到指定步数。6.3.2 求解实现利用该算法编程实现求解，并结合考虑在某些钢厂可能不承担制造钢管任务的情况下，来求解得到最优解。既有问题（1）的最小费用为 127.9661 亿元。问题（2）的解为 S 的钢管销售价格的变化对购运计划和总费用影响最大。S5的钢管产量上限的变化对购运计划和总费用影响最大。1问题（3）的最小费用为 130.9840305 亿元。7.模型的结果分析由问题（1）的求解结果可知，钢厂 承担制造这种钢管时，总费用最小。分析一4S个单位钢管从 运到 的最小费用矩阵，比较 和 到 的最小费用 与 （iSjA6jAjC4j6）可知，除了 外，其余均有 ，且对 均较大程度地大于同列2j 684CjjC448中某些数。由所有的钢厂 ， 全部承担制造钢管的任务时，其订购方案中,21S7=0，即说明 不向 运送钢管，又 的生产上限为 2000 单位，其值是比较大的，48x4S8A6所以由 完全承担 的生产量将会比 生产 500 单位耗资少。因此， 不承担制造这6 4 4S种钢管任务时，其最小费用较低，者也与问题的分析较一致。在总费用最小的情况下， 的生产量均达到他们的生产上限分析矩阵321,S，前 8 列中每列的值 均较小，说明从钢厂 ， ， 订购钢管21715C与 jjC1S2317到节点 ,8)的运输费用都比较低。因此 ，8）将尽可能地从,21(jA ,21(jA订购钢管。 ，8）总共至少需要钢管 2361 单位，故钢厂321,S,21(j产量均要达到上限。,由问题（2）的结果可知，钢厂 的钢管产量的上限变化对购运计划和总费用影响1S较大，这也是由从 到 ,8)的最小运输费用最少决定的，从图上也可以看出，1S2(jA所处的地理位置 距 都较其他钢厂都近，且交通方便，利于运输。因此，建议7至在可能的条件下，由国家投资通过改进钢厂 的生产技术等方式提高钢厂 的生产量，1S1S以节省运输开支。8.算法的理论分析命题 文中提出的递推算法的时间复杂度为 。4nO证明 在算法的步骤 1 中，利用到了 Floyd 算法，其时间复杂度为 。在步骤3nO2 中，需要用递推的方法求 ，每作一次迭代求解最多需计算 2n(n-1)(n-2)次，kBA和总共求了 n-1 次，所以时间的复杂度还是为 。4nO另一方面，文中主要运用了遗传算法对模型一进行了求解。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它能从整个解空间寻找全局最优解，避免只得出局部最优解。因此，这些优美的性质从理论上保证了我们所得模型结果为全局范围的近似最优解。9.模型的评价及进一步探讨9.1 模型的评价（1）我们设计了求公路与铁路网络中任意两点最小费用路德一般性算法“递推法” 。并证明了该算法的时间复杂度为 。4nO（2）模型一和模型二同样适用于管道、铁路、公路交叉纵横构成任意网络上铺设钢管的问题。例如，如果在附图 6-2 的基础上增加两条管道路线： 与 ，,192A到 146S到这样就铺设的管道成为一个含有 3 个圈得网络。用模型一和模型二对他们进行求解，18所得最小费用为 132.8816 亿元。（3）由于模型二把一公里看作一个点，相对于模型一而言误差较大，我们给出了一种近似的最优算法，因此结果不如模型一理想。但模型二将一个实际问题抽象为图论中的最小费用循环流问题，具有一定的理论价值和实践意义，这对于一些实际问题抽象为数学理论问题，也具有一定的启发性。9.2 模型的进一步探讨对于题目中引出的公路与铁路交叉网问题，如何确定两点间最小费用路德问题，可以直接将其方法推广到更一般的情形，其推广的方法如下：将网络中所有边分为 N 类，每一类定义一个价值函数，求 G 中任意两点的最小价值路；当 N=1 时就是两点之间最短路问题；当 N=2 时就是本题目中公路与铁路交叉构成的网络，可以用文中的递推算法求解；当 N 3 时，仍可用该递推算法求解，但此时的算法的时间复杂度由 N=2 时的多项式时间迅速上升到指数时间，也就是说，对于 N3 的情形递推算法不再有效。我们对其进行了研究，没有找到多项式时间的算法，也无法证明它属于 NP 完全问题，所以，我们提出猜想：该问题在 N 3 时是一个 NP 完全问题。19参考文献1刘宝碇，赵瑞清，随机规划与模糊规划。北京：清华大学出版社，1998。2谢政，李建平。网络算法与复杂性理论。长沙：国防科技大学，1995。3E.米涅卡 .网络和图的最优化算法.北京：中国铁道出版社， 1984.4唐善策等.数据结构用 C 语言描述.北京：高等教育出版社，1999.附表 6-1 问题（1）的钢管订购计划表1 2 3 4 5 6 71 1707（ 1）2157（ 1）2307（ 1）2607（ 1）2557（ 1）2657（ 1）2757（ 1）2 1603（ 1）2053（ 1）2203（ 1）2503（ 1）2453（ 1）2553（ 1）2653（ 1）3 1402（ 2）1902（ 2）2002（ 2）2352（ 2）2252（ 2）2352（ 2）2452 (2)4 986（4）1716（ 4）1816（ 4）2166（ 4）2066（ 4）2166（ 4）2266 (4)5 380（4）1110（ 4）1210（ 4）1560（ 4）1460（ 4）1560 (4)1660 (4)6 205（5）955（5）1055（ 5）1405（ 5）1305（ 5）1405 (5)1505 (5)7 31（7）860（6）960（6）1310（ 6）1210（ 6）1310 (6)1410 (6)8 212（8）712（8）862（8）1162（ 8）1112（ 8）1212 (8)1312 (8)9 642（9）1142（ 9）482（9）842（ 9）792（ 9）842 (9)992（ 9）10920（10）1420（ 10）820（10）620（ 10）570（ 10）620（ 10）770（ 10）11960（11）1460（ 11）860（11）510（ 11）330（ 11）510（ 11）660（ 11）121060（ 12）1560（ 12）960（12）610（ 12）510（ 12）450（ 12）560（ 12）20131212（ 13）1712（ 13）1112（ 13）762（ 13）712（ 13）262（ 13）382（ 13）141280（ 15）1780（ 15）1180（ 15）830（ 15）730（ 15）110（ 14）260（ 15）151420（ 16）1920（ 16）1320（ 16）970（ 16）870（ 16）280（ 16）20（17）附表 6 -2 问题（3）的钢管订购计划表1 2 3 4 5 6 71 1707 2157 2307 2607 2557 2607 27572 1603 2053 2203 2503 2453 2503 26533 1402 1902 2002 2352 2252 2352 24524 986 1716 1816 2166 2066 2166 22665 380 1110 1210 1560 1460 1560 16606 205 955 1055 1405 1305 1405 15057 31 860 960 1310 1210 1281 14108 212 712 862 1162 1112 1162 13129 642 1142 482 842 792 842 99210920 1420 820 620 570 610 77011960 1460 860 510 330 470 640121060 1560 960 610 510 370 560131212 1712 1112 762 712 162 382141280 1780 1180 830 730 110 260151420 1920 1320 970 870 280 2016600 1100 440 800 750 800 95017950 1450 850 500 320 460 630181000 1500 900 550 450 330 500191050 1550 950 600 500 360 550201150