钢管订购和运输
要铺设一条A1?A2???A15的输送天然气的主管道, 如图一所示。经筛选后可以生产这种主管
道钢管的钢厂有S1,S2,?S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
290 S3 S2 690 1200 720 202 1100 20 195 3061150 600 10 5 194 A6A5 606 10 31 201 A8S1 12 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 A9300 A10 450 205 A780 A3 301 104 A2 A1 3 2 750 A4 图一
为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si个单位，钢管出厂销价1单位钢管为pi万元，如下表：
i 1 800 160 2 800 155 3 1000 155 4 2000 160 5 2000 155 6 2000 150 7 3000 160 si pi
1单位钢管的铁路运价如下表：
里程(km) 运价(万元) ≤300 20 301～350 23 351～400 26 401～450 29 451～500 32
里程(km) 运价(万元)
1000km以上每增加1至100km运价增加5万元。?
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点A1,A2,?,A15，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
摘要：本文建立一个钢管订购和运输模型，从钢厂到主管道结点的运费是影响总费用的重要因素。为使总费用最小，须使从钢厂到主管道结点的运费——钢管运输费最小。对求网络中最短路径的Dijkstra算法进行改进，得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径）。在此基础上，建立起描述总费用的函数，把钢管的订购和运输问题归结为在一定约束条件下求最小总费用的二次规划问题。
对于问题（１），运用Lingo软件包求出了较优的订购和运输计划（见表4，表5），其最小费用为1278632万元。对于问题（2）而言，可得出钢厂S6钢厂销价变化对总费用影响最大，S5,S6钢厂钢管的销价的变化对购运计划影响最大，S1钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。
关键词：穷举法 非线性规划
501～600 37 601～700 44 701～800 50 801～900 55 901～1000 60 一、 问题重述和分析
要铺设一条A1?A2???A15的输送天然气的主管道，如图一所示,经筛选后可以生产这种主管道的钢厂有S1,S2,?,S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。
为了方便，1km主管道称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大生产数量为si个单位，钢厂出厂销价为pi万元，如下表：
表1
i si 1 800 160 2 800 155 3 1000 155 4 2000 160 5 2000 155 6 2000 150 7 3000 160 pi 1单位钢管的铁路运价如下表： 里程（km） 运价（万元） 里程（km） 运价（万元）
?300 301~350 20 501~600 37 23 601~700 44 表2 351~400 26 701~800 50 401~450 29 801~900 55 451~500 32 901~1000 60 1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。
管道可由铁路、公路运往铺设地点（不只是运到点A1?A2???A15，而是管道全线）。 要求：
（1） 制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用。
（2） 就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个
钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
二、 基本假设
1． 在计算运费时，沿管道铺设路线上的公路与其它普通公路相同（1单位钢管每公里0.1万元）； 2． 订购的钢管数量刚好等于需要铺设的钢管数量；
3． 管道可由铁路、公路、管道全线运往铺设地点（不只是运到点A1,A2,?,A15）；
4． 模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如不计换车、转站的时间和费用，不计装卸费用等；
5． 不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失； 6． 销售价和运输价不受市场价格变化的影响。
三、符号说明
Si ： si：
第i钢管厂
表示Si的最大生产能力
Aj： 表示需要铺设管道路径上的车站
xi j： ci j：
从所有Si运往Aj的钢管数
表示单位钢管从Si地运往Aj地的最小费用 从Si订购钢管的单位价格
pi：
Q： 订购的所有钢管全部运到Aj(j?1,2,?,15)点的总运费
T： 当钢管从钢厂Si运到点Aj后，钢管向Aj的左右两边运输（铺设）管道的运输费用 Z ：
用于订购和运输的总费用
yj： 运到Aj地向左铺设的数目 zj： 运到Aj地向右铺设的数目
d： 单位钢管1公里的公路运输费用 Aj, j?1： 表示Aj和Aj?1之间需要铺设的管道长度
四、 模型的建立与求解
问题一
1、 模型的建立
钢管的订购和运输方案是直接影响工程费用的主要原因，因此，选取费用最小的路线运送货物，合理的订购计划是决定该工程费用的重要因素，首先利用图论的方法，来确定从钢管生产厂家到施工结点的费用最小路线，然后建立工程费用的优化模型，从中优化出最佳购运方案。
对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段。欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i地运往j地的最优路线（费用最小）；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往j地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j为终点的钢管只铺到与j点相邻的两段管道上。因此，本问题可以按以下步骤求解。
第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。
si(i?1,2,?7)表示钢管厂Si(i?1,2,?7)的最大生产能力，Aj(j?1,2,?,15)表示需要铺设钢管路
径上的车站。假设从Si运往Aj的钢管用于铺设Aj点左右侧的钢管数为xi, j单位，单位产品从Si到Aj地的运费为Fi, j万元，用ci, j表示单位钢管从Si地运往Aj地的最小费用，则：
cij?minFij ……………………………………………………（1）
第二步：建立从Si厂运送xi, j单位钢管到Aj点的运费的模型： 用Q表示订购的所有钢管全部运到Aj(j?1,2,?,15)点的总运费，则：
157i jQ???xj?1i?1ci j； ……………………………………………………（2）
第三步：将运到Aj处的钢管铺到相邻两段路上的运输费用
对于运到Aj的钢管，它向左运输的总量yj，它向左运输的总费用为：
yj?d?(yj?1)?d?(yj?2)?d?1?d
＝0.1?(1?2???yj)?0.05yj?yj?1?（万元）；
同理它向右运输的总费用为：d(zj?1)2zj＝0.05zj?zj?1?
用T表示当钢管从钢厂Si运到点Aj后，钢管向Aj的左右两边运输（铺设）管道的运输费用，得：
T?0.05???1?yj?yj??1?zj?zj? ……………………………………（3）
??j?115yj和zj之间存在的关系：
?7??xi j?yj?zj;(j?1,2,?,15)………………………………………………（4） ?i?1?z?y?Aj,j?1;(j?1,2,?,14)j?1?j（Aj, j?1表示Aj和Aj?1之间需要铺设的管道长度）
第四步：建立订购费用的模型
设W表示订购管道的总费用，则可建立如下模型：
715W???i?1j?1pixi, j …………………………………………………………（5）
又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂Si在指定期限内最大生产量
1515ij为si个单位，故500??xj?2?si 或?xij?0 ， 用Z表示订购和运输的总费用，由（2）、（3）、（4）、
j?2（5），本问题可建立如下的非线性规划模型：
目标函数
715minZ?W?Q?T? ?i?1?(pj?1i?cij)xij?0.05???1?yj?yj??1?zj?zj?
??j?115约束条件
?7??xi j?yj?zj;(j?1,2,?,15)?i?1??zj?yj?1?Aj,j?1;(j?1,2,?,14) …………………………………………（6） ?1515?500?xij?si或?xij?0;(i?1,2,?,7)??j?2j?2???xij?0 i?1,?,7,j?2,?,15（Aj, j?1表示Aj和Aj?1之间需要铺设的管道长度）
2、模型的求解
（1）首先求解ci j