钢管的订购和运输优化模型
摘要
本文建立的多元非线性优化模型。问题一在保证天然气管道铺设可以顺利实施的情况下，给出了钢管的订购与运输总费用最小的方案。在求钢管由钢厂运输到站点的费用和铺设钢管时产生的运输费，根据图一，我们通过深度优先遍历的方法对整个图一进行路径搜索，然后根据每条搜索到的路径上的铁路和公路上的不同权重，找到了各个钢厂到各个天然气管道上的站点的最佳路径。对于整个优化过程我们给出了相关的算法，并用matlab软件编程，经过一系列计算之后，得出了最优的订购与运输方案。对于问题 1，我们求得的最优解为（具体方案见表五）： 总费用 S7 S3 S5 S6 S1 S2 S4 800 对于问题2我们经过计算比较得出：S6钢管销价的变化对购运计划和总费用影响最大。S1的生产上限的变化购运计划和总费用影响最大。
对于问题 3，当天然气管道呈现的是一个树状图的时候，我们得到的最优解
为（具体方案见表六）: 总费用 S7 S3 S5 S6 S1 S2 S4 800
关键字：非线性优化 深度优先遍历 最佳路径
800 1000 0 1450 1853 0 1.4148?106800 1000 0 1190 1181 0 1.2786?106
1
一、问题重述 要铺设一条A1?A2???A15的输送天然气的主管道, 如图一所示(见下
页)。经筛选后可以生产这种主管道钢管的钢厂有S1,S2,?S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si个单位，钢管出厂销价1单位钢管为pi万元，如下表： i 1 800 160 2 800 155 3 1000 155 301～350 23 4 2000 160 351～400 26 5 2000 155 6 2000 150 7 3000 160 451～500 32 si pi 1单位钢管的铁路运价如下表： 里程(km) 运价(万元) 里程(km) 运价(万元) 501～600 37 601～700 44 701～800 50 801～900 55 901～1000 60 ≤300 20 401～450 29 1000km以上每增加1至100km运价增加5万元。?
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点A1,A2,?,A15，而是管道全线）。
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。
2
290 S3 S2 690 1200 720 202 1100 20 12 195 3061150 600 10 5 194 A6606 2 750 A4 A2 A3 301 A5 10 31 201 A8A7S1 42 70 10 170 520 88 462 S5 10 220 A11 S4 320 160 70 30 70 62 S6 110 420 A15 500 A14 20 30 S7 20 690 160 A13 210 A12 480 680 A9A10 300 450 80 3 104 A1 205 图一 290 S3 S2 690 1200 720 A16 202 1100 20 195 3061150 600 10 5 194 A6 A5 606 10 12 31 300 A10 A9 680 480 S1 42 170 520 88 S4 A18 160 130 160 70 A20 100 30 260 S6 70 (A21) 320 A19 110 62 420 30 S7 20 690 20 A15
190 462 10 500 A14 A17 70 S5 10 220 A13 210 A12 A11 201 A8205 A7 450 80 2 750 A4 A3 301 A2 图二 3 104 A1
3
二、模型假设
1、假设沿管道或者原来有公路，或者建有施工公路；
2、运费只按铁路、公路里程收取，即不考虑火车、汽车由于停靠站等其他一切外因带来的费用；
3、钢管在铺设过程中以1km为单位进行铺设；
4、钢管可由铁路、公路运往铺设路线任一地点；
5、所有钢管在指定期限内都能按时生产并运送指定地点； 6、钢管铺设过程中由站点向左右两边进行铺设。
三、符号说明
Si ：第i个厂?i?1,2?7?； ：第j个站点?j?1,2?15?；
Aj
mij : Si向Aj运送的钢管量 单位（km）； maxi:Si在指定期限内的最大生产量 单位（km）； Rj : Aj向右铺设的钢管量 单位（km）； Lj : Aj向左铺设的钢管量 单位（km）；
Dj : Aj到Aj?1间的距离?j?1,2?14? 单位（km）；
D0 Pi TijDijM :管道全线总长 单位（km）；
: Si钢管出厂销价?i?1,2?7? 单位（万元/单位）；
: Si向Aj运送一单位钢管所需的铁路费 单位（万元/单位）； : Si向Aj运送一单位钢管所需的公路费 单位（万元/单位）；
：购买钢管所花的总费用；
Y :由厂到站点所需运输总费；
Y0 W ：由站点到铺设地点所需运输总费；
:订购和运输钢管所需总费用 单位（万元）。
4
四、问题分析
问题一是在一定约束条件下的非线性优化问题，由题意知，拟建立以总费用为目标函数来寻求最优解。总费用W由钢管的购买费、厂到站点的运输费以及站点到铺设地点的运输费三部分组成。 一、钢管的购买费可由在每个厂的购买量与每个厂的出厂销价的线性运算得到 。在每个厂购买的钢管量必须大于500km ，否则则不在该厂购买。可以构造一个1?7的矩阵S，那么当Si为0时，表示不在第i个钢厂购买，否则则在第i个钢厂购买大于500km的钢量。二、要求得每个钢厂到站点的运输费需先知道每个厂到各个站点的钢管输送量，以及所选择的路线即铁路总长和公路总长，所以需要首先计算出各个钢厂到每个站点的最佳运输路径，使得平均单位公里的运输费用最小。但是由于铁路每公里的运输费用不是线性变化，而是变化不均匀的分段函数。在这里，我们利用深度优先遍历，找到某个厂到达各个站点的所有路径，然后根据每条路径的铁路和公路里程数计算出平均每公里运输费用最小的一条。以此类推，计算出所有钢厂到所有站点的最佳路径。 三、在站点到铺设地点的运输费问题上，如果我们认为车边向前走边进行铺设，即边走边将钢管放下，那么就需要通过积分来计算。但是，尽管用积分算下来结果会很精确，但在实际中不可能这样实施。另外，这也与题目中不足整公里的按整公里计算相矛盾。所以，我们假设以1km为单位进行铺设，即铺设中车每向前开1km便将1km的钢管放下。由于铺设管道是线型的，除了两个端点外，每个站点需要往两边进行铺设管道。所以，假设第j个站点往左、右边铺设管道为Rj和Lj公里，则由站点到铺设地点的运输费就可以通过等差数列求和得到。
问题二即为对问题一中模型的灵敏度分析，在讨论各厂的钢管销价和生产上限对购运计划和总费用的影响时，只让其中一个量变化，其他一切条件皆不变，即逐个变量单独分析。
问题三即为问题一中模型的推广，在问题一的基础上将站点向左右两边铺设变为向三个方向铺设，按问题一处理即可。
五、模型建立（问题一）
总费用W由钢管的购买费M、厂到站点的运输费Y以及站点到铺设地点的运输费Y0三部分组成，则
W?M?Y?Y0
在第i个厂的购买费应为15个站点在第i个厂的购买总量与该厂销价的乘积
15总和，即?MijPj，则总购买费
j?1715ij M?
?(?mi?1j?1Pj)
5