钢管订购和运输优化模型 要铺设一条A→42→.→A5的输送天然气的主管道，如图1所示（见反 面).经筛选后可以生产这种主管道钢管的钢厂有S,S2,.,S,·图中粗线表示铁 路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或 者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示 里程（单位：km). 为方便计，1km主管道钢管称为1单位钢管. 一个钢厂如果承担制造这种钢管，至少需要生产500个单位.钢厂S,在指定期 限内能生产该钢管的最大数量为3，个单位，钢管出厂销价1单位钢管为P,万元， 如下表： i 1 2 3 4 5 6 3,80080010002000 20002000 3000 p,160155155160155150 160 1单位钢管的铁路运价如下表： 里程(km)≤300301~350351~400401~450 451-500 运价（万元） 20 23 26 29 32 里程(km) 501~600601-700 701~800801~900901~1000 运价（万元） 37 44 50 55 60 1000km以上每增加1至100km运价增加5万元， 公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）. 钢管可由铁路、公路运往铺设地点（不只是运到点A,42,.,45,而是管道 全线)
1 钢管订购和运输优化模型 要铺设一条 A1 → A2 →→ A15 的输送天然气的主管道, 如图 1 所示(见反 面).经筛选后可以生产这种主管道钢管的钢厂有 1 2 7 S S S , , , .图中粗线表示铁 路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或 者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示 里程(单位：km). 为方便计，1km 主管道钢管称为 1 单位钢管. 一个钢厂如果承担制造这种钢管，至少需要生产 500 个单位.钢厂 i S 在指定期 限内能生产该钢管的最大数量为 i s 个单位，钢管出厂销价 1 单位钢管为 i p 万元， 如下表： i 1 2 3 4 5 6 7 i s 800 800 1000 2000 2000 2000 3000 i p 160 155 155 160 155 150 160 1 单位钢管的铁路运价如下表： 里程(km) ≤300 301～350 351～400 401～450 451～500 运价(万元) 20 23 26 29 32 里程(km) 501～600 601～700 701～800 801～900 901～1000 运价(万元) 37 44 50 55 60 1000km 以上每增加 1 至 100km 运价增加 5 万元. 公路运输费用为 1 单位钢管每千米 0.1 万元（不足整千米部分按整千米计算）. 钢管可由铁路、公路运往铺设地点（不只是运到点 1 2 15 A , A , , A ，而是管道 全线）
问题： (1)请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用） 思考题： (2)请就(1)的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用 影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并 给出相应的数字结果 (3)如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构 成网络，请就这种更一般的情形给出一种解决办法，并对图2按(1)的要求给出 模型和结果. 9 30 1200 17 110 500 1100 210 480 195 3001 115 20 10 45 94 6064 图1 104 2
2 问题： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用). 思考题： （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用 影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并 给出相应的数字结果. （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构 成网络，请就这种更一般的情形给出一种解决办法，并对图 2 按（1）的要求给出 模型和结果. A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 0 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A1 1 A8 A1 1 A9 11 A1 1 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图 1
29 20 1100 210 220 A13 199 0 4o300 1150 600 450 205 759% 4605 图2 一、基本假设 1.沿铺设的主管道以有公路或者有施工公路 2.在主管道上，每千米卸1单位的钢管 3.公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算 4.在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用 5.在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况， 即钢厂的产量不受限制】 6.假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km,1单位钢管 3
3 一、 基本假设 1．沿铺设的主管道以有公路或者有施工公路. 2．在主管道上，每千米卸 1 单位的钢管. 3．公路运输费用为 1 单位钢管每千米 0.1 万元（不足整千米部分按整千米计算） 4．在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用. 5．在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况， 即钢厂的产量不受限制. 6．假设钢管在铁路运输路程超过 1000km 时，铁路每增加 1 至 100km，1 单位钢管 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 0 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A19 130 190 260 100 A2 A3 A4 A5 A6 A7 A8 A1 1 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 A16 A17 A18 A20 (A21) 图 2
的运价增加5万元， 二、符号说明： S,:第i个钢厂： i=1,2,.,7 S,:第i个钢厂的最大产量： i=1,2,.,7 A:输送管道（主管道）上的第j个点： j=1,2,.,15 P,:第i个钢厂1单位钢管的销价 i=1,2,.,7 x:钢厂S,向点A,运输的钢管量： i=12,.,7j=1,2,.15 1,:在点A,与点A之间的公路上，运输点A,向点A方向铺设的钢管量： j=1,2,3,.,14(41=0) a):1单位钢管从钢厂S运到结点A,的最少总费用，即公路运费、铁路运费和 钢管销价之和： i=1,2.,7 j=1,2,.,15 b,:与点A,相连的公路和铁路的相交点： j=2,3.,15 A41:相邻点A,与A1之间的距离： j-1,2,.,14 三、模型的建立与求解 问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小 由题意可知，钢管从钢厂S,到运输结点A,的费用a,包括钢管的销价、钢管的 铁路运输费用和钢管的公路运输费用在费用，最小时，对钢管的订购和运输进行 分配，可得出本问题的最佳方案 1.求钢管从钢厂S,运到运输点A,的最小费用 1)将图1转换为一系列以单位钢管的运输费用为权的赋权图
4 的运价增加 5 万元. 二、符号说明： i S ：第 i 个钢厂； i = 1,2, ,7 i s ：第 i 个钢厂的最大产量； i = 1,2, ,7 Aj ：输送管道（主管道）上的第 j 个点； j = 1,2, ,15 i p ：第 i 个钢厂 1 单位钢管的销价； i = 1,2, ,7 ij x ：钢厂 i S 向点 Aj 运输的钢管量； i = 1,2, ,7 j = 1,2, ,15 j t ：在点 Aj 与点 Aj+1 之间的公路上，运输点 Aj 向点 Aj+1 方向铺设的钢管量； j = 1,2,3, ,14 ( t 1 = 0 ) ij a ：1 单位钢管从钢厂 Si 运到结点 Aj 的最少总费用，即公路运费﹑铁路运费和 钢管销价之和； i = 1,2, ,7 j = 1,2, ,15 bj ：与点 Aj 相连的公路和铁路的相交点； j = 2,3, ,15 Aj. j+1 ：相邻点 Aj 与 Aj+1 之间的距离； j = 1,2, ,14 三、模型的建立与求解 问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小 由题意可知，钢管从钢厂 i S 到运输结点 Aj 的费用 ij a 包括钢管的销价﹑钢管的 铁路运输费用和钢管的公路运输费用.在费用 ij a 最小时，对钢管的订购和运输进行 分配，可得出本问题的最佳方案. 1. 求钢管从钢厂 i S 运到运输点 Aj 的最小费用 1）将图 1 转换为一系列以单位钢管的运输费用为权的赋权图
由于钢管从钢厂S,运到运输点A,要通过铁路和公路运输，而铁路运输费用是 分段函数，与全程运输总距离有关又由于钢厂S直接与铁路相连，所以可先求出 钢厂S到铁路与公路相交点b,的最短路径如图3 图3铁路网络图 依据钢管的铁路运价表，算出钢厂S到铁路与公路相交点b,的最小铁路运输 费用，并把费用作为边权赋给从钢厂S,到b,的边再将与b,相连的公路、运输点A 及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路 上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以S为 例得图4
5 由于钢管从钢厂 i S 运到运输点 Aj 要通过铁路和公路运输，而铁路运输费用是 分段函数，与全程运输总距离有关.又由于钢厂 i S 直接与铁路相连，所以可先求出 钢厂 i S 到铁路与公路相交点 j b 的最短路径.如图 3 图 3 铁路网络图 依据钢管的铁路运价表，算出钢厂 i S 到铁路与公路相交点 j b 的最小铁路运输 费用，并把费用作为边权赋给从钢厂 i S 到 j b 的边.再将与 j b 相连的公路、运输点 Ai 及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路 上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以 1 S 为 例得图 4