钢管订购和运输优化模型 要铺设一条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 为例得图四
b11b12b3 3075605194120 A4 A5 A6 A8A9A10A11A12A13A14A15 图四钢管从钢厂S1运到各运输点A,的铁路运输与公路运输费用权值图 2)计算单位钢管从S到A,的最少运输费用 根据图四,借助图论软件包中求最短路的方法求出单位钢管从S到A,的最少 运输费用依次为:170.7,160.3,1402,98.6,38,205,3.1,21.2,642,92,96 106,121.2 42(单位:万元)。加上单位钢管的销售价P,得出从钢厂S1 购买单位钢管运输到点A的最小费用a1依次为:3303,3203,302,2586,198, 180.5,163.1,181.2,2242,252,256,266,281.2,288,302(单位:万元)。 同理,可用同样的方法求出钢厂S2·S3S4·S5S6、Sn到点A的最小 费用,从而得出钢厂到点的最小总费用(单位:万元)为 表一S到点A最小费用 9 alo all a12 al3 a14 al5 sl320.3300.2258.6198180.5163181.2224.2252256266281.2288302 s2360.3345.2326.6266250.5241226.2269.2297301311326.233334 s3375.3355.2336.6276260.5251241.2203.2237241251266.2273287 s4410.3395.2376.6316300.5291276.2244.2222211221236.2243257 s5400.3380.2361.6301285.5276266.2234.2212188206226.2228242 s6405.3385.2366.6306290.5281271.2234.22122011951762161178 s7425.3405. 6326310.5301291.2259.2237226216198.2186162 2、建立模型
6 图四 钢管从钢厂 1 S 运到各运输点 Aj 的铁路运输与公路运输费用权值图 2）计算单位钢管从 1 S 到 Aj 的最少运输费用 根据图四，借助图论软件包中求最短路的方法求出单位钢管从 1 S 到 Aj 的最少 运输费用依次为：170.7，160.3，140.2，98.6，38，20.5，3.1，21.2，64.2，92，96， 106，121.2，128，142（单位：万元）。加上单位钢管的销售价 i p ，得出从钢厂 1 S 购买单位钢管运输到点 Aj 的最小费用 j a1 依次为：330.3，320.3，300.2，258.6，198， 180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）。 同理，可用同样的方法求出钢厂 2 S ﹑ 3 S ﹑ 4 S ﹑ 5 S ﹑ 6 S ﹑ 7 S 到点 Aj 的最小 费用，从而得出钢厂到点的最小总费用（单位：万元）为： 表一 i S 到点 Aj 最小费用 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 s1 320.3 300.2 258.6 198 180.5 163 181.2 224.2 252 256 266 281.2 288 302 s2 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347 s3 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287 s4 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257 s5 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 s6 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178 s7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 186 162 2、建立模型
运输总费用可分为两部分: 运输总费用=钢厂到各点的运输费用+铺设费用 运输费用:若运输点A,向钢厂S订购x单位钢管,则钢管从钢厂S运到运 输点A所需的费用为anx°由于钢管运到A1必须经过A2,所以可不考虑A1,那 么所有钢管从各钢厂运到各运输点上的总费用为;∑∑不 铺设费用:当钢管从钢厂S,运到点A后,钢管就要向运输点A的两边A,4 段和A/1A,段运输(铺设)管道。设A向AA1段铺设的管道长度为y,则A 向A4A1段的运输费用为01×(1+2+…+y) (万元);由于相邻运输 点A与A1之间的距离为AH,那么A向AA+1段铺设的管道长为 AA+-1,所对应的铺设费用为 (万元)。所以,主管 道上的铺设费用为 总费用为-+(b出,m=+= 2 0 2 又因为一个钢厂如果承担制造钢管任务,至少需要生产500个单位,钢厂S在 指定期限内最大生产量为s,个单位,故500≤ 0因此本 问题可建立如下的非线性规划模型: min f= 1(1+)+(4-14+1-)+S xi= j= x 0i=1…,7,j=2,…,1 、模型求解:
7 运输总费用可分为两部分： 运输总费用=钢厂到各点的运输费用+铺设费用。 运输费用：若运输点 Aj 向钢厂 i S 订购 ij x 单位钢管，则钢管从钢厂 i S 运到运 输点 Aj 所需的费用为 ij ij a x 。由于钢管运到 A1 必须经过 A2 ，所以可不考虑 A1 ，那 么所有钢管从各钢厂运到各运输点上的总费用为： = = 15 2 7 j i 1 ijaij x 。 铺设费用：当钢管从钢厂 i S 运到点 Aj 后，钢管就要向运输点 Aj 的两边 Aj Aj+1 段和 Aj−1Aj 段运输（铺设）管道。设 Aj 向 Aj Aj+1 段铺设的管道长度为 j y ，则 Aj 向 Aj Aj+1 段的运输费用为 ( ) 20 1 0.1 (1 2 ) + + + + = j j j t t y （万元）；由于相邻运输 点 Aj 与 Aj+1 之间的 距离 为 Aj. j+1 ，那么 Aj+1 向 Aj Aj+1 段铺设的 管道 长为 j j j A − t . +1 ，所对应的铺设费用为 ( )( ) 20 j. j 1 j 1 j. j 1 j A − t + A − t + + （万元）。所以，主管 道上的铺设费用为： ( ) ( )( ) = + + − + − + 14 + 1 . 1 . 1 20 1 20 1 j j j j j j j j j t t A t A t 总费用为： ( ) ( )( ) = = = + + − + − + + = + 7 1 15 2 14 1 . 1 . 1 20 1 20 1 i j j j j j j j j j j i j i j t t A t A t f x a 又因为一个钢厂如果承担制造钢管任务，至少需要生产 500 个单位，钢厂 i S 在 指定期限内最大生产量为 i s 个单位，故 i j ij x s = 15 2 500 或 0 15 2 = j= ij x 因此本 问题可建立如下的非线性规划模型： 3、模型求解： 0 0 1, ,7, 2, ,15 500 0 j 2,3, ,15 . . 20 ( )( 1 ) 20 ( 1) min ( . 1 1 5 2 1 5 2 7 1 1 5 2 7 1 1 4 1 . 1 . 1 = = = = = + − + − + + = + = = = = = = + + j j j i j j i j j i j i i i j j j i i j i j j j j j j j j j j t A x i j x s x x n st x a t t A t A t f 或
由于 MATLAB不能直接处理约束条件:500c∑x≤S或∑x=0,我们可 先将此条件改为∑x≤S,得到如下模型: inf=∑ (,+1),(4 xi=ni s1∑xsS 0i=1…,7,j=2,…,15 用 MATLAB求解,分析结果后发现购运方案中钢厂S的生产量不足500单位, 下面我们采用不让钢厂S,生产和要求钢厂S的产量不小于500个单位两种方法计 算 1)不让钢厂S生产 计算结果:f1=1278632(万元)(此时每个钢厂的产量都满足条件) 2)要求钢厂S的产量不小于500个单位 计算结果:f2=1279664(万元)(此时每个钢厂的产量都满足条件) 比较这两种情况,得最优解为,mnf=mn(f,f2)=f1=1278632(万元) 具体的购运计划如表二 表二问题一的订购和调运方案 订购量A2A A 20113320026600 1791 14295|003000000000 S31000 13911 86[000640000000 0「0「0|010|0 0 0 0 00|0
8 由于 MATLAB 不能直接处理约束条件： i j ij x s = 15 2 500 或 0 15 2 = j= ij x ，我们可 先将此条件改为 i j ij x s = 15 2 ，得到如下模型： 用 MATLAB 求解，分析结果后发现购运方案中钢厂 7 S 的生产量不足 500 单位， 下面我们采用不让钢厂 7 S 生产和要求钢厂 7 S 的产量不小于500个单位两种方法计 算： 1）不让钢厂 7 S 生产 计算结果： f 1 = 1278632（万元）（此时每个钢厂的产量都满足条件）。 2）要求钢厂 7 S 的产量不小于 500 个单位 计算结果： f 2 = 1279664 （万元） （此时每个钢厂的产量都满足条件）。 比较这两种情况，得最优解为， 1 2 1 min f = min( f , f ) = f =1278632（万元） 具体的购运计划如表二： 表二 问题一的订购和调运方案 订购量 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 800 0 201 133 200 266 0 0 0 0 0 0 0 0 0 S2 800 179 11 14 295 0 0 300 0 0 0 0 0 0 0 S3 1000 139 11 186 0 0 0 664 0 0 0 0 0 0 0 S4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 S5 1015 0 358 242 0 0 0 0 0 0 415 0 0 0 0 S6 1556 0 0 0 0 0 0 0 0 0 351 86 333 621 165 S7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1, ,7, 2, ,15 j 2,3, ,15 . . 20 ( )( 1 ) 20 ( 1) min ( . 1 1 5 2 7 1 1 5 2 7 1 1 4 1 . 1 . 1 = = = = + − + − + + = + = = = = = + + j j j i j j i j i i i j j j i i j i j j j j j j j j j j t A x i j x s x n st x a t t A t A t f