钢管的订购与运输

1、 建模案例：钢管订购及运输优化模型建模案例：钢管订购及运输优化模型20002000年年“网易杯网易杯”全国大学生数学建模竞赛全国大学生数学建模竞赛B B题题 一、问题提出一、问题提出 要铺设一条输送天然气的主管道A1A2A15，能生产这种钢管的厂家一共有:S1,S2,S7 。厂家与管道间的交通网络交通网络已知。假设沿管道或者原来有公路，或者建有施工公路。 为方便计算，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si 个单位，钢厂1单位钢管的出厂销价为pi万元，如下表： I1 2 3 4 5 6 7 SI80

2、0 800 1000 2000 2000 2000 3000 Pi160 155 155 160 155 150 160 1单位钢管的铁路运价铁路运价如下表，1000km以上每增加1至100km运价增加5万元。公路运输费用公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到主管道结点A1,A2, A15 ,而是管道全线）。里程（km） 300 301350 351400 401450 451500 运价（万元） 20 23 26 29 32 里程（km） 501600 601700 701800 801900 9011000 运价（

3、万元） 37 44 50 55 60 （1 1）请制定一个主管道钢管主管道钢管的订购和运输计划，使总费用最小（给出总费用）。 （2 2）请就（）的模型分析：哪个钢厂钢管的销销价的变化价的变化对购运计划购运计划和总费用总费用影响最大，哪个钢厂钢管的产量的上限的变化产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3 3）如果要铺设的管道不是一条线，而是一个树树形图形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图（）的情形给出模型和结果。 需解决的问题需解决的问题： 二、模型假设二、模型假设1.沿铺设的主管道以有公路或者有施工公路。2.在主管道上，

4、每公里卸1单位的钢管。3.公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）4.在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用。5.假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管的运价增加5万元。 三、符号说明三、符号说明iS ：第i个钢厂； 7 , 2 , 1 i is ：第i个钢厂的最大产量； 7 , 2 , 1 i jA ：输送管道（主管道）上的第 j个点； 15, 2 , 1j ip ：第i个钢厂1单位钢管的销价； 7 , 2 , 1i ijx ：钢厂iS 向点jA 运输的钢管量； 7 , 2 , 1 i 15, 2

5、, 1 j jy ：在点jA 与点1jA之间的公路上，运输点jA 向点1jA方向铺设的钢管量；14, 3 , 2 , 1j ijA ：1 单位钢管从钢厂iS到点jA 的最少总费用，即公路运费铁路运费和钢管销价之和； 7 , 2 , 1 i 15, 2 , 1j jmb： 与点jA 相连的第m条公路和铁路的相交点； 15, 3 , 2j，2m jd ：相邻点jA 与1jA之间的距离； 14, 2 , 1j 四、模型的分析、建立、求解四、模型的分析、建立、求解 先看总费用：总费用总费用：总费用由三部分组成： 1) 1) 钢管的订购费钢管的订购费。 支付钢厂订购钢管的费用。因为钢厂生产单位钢管的出厂

6、销价为常量常量，所以在运费相同的情况下，应从销价低的钢厂订购钢管应从销价低的钢厂订购钢管。 1. 模型的分析与决策变量的设置模型的分析与决策变量的设置 根据题目要求，要制定一个主管道钢管主管道钢管的订购订购和运输运输计划，使总费用总费用最小。 2)2) 把钢管从钢厂运到主管道结点钢厂运到主管道结点所需的运费运费。 要注意运输过程中既有铁路，也有公路既有铁路，也有公路。 3)3) 从结点Ai向两边铺设管道的费用铺设管道的费用。 要注意每个结点分别向左右铺设多少分别向左右铺设多少？ 再看订购和运输计划：订购和运输计划： 所谓所谓订购计划订购计划：就是向每个钢厂订购多少钢管。 所谓所谓运输计划运输计

7、划：就是将每个钢厂订购的钢管运输到 那些节点？运多少？ 故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管。 1,2,72,3,15ij 故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管 。 故变量xi可以不要，少用少用7 7个变量个变量！151 iijjxx另外另外，要决定每个结点分别向左右铺设多少？当钢管从钢厂iS 运到点jA 后， 钢管就要向运输点jA 的两边1jjAA段和jjAA1段运输（铺设）管道。 设jy是结点jA向右铺设与1jA向左铺设之间的交交点点（01y，015y） 。 1jA 1jy jA jy 1jA 1,2,

8、72,3,15ij2,3,14j 第二方案第二方案：也可以考虑在Aj左右各设一个变量左右各设一个变量！ 2.求单位钢管从钢厂运到运输点的最小费用求单位钢管从钢厂运到运输点的最小费用方法方法：将图一转换为一个以单位钢管的运输费 用为权的赋权图，再求最短路的权。赋权图，再求最短路的权。 由于运输过程中既有铁路，也有公路，且铁路铁路的运费还是分段函数的运费还是分段函数，与全程运输总距离有关 ；各路运费确是线性函数线性函数。1单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)501600601700701800801

