钢管订购和运输计划的最小费用问题(崔王李).doc

钢管订购和运输计划的最小费用问题崔亚奇，王莹桂，李润泽指导教员：数模组（海军航空工程学院，烟台，264001）摘要：这是一个求最少费用以及如何取得最少费用的问题。针对铁路运费因里程不同而不等，首先，将铁路转化为等价公路，构造无向图并求其最短路径；进一步将问题转化一个非线性规划问题，建模并用Lingo求解即得。在研究销价的变化对购运计划和总费用影响时，采用了分别波动销价，观察对最小费用的影响的方法；而在研究上限的变化对购运计划和总费用的影响时，则采用了放松各厂钢管生产上限约束条件均到所需钢管的总量以上，通过分析对其购买量的影响程度来确定。关键字：等价公路，图的最短路径，Floyd算法，非线性规划。1.问题的提出现要铺设一条的输送天然气的主管道。所给条件如下：一个钢厂如果承担制造这种钢管，至少需要生产500个单位（1km主管道钢管称为1单位钢管）。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，经筛选后可以生产这种主管道钢管的钢厂有。在运输过程中所要经过的铁路、公路的运费为已知，其中铁路运费随着距离的增加而改变，公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。沿铺设的管道或者原来有公路，或者建有施工公路。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。2.问题的分析对于问题一，我们分以下两步进行。首先，解决如何用最少运费把钢管从钢厂运到各管道节点，这是一个图的最小路径问题，由于铁路运费和里程有关，所以我们要对其进行等价转换，即把铁路等价为同等运费的公路，再和原有公路一起建构一个具有权值（权值为一单位钢的运费）的完全图，对其利用Floyd算法求出最短路经，我们就得到了从钢管厂到所要铺设的管道节点之间的最少运费路径。然后，解决从各个钢厂运到管道节点的钢管如何铺设问题。如果我们从节点往一个方向或者跨节点铺设，势必会增加我们的总费用，所以我们从节点分别向两边铺设，很好的解决了运费问题。建立以钢管的价格费用和运输费用（包括铺设过程中的运费）之和为最小的目标函数，用非线性规划求解，最终得到问题的答案。问题二对于钢厂钢管的销价的变化对总费用影响，我们可以采用分别让钢厂的销价在一定范围内改变，做出销价和总费用的敏感程度曲线，对其分析即可得出影响的大小；钢厂钢管产量上限的变化对购运计划和总费用的影响，可以通过放开生产上限这个约束条件， 从各钢厂供货数量的变化中得出。问题三是问题一的一个推广，可以在模型一的基础上修改得到。3.问题的假设1.假设沿管道的公路（施工公路）运输费用也为每公里0.1万元（不足整公里部分按整公里计算）。2.假设公路运输费用不是整公里的按整公里计算是合理的。3.假设不考虑铁路、公路及施工公路的运输能力限制，并且运输单位可提供足够的火车与汽车。4.只考虑订购费用和运输费用，不考虑装卸等其它费用。5.假设在铺设过程中，每公里卸下一单位钢管是合理的。4.符号的说明：钢厂；：火车站；：管道节点；: 钢厂在指定期限内生产钢管的最大数量（单位：单位钢管）；: 钢厂单位钢管的出厂价格（单位：万元）；：从 钢厂运到的钢管数量（单位：单位钢管）；：与之间所需要的钢管数量（单位：单位钢管）；：表示1单位钢管从 钢厂到的最少运费（单位：万元）；：表示1单位钢管从 钢厂到的最小费用（单位：万元）；：运到的钢管总数（单位：单位钢管）； ：从向方向铺设的钢管的数量（单位：单位钢管）；其中：，。5.模型的建立与求解5.1问题一的求解5.1.1最短路径的求解首先，将铁路运输转化为公路运输，具体步骤如下：仅考虑铁路运输，以火车站及钢厂为节点，并以铁路里程为权值，构造一个带有权值的无向图。用Floyd算法求出到最短路经，进一步根据铁路里程和运费之间的关系，计算出到所需要的费用，现在假设到之间有一条所需运费为的公路，并用这些公路代替原来铁路。至此，我们已经把铁路运输转化为公路运输的问题。进一步分析，假设公路与原公路可以组成一个新的无向图。对其边进行赋权值，其中假设公路的权值为 ，原公路的权值为其运费（可由已知条件求得），如果到之间的公路与原公路发生冲突（即任意两节点之间出现两条边），我们就取权值较小的边构成无向图。用Floyd算法求出到管道节点之间的最短路经，即从运输一单位钢管到管道节点的最少运费。由所给条件知的钢管价格为，最终得到一单位钢运到管道节点需要的总费用为。上述算法程序见附录。5.1.2f的建立和求解由题目可知，这是一个非线性规划问题，我们要找出其目标函数和约束条件。其中目标函数可分为两部分：1. 所有钢管从钢厂运到()的费用： 2.铺设钢管所需要的费用：在铺设中，我们采取从分别向两边铺设的方法，从向方向铺设的钢管的数量为，在假设条件每公里卸下一单位钢的情况下，其运费为等差数列的前项和。得到总的铺设费用：综上所述，我们可以得到目标函数如下：由已知和实际问题可得以下约束条件：1.所购买的钢管的总数量应不少于所需求量2.要保证不重复铺设，向左与向右铺设的数量和应与相等3.从向两边铺设的钢管的总量应与一致4.运到的钢管数量应与从各分别购买的数量和相符5.各个变量的取值范围特别地，因为钢厂有一生产上限和一下限，对有或综上所述模型可建立为：s.t. 或我们可以利用Lingo对模型求解（程序见附录），计算结果如下：最少费用为：128.13亿元。订购计划和运输方案如下：表一：钢管的订购计划 (单位:一单位钢)A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15总计S1000322.711.820026500000000800S20179065256003000000000800S300003360006640000001000S40000000000000000S50050880.311.7000035141500001366S6000000000008633378601205S70000000000000000总计0179508387.7615.52002653006643514158633378605171主管道钢管的运输方案如下：括号内的数字为订购的钢管的数量,火车站均用数字标注。从运到的最少运费路径和钢管数量：S1222120A5A4(322.7) S1222120A5(11.8)S12221A6(200) S1A7(265) 从运到的最少运费路径和钢管数量： S224191816A2(179) S22423222120A5A4(65) S22423222120A5(256) S224A8(300)从运到的最少运费路径和钢管数量： S3262423222120A5(336)S326A9(664)从运到的最少运费路径和钢管数量：S53029282624191817A3(508)S5302928262423222120A5A4(80.3)S5302928262423222120A5(11.7) S5302928A10(351) S530A11(415) 从运到的最少运费路径和钢管数量：S63735332928A10(175)S637353334A12(86)S63735A13(333) S6A14(541)5.2问题二的求解5.2.1钢厂的销价对总费用的影响我们可以分别让每一个钢厂的价格在一定范围内有规律地浮动（万元），求目标函数的最少费用，以价格变化量为自变量，最少费用为因变量对其线性拟合，可分别得到每个钢厂价格变动对最小费用影响的函数，即目标函数在最优值附近对七个钢厂钢管价格敏感程度的曲线。表二：价格变动时的最少费用（单位：万元）-9-5-1159S11.26761.27081.27401.275601.27881.2820S21.26761.26921.27401.27561.27881.2820S31.26581.26981.27381.27581.27981.2838S41.27481.27481.27481.27481.27481.2748S51.26231.26791.27351.27581.27971.2811S61.26001.26801.27351.27581.27951.2831S71.27241.27351.27461.27511.27601.2768在同一坐标系中做出其图像如下：图一：目标函数对价格的敏感程度曲线观察图像我们看出，在范围内，的波动最大，因此第五个和第六个钢厂的钢管的价格对总费用影响较大。5.2.2钢厂钢管产量的上限对购运计划和总费用的影响由问题一可以发现从四厂购得的钢管总量原未达到它们的生产上限，所以它们不会对目标函数构成太大的影响，不必考虑；因为钢管的总需求量为5717个单位，因此我们可将三厂的生产上限均改为6000个单位，观察三厂提供的钢管的数量,提供数量明显增多的钢厂对购运计划和总费用的影响最大。经计算可得:表三：上限改变时钢管的量钢厂S1S2S3钢管数量29090514由表三很明显地看出,由原来的800单位增长到2909单位,我们可以肯定地说, 的上限对购运计划和总费用的影响最大。5.3问题三的求解问题三是问题一的推广，当铺设的管道不再为一条线时，我们不能再仅向两边铺，而应考虑到所有和节点相连的边，我们只需对铺设费用及其相关的约束函数进行修改。设为从向铺设的数量，则铺设费用修改为：其中管道节点的个数由原来的15个变为21个，为所有与相连的管道节点，若不与相连，则。参照问题一的求解，模型建立如下：s.t. 或同问题一的求解方法，计算结果如下：最少费用为：140.663亿元订购计划和运输方案如下：表四：钢管的订购计划 (单位:一单位钢) s1 s2 s3 s4 s5 s6 s7 总计 A100000000 A2017900000179 A3004050400508 A453215013900470 A533002850000615 A6200000000200 A7265000000265 A8030000000300 A9006640000664 A1000001262250351 A11000038000380 A12 000001110111 A13000003930393 A14000005700570 A15000001650165 A160042000042 A17000015500155 A180000080080 A190000095095 A20000002600260 A21000001000100 总计800800100001304199905903主管道钢管的运输方案如下括号内的数字为订购的钢管的数量,火车站用数字标注。从运到的最少运费路径和钢管数量：S1222120A5A4(5)S1222120A5(330)S12221A6(200)S1A7(265)从运到的最少运费路径和钢管数量：S224191816A2(171)S224S1222120A5A4(21)S224A8(300)从运到的最少运费路径和钢管数量；S32624191817A3(4)S32624S1222120A5A4(5)S32624S1222120A5(285)S326A9(664)S3A16(42)从运到的最少运费路径和钢管数量：S53029282624191817A3(504)S5302928262423222120A5A4(139)S53011A10(273)S5A17A11(380)S5A17(155)从运到的最少运费路径和钢管数量：S635332928A10(225)S635A13A12(110)S635A13(393)S6A14(570)S614A15(165)S635A18(80)S635A18A19(95)S6A20(260) S6A21（重合）(100)6.模型的评价和改进本模型首先把铁路等价为公路，然后应用图论知识，把整个网络变成完全图，利用 Floyd 算法求出图中任意两顶点之间的最短路径，即最小费用。再应用非线性规划知识和Lingo软件求解。并对更一般的树形管道路线，给出了解决办法。模型求解速度快，对实际问题有一定的指导意义。参考文献1 卜月华，图论及其应用，东南大学出版社，2003。2 李占利，运筹学简明教程，西安：西安工业出版社，2004。3 袁亚湘、孙文瑜，最优化理论与方法，科学出版社，2001。附录：最短路径得求取：clear;clc;M=10000;%铁路转化为公路 a=zeros(39,39);a(16,18)=450,a(17,18)=80,a(18,19)=1150,a(19,24)=1100,a(24,25)=1200;a(24,26)=720,a(26,27)=690,a(26,28)=520,a(28,29)=170,a(29,32)=690;a(29,30)=88,a(30,31)=462,a(29,33)=160,a(33,35)=320,a(33,34)=70;a(35,37)=160,a(36,37)=70,a(37,38)=290,a(38,39)=30,a(20,21)=306;a(21,22)=195,a(22,23)=20,a(23,24)=202;a=a+a;a(find(a=0)=M;path_a=zeros(length(a);for k=16:39 for i=16:39 for j=16:39 if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end endend;for i=1:39 for j=1:39 if 0a(i,j)&a(i,j)=300 a(i,j)=200, elseif a(i,j)=350 a(i,j)=230, elseif a(i,j)=400 a(i,j)=260, elseif a(i,j)=450 a(i,j)=290, elseif a(i,j)=500 a(i,j)=320, elseif a(i,j)=600 a(i,j)=370, elseif a(i,j)=700 a(i,j)=440, elseif a(i,j)=800 a(i,j)=500, elseif a(i,j)=900 a(i,j)=550, elseif a(i,j)=1000 a(i,j)=600, else a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end endendc(1,:)=a(1,23),a(1,25),a(1,27),a(1,32),a(1,31),a(1,36),a(1,39);c(2,:)=a(2,23),a(2,25),a(2,27),a(2,32),a(2,31),a(2,36),a(2,39);c(3,:)=a(3,23),a(3,25),a(3,27),a(3,32),a(3,31),a(3,36),a(3,39);c(4,:)=a(4,23),a(4,25),a(4,27),a(4,32),a(4,31),a(4,36),a(4,39);c(5,:)=a(5,23),a(5,25),a(5,27),a(5,32),a(5,31),a(5,36),a(5,39);c(6,:)=a(6,23),a(6,25),a(6,27),a(6,32),a(6,31),a(6,36),a(6,39);c(7,:)=a(7,23),a(7,25),a(7,27),a(2,32),a(7,31),a(7,36),a(7,39);c(8,:)=a(8,23),a(8,25),a(8,27),a(8,32),a(8,31),a(8,36),a(8,39);c(9,:)=a(9,23),a(9,25),a(9,27),a(9,32),a(9,31),a(9,36),a(9,39);c(10,:)=a(10,23),a(10,25),a(10,27),a(10,32),a(10,31),a(10,36),a(10,39);c(11,:)=a(11,23),a(11,25),a(11,27),a(11,32),a(11,31),a(11,36),a(11,39);c(12,:)=a(12,23),a(12,25),a(12,27),a(12,32),a(12,31),a(12,36),a(12,39);c(13,:)=a(13,23),a(13,25),a(13,27),a(13,32),a(13,31),a(13,36),a