钢管订购和运输优化模型 要铺设一条A1→>A2→>…→>A1的输送天然气的主管道,如图1所示(见反 面).经筛选后可以生产这种主管道钢管的钢厂有S,S2…,S·图中粗线表示铁 路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或 者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示 里程(单位:km) 为方便计,1km主管道钢管称为1单位钢管. 个钢厂如果承担制造这种钢管,至少需要生产500个单位.钢厂S在指定期 限内能生产该钢管的最大数量为s个单位,钢管出厂销价1单位钢管为P2万元 如下表: 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 所示(见反 面).经筛选后可以生产这种主管道钢管的钢厂有 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)的要求给出 模型和结果 320 69016 4: 图1
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
1100 70 1150 21750606 图2 一、基本假设 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) 图 2
的运价增加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)将图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 S6(b14 图3铁路网络图 依据钢管的铁路运价表,算出钢厂S到铁路与公路相交点b的最小铁路运输 费用,并把费用作为边权赋给从钢厂S到b的边再将与b,相连的公路、运输点A 及其与之相连的要铺设管道的线路(也是公路)添加到图上,根据单位钢管在公路 上的运价规定,得出每一段公路的运费,并把此费用作为边权赋给相应的边以S1为 例得图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
0.260 20.168 图4钢管从钢厂S1运到各运输点A的铁路运输与公路运输费用权值图 2)计算单位钢管从S到A的最少运输费用 根据图4,借助图论软件包中求最短路的方法求出单位钢管从S1到A,的最少 运输费用依次为:170.7,160.3,140.2,98.6,38,205,3.1,21.2,642,92,96 06,121.2,128,142(单位:万元)加上单位钢管的销售价P2,得出从钢厂S购 买单位钢管运输到点A的最小费用a1依次为:3303,320.3,3002,2586,198, 180.5,163.1,181.2,224.2,252,256,266,281.2,288,302(单位:万元) 同理,可用同样的方法求出钢厂S2、S3S4、S5·S6、S到点A的最小 费用,从而得出钢厂到点的最小总费用(单位:万元)为: 表1S到点A最小费用 A3A4|4s|6 S1|320.33002258.6198|180.516381.2|22.2252256261281.2288302 S,360.3345.2326626650.524126.2269g297301311326233347 375.3|355.2336.6276260.5251241.2203.2237241251266.2273287 S4410.3395.2|376.6316300.5291276.224.2222211221236.2243257 S5400.3|380.2361.6301285.5|276266.2234.2212188206226.2|22824 405.3|385.2366.6306290.5281271.2234.22122011951762161178
6 图 4 钢管从钢厂 1 S 运到各运输点 Aj 的铁路运输与公路运输费用权值图 2）计算单位钢管从 1 S 到 Aj 的最少运输费用 根据图 4，借助图论软件包中求最短路的方法求出单位钢管从 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 的最小 费用，从而得出钢厂到点的最小总费用（单位：万元）为： 表 1 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 2 S 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347 3 S 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287 4 S 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257 5 S 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 6 S 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178
S|425.3405.2386.6326310.5|301291.2259.2237226216198.2186162 2.建立模型 运输总费用可分为两部分 运输总费用=钢厂到各点的运输费用+铺设费用 运输费用:若运输点A向钢厂S.订购x,单位钢管,则钢管从钢厂S,运到运 输点A所需的费用为anx由于钢管运到A1必须经过A2,所以可不考虑A1,那 么所有钢管从各钢厂运到各运输点上的总费用为:∑∑x,a 铺设费用:当钢管从钢厂S运到点A后,钢管就要向运输点A的两边A,A 段和A1A段运输(铺设)管道设A,向AA1段铺设的管道长度为y,则A向 A段的运输费用为01x(1+2+…+y,)= 20(万元);由于相邻运输点 A与Am1之间的距离为AA,那么Am1向A4m1段铺设的管道长为AAH1-t 所对应的铺设费用为 (万元).所以,主管道上的铺设费 用为:∑ 总费用为f=∑∑x+∑ 又因为一个钢厂如果承担制造钢管任务,至少需要生产500个单位,钢厂S在 指定期限内最大生产量为S个单位,故500≤∑x x=0因此本 问题可建立如下的非线性规划模型: min f t1(t1+1)(A,41-1A,+1-t;) 20 +∑∑xa st500≤∑x≤或∑x=0 x≥0i=1;…,7,J=2,…,15 0<t<A
7 7 S 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 186 162 2. 建立模型 运输总费用可分为两部分： 运输总费用=钢厂到各点的运输费用+铺设费用. 运输费用：若运输点 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 因此本 问题可建立如下的非线性规划模型： 14 15 7 . 1 . 1 1 2 1 7 1 15 15 2 2 . 1 ( 1) ( )( 1 ) min ( 20 20 j 2,3, ,15 s.t. 500 0 0 1, ,7, 2, ,15 0 j j j j j j j j ij ij j j i ij j i ij i ij j j ij j j j t t A t A t f x a x n x s x x i j t A + + = = = = = = + + − + − = + + = = = = = 或
3.模型求解 由于 MATLAB不能直接处理约束条件:500c∑x≤S或∑x=0,我们可 先将此条件改为∑x≤S,得到如下模型: mn=2((1+)+(4-M4+1-+∑x,a x=n,J=2,3,…,1 t{∑x 0i=1,…,7,j=2,…15 0≤t≤A 用 MATLAB求解,分析结果后发现购运方案中钢厂S,的生产量不足500单位, 下面我们采用不让钢厂S生产和要求钢厂S1的产量不小于500个单位两种方法计 算 1)不让钢厂S生产 计算结果:f1=1278632(万元)(此时每个钢厂的产量都满足条件) 2)要求钢厂S的产量不小于500个单位 计算结果:f2=1279664(万元)(此时每个钢厂的产量都满足条件) 比较这两种情况,得最优解为,minf=mi(f,f2)=f1=1278632(万元) 具体的购运计划如表2: 表2问题一的订购和调运方案 订购量A444打44A0A2AB和As S1|800 0|201133|200266|000000000 S3 1000 13911186000641000000 0150358242000000415000 S61556 0 35l86333621165 0[0[00D00[00000[01
8 3. 模型求解： 由于 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（万元） 具体的购运计划如表 2： 表 2 问题一的订购和调运方案 订购量 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 14 15 7 . 1 . 1 1 2 1 7 1 15 2 . 1 ( 1) ( )( 1 ) min ( 20 20 j 2,3, ,15 s.t. 0 1, ,7, 2, ,15 0 j j j j j j j j ij ij j j i ij j i ij i j ij j j j t t A t A t f x a x n x s x i j t A + + = = = = = + + − + − = + + = = = =