9、9009011000运价(万元)3744505560可考虑将铁路与公路分开考虑分开考虑。 1) 将铁路图转化成费用图（与将铁路图转化成费用图（与Ai对应编号）对应编号）图一图一中去掉公路得铁路图: 将铁路与公路交界的点编号 bj: 1)1) 由于钢厂iS 直接与铁路相连，所以可先求出钢厂iS 到铁路与公路相交点铁路与公路相交点jb（对应于 Aj）的最短路径。 1) 将铁路图转化成费用图将铁路图转化成费用图 (统一统一编号编号)由于钢厂iS 直接与铁路相连，所以可先求出钢厂iS 到铁铁路路与与公公路路相相交交点点jb的最短路径。图一中去掉公路得铁路图: 图一图一 （2 2) ) 依据钢管的铁路运

10、价表， 算出钢厂iS 到铁路与公路相交点jb的最小铁路运输费用， 并把费用作为边权赋给从钢厂iS 到jb 的边. b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140可利用专业的图论软件包图论软件包或MATLABMATLAB软件包软件包求最短路。计算计算Si 到到bi 的最小费用（与的最小费用（与Ai对应编号）对应编号）（1 1) ) 由于钢厂iS 直接与铁路相连， 所以可先求出钢厂iS 到铁铁路路与与公公路路相相交交点点jb（对应于 Aj）的最短路径。 如以S1 为例例：S1

11、到bi的最小费用为: 依据钢管的铁路运价表， 算出钢厂iS 到铁路与公路相交点jb的最小铁路运输费用， 并把费用作为边权赋给从钢厂iS 到jb 的边 再将与jb 相连的公路、运输点iA 及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。以1S 为例得图： b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15b16b1716014080372020020608595105115125130140140 可利用专业的图论软件包图论软件包或MATLABMATLAB软件包软件包求解,如S1到b

12、i的最小费用为:计算计算S1到到bi的最小费用的最小费用(统一编号统一编号) 再将与jb 相连的公路、运输点iA 及其与之相连的要铺设管道的线路（也是公路）添加到图上。 b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140 利用MATLABMATLAB软件包软件包求解,如S1到bi的最小费用为:2) 合并铁路和公路图得以费用为权的交通网络图合并铁路和公路图得以费用为权的交通网络图同时根据单位钢管在公路上的运价规定， 得出每一段公路的运费，并把此费用作为边权赋给相应的边。以1S

13、为例得图： S1到结点到结点Ai的最小费用图的最小费用图 再用图论软件包图论软件包或MATLAB软件包软件包求解,如S1到Ai的最小费用（万元）为:A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281423) 计算计算S1到结点到结点Ai的最小费用的最小费用 A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281424) 计算单位钢管从计算单位钢管从S1到到Ai的订购与运输的最小

14、费用的订购与运输的最小费用加上单位钢管的销售价ip ，得出从钢厂1S购买单位钢管运输到点jA 的最小费用1jA（1160p 万元） 。 A2A3A4A5A6A7A8320.3300.2258.6198180.5163.1181.2A9A10A11A12A13A14A15224.2252256266281.2288302 同理，可用同样的方法求出钢厂2S3S 4S5S 6S 7S 到点jA的最小费用，从而得出从钢厂 Si购买单位钢管运到结点 Aj的最小总费用ijA（单位：万元）为： 5) 从从Si 购买单位钢管运到结点购买单位钢管运到结点Ai的最小费用的最小费用Aij ：A2A3A4A5A6A7

15、A8A9A10A11A12A13A14A15s1320.3300.2258.6198180.5163.1181.2224.2252256266281.2288302s2360.3345.2326.6266250.5241226.2269.2297301311326.2333347s3375.3355.2336.6276260.5251241.2203.2237241251266.2273287s4410.3395.2376.6316300.5291276.2244.2222211221236.2243257s5400.3380.2361.6301285.5276266.2234.2212188

16、206226.2228242s6405.3385.2366.6306290.5281271.2234.2212201195176.2161178s7425.3405.2386.6326310.5301291.2259.2237226216198.2186162ijA从钢厂 Si购买单位钢管运到结点 Aj的最小总费用ijA（单位：万元） (1)(1)铺设总费用铺设总费用总费用总费用= =铺设总费用铺设总费用+ +成本及运输总费用成本及运输总费用=C+W=C+W3.模型的建立模型的建立当钢管从钢厂iS 运到点jA 后， 钢管就要向运输点jA 的两边1jjAA段和jjAA1段运输（铺设）管道。 jy

