钢管订购和运输优化模型 要铺设一条A1→>A2→>…→>A1的输送天然气的主管道,如图一所示(见反 面)。经筛选后可以生产这种主管道钢管的钢厂有S,S2,…S7。图中粗线表示铁路 单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建 有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单 位km) 为方便计,1km主管道钢管称为1单位钢管。 个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂S;在指定 期限内能生产该钢管的最大数量为s2个单位,钢管出厂销价1单位钢管为p1万元, 如下表: 5 6 7 2000 20002000 3000 P 160155 160 155 150 160 1单位钢管的铁路运价如下表: 里程(km) ≤300 01~350351~400401~450451~500 运价(万元) 里程(k 501~600601~700701~800801~900901~1000 运价(万元) 55 60 1000km以上每增加1至100km运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。 钢管可由铁路、公路运往铺设地点(不只是运到点A,A2,…,As,而是管道 全线)
1 钢管订购和运输优化模型 要铺设一条 A1 → A2 →→ A15 的输送天然气的主管道, 如图一所示(见反 面)。经筛选后可以生产这种主管道钢管的钢厂有 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)如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构 成网络,请就这种更一般的情形给出一种解决办法,并对图二按(1)的要求给出 模型和结果 320 69016 20ao94103041 4: 图一
2 问题： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 思考题： （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用 影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并 给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构 成网络，请就这种更一般的情形给出一种解决办法，并对图二按（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 A11 A7 11 A1 1 A8 A1 1 A9 11 A1 1 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图一
19{19 1100 70 1150 21750,606 图二 基本假设: 1.沿铺设的主管道以有公路或者有施工公路 2.在主管道上,每公里卸1单位的钢管。 3.公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算) 4.在计算总费用时,只考虑运输费和购买钢管的费用,而不考虑其他费用 5.在计算钢厂的产量对购运计划影响时,只考虑钢厂的产量足够满足需要的情况, 即钢厂的产量不受限制 6.假设钢管在铁路运输路程超过1000km时,铁路每增加1至100km,1单位钢管
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) 图二
的运价增加5万元 二.符号说明: S,:第i个钢厂; s1:第i个钢厂的最大产量 4:输送管道(主管道)上的第j个 P2:第i个钢厂1单位钢管的销价 i=1,2,…,7 xn:钢厂S向点A运输的钢管量: i=1,2,…,7j=1,2,…,15 t:在点A与点AA1之间的公路上,运输点A向点A1方向铺设的钢管量 j=1,2,3,…,14(1=0) an:1单位钢管从钢厂S运到结点A的最少总费用,即公路运费、铁路运费和 钢管销价之和 i=1,2…,7 j=1,2,…15 b,:与点A相连的公路和铁路的相交点 j=2,3,…,15 A1:相邻点A,与A1之间的距离 j=1,2,…,14 模型的建立与求解 问题一:讨论如何调整主管道钢管的订购和运输方案使总费用最小 由题意可知,钢管从钢厂S到运输结点A,的费用a包括钢管的销价、钢管的 铁路运输费用和钢管的公路运输费用。在费用an最小时,对钢管的订购和运输进 行分配,可得出本问题的最佳方案。 l、求钢管从钢厂S,运到运输点A的最小费用 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）将图一转换为一系列以单位钢管的运输费用为权的赋权图
由于钢管从钢厂S运到运输点A要通过铁路和公路运输,而铁路运输费用是 分段函数,与全程运输总距离有关。又由于钢厂S,直接与铁路相连,所以可先求 出钢厂S.到铁路与公路相交点b,的最短路径。如图三 图三铁路网络图 依据钢管的铁路运价表,算出钢厂S,到铁路与公路相交点b,的最小铁路运输 费用,并把费用作为边权赋给从钢厂S到b的边。再将与b,相连的公路、运输点 A1及其与之相连的要铺设管道的线路(也是公路)添加到图上,根据单位钢管在 公路上的运价规定,得出每一段公路的运费,并把此费用作为边权赋给相应的边。 以S1为例得图四
5 由于钢管从钢厂 i S 运到运输点 Aj 要通过铁路和公路运输，而铁路运输费用是 分段函数，与全程运输总距离有关。又由于钢厂 i S 直接与铁路相连，所以可先求 出钢厂 i S 到铁路与公路相交点 j b 的最短路径。如图三 图三 铁路网络图 依据钢管的铁路运价表，算出钢厂 i S 到铁路与公路相交点 j b 的最小铁路运输 费用，并把费用作为边权赋给从钢厂 i S 到 j b 的边。再将与 j b 相连的公路、运输点 Ai 及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在 公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。 以 1 S 为例得图四