17、：表示结点jA到1jA之间的分分界界点点（01y，015y） ，铺设 方法如下图： 1jA 1jy jA jy 1jA 1) 1) 目标函数目标函数 铺设总费用：铺设总费用：设jA 向1jjAA段铺设的管道长度为jy ， 则jA 向1jjAA段的运输费用为201)21 (1 . 0jjjyyy；由于相邻运输点jA 与1jA之间的距离为jd ，那么1jA向1jjAA段铺设的管道长为jjyd ，所对应的铺设费用为201jjjjydyd。 1jA 1jy jA jy 1jA 故总的铺设费用为：故总的铺设费用为： 141112020jjjjjjjyydydyC 71512ijijijWAx（2)成本及

18、运输总费用：成本及运输总费用：设若运输点jA向钢厂iS 订购ijx单位钢管，ijA是 1 单位钢管从钢厂iS到点jA的最少总费用， 即公路运费公路运费铁路运费铁路运费和钢钢管销价管销价之和；则钢管从钢厂iS运到运输点jA所需的费用为ijijxA。由于钢管运到1A 必须经过2A ，所以可不考虑1A ，那么所有钢管从各钢厂运到各运输点上的总费用为： 71512ijijijWAx目标函数为：目标函数为：总费用总费用= =铺设总费用铺设总费用+ +成本及运输总费用成本及运输总费用= =C+ +W 141112020jjjjjjjyydydyC 14715112112020jjjjjjijijjijyy

19、dydyfA x 2）约束条件）约束条件（1 1）生生产产能能力力约约束束 因为一个钢厂如果承担制造钢管任务，至少需要生产 500 个单位，钢厂iS 在指定期限内最大生产量为is 个单位： ijijsx 152500 或0152jijx ) 7 , 2 , 1(i （2 2） 需需求求约约束束 运到点jA 的钢管只提供11jjjjAAAA和段的铺设，由于钢管运到1A 必须经过2A ，所以01y。15A是终点，所以015y。 jjjiijyydx1171 )15, 3 , 2j（ 非线性规划模型：非线性规划模型：715141211515227111(1)()(1)min()20205000 1,

20、2,7. .0 , 0 (1,7,2,15) 2,3,15jjjjjjijijijjijiijjjijiijjjijiyydydyfA xxsxistxydijdyyxj 或或综合上述分析，得 由于 LINGO 不能直接处理约束条件：ijijsx 152500或0152jijx，我们可先将此条件改为ijijsx 152，得到如下模型： 5.模型求解模型求解715141211527111(1)()(1)min()2020 1,2,7. .0 , 0 (1,7,2,15) 2,3,15jjjjjjijijijjijijijiijjjijiyydydyfA xxsistxydijdyyxj 1515

21、225000ijiijjjxsx或或152ijijxs 利用利用LINGO软件包编程求解软件包编程求解分析计算结果后发现购运方案中钢厂4S 不不生生产产， 钢厂7S生产但生生产产量量不不足足 5 50 00 0 单单位位。 用 LINGO 求解（gangguan）: Global optimal solution found. Objective value: 1275352. Objective bound: 1275352. Infeasibilities: 0.000000 Extended solver steps: 1 Total solver iterations: 381 Mod

22、el Title: 问题一的模型求解：分三种情况分别求解 Variable Value S1DINGGOULIANG 800.0000 S2DINGGOULIANG 800.0000 S3DINGGOULIANG 1000.000 S4DINGGOULIANG 0.000000 S5DINGGOULIANG 1155.824 S6DINGGOULIANG 1170.176 S7DINGGOULIANG 245.0000 1）不让）不让S7生产的模型求解生产的模型求解7151412115215727111(1)()(1)min()2020, 1,2,70.0 , 0 1,7,2,15 2,3,1

23、5jjjjjjijijijjijijjjijjjjjjijiy ydydyfx Axsixstxydijdyyxj 715141211527111(1)()(1)min()2020 1,2,7.0 , 0 (1,7,2,15) 2,3,15jjjjjjij ijijjijijijiijjjijiy ydydyfAxxsist xydijdyyxj 下面我们采用不不让让钢钢厂厂7S 生生产产和要要求求钢钢厂厂7S 的的产产量量不不小小于于 5 50 00 0 个个单单位位两种方法计算： 添加一个S7生产量为0的约束原模型原模型不让不让S7生产的模型生产的模型 计计算算结结果果：1f1278632

24、（万元） （此时每个钢厂的产量都满足条件） 。 2) 要求钢厂要求钢厂S7的产量不小于的产量不小于500个单位个单位 7151412115215727111(1)()(1)min()2020, 1,2, ,7500.0 , 0 1, ,7,2, ,15 2,3, ,15jjjjjjijijijjijijjjijjjjjjijiy ydydyfx Axsixstxydijdyyxj 715141211527111(1)()(1)min()2020 1,2,7.0 , 0 (1,7,2,15) 2,3,15jjjjjjij ijijjijijijiijjjijiy ydydyfAxxsist xydijdyyxj 计算结果：2f 1279661（万元