钢管的订购和运输问题.docx

1、钢管的订购和运输问题钢管的订购和运输问题长安大学杨剑浩陈晓渭程牧刚本文针对钢管订购和运输的一般特点和要求， 建立了两个遵循题目要求的非线性规划模型。在给定钢管需求量，运输方式及价格，厂家生产量上下线，运输 路线图等条件下，非线性规划模型和图论的最短路算法， 从而得到线最优的钢管 订购运输方案，是成本达到最小。对于问题一，我们选取了钢管订购和运输的总费用最小作为模型的目标函 数，用floyd算法分别求出铁路最短路矩阵和公路最短路矩阵， 利用费用转化公式，得到两个矩阵的最小费用，将两者综合求得总体最小运输费用矩阵 C(i,j)。然后用lingo求解得到最优的钢管订购运输方案。对于问题二，我们根据要

2、求改变钢厂钢管的销价和钢厂钢管的产量上限， 然后用lingo求解，观察得到的图表，对改变以上两个条件后总运费及方案受到的 影响进行分析。考虑到问题三与问题一很相似，不同之处在于问题三中的钢管铺设路线变成 了树形，因此我们仍然采用问题一的建模思路， 对于特殊之处进行修改。采用图论中的floyd算法，求得总体最小运输费用矩阵 C(i,j)。然后用lingo求解得 到最优的钢管订购运输方案。对问题一模型的求解得到最优钢管订购运输方案为：总费用=1278632万元每家厂家的生产量:S1S2S3S4S5S6S7800.0000800.00001000.00001297.4281273.5720对问题二求

3、解得：厂家s5和厂家s6的单位钢管销售价发生变化时，对方案中总运费的影响最大。厂家si的钢管总产量上限变化对总费用影响最大。对问题三的模型求解得到最优钢管订购运输方案为:总费用=1403233万元。每家厂家的生产量:S1S2S3S4S5S6S7800.0000800.00001000.00001303.0002000.0000关键词：floyd算法非线性规划模型总体最小运输费用矩阵一、问题重述要铺设一条输送天然气的主管道。经筛选后可以生产这种主管道钢管的钢厂 有七家。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道 （假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁

4、路、公 路和管道旁的阿拉伯数字表示里程（单位km）。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢 管，至少需要生产500个单位。每个钢厂在指定期限内能生产该钢管的最大数量 和钢管出厂销售1单位钢管价格均已给出。1000k m以上每增加1至100km运价 增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整 公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。1单位钢管的铁路运价如下表:里程（km） 300301350351400401450451500运价（万元）2023262932里程（km）50160060170070180

5、08019009011000运价（万元）3744505560（1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费 用）。（2） 请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费 用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（ 1）的要求给出模型和结果。2.1基本符号说明、基本符号说明与基本假设S，线段未占用 N:表示该线段是否被占用，N = *1线段已占用 L.）2.2基本假设1） 假设沿管

6、道或者原来有公路，或者建有施工公路。2） 所有钢管由七个产地供应。3） 钢管在运输过程中不考虑途中运输磨损，即运输的钢管都可用4） 运输过程中不考虑铁路，公路转换时的搬运费用。5） 题目所给数据可靠性高。三、问题分析和基本思路3.1问题分析和建模思路该问题是一个比较明显的优化问题， 其中主要包含两部分的优化选择：一个 是运输路线的选择，另一个是产销地的选择。其中运输路线的选择是本题的关键， 不妨将本题看作是一个运费最少的路线选择问题。 由于运输问题中需要考虑单位 运价，运输量，运输距离，运输方式等一些因素的影响，而其中运价已经在题目 中间接地给出，运价和选择的运输方式以及运输距离，运输量有关。

7、因此，我们 需要考虑解决的因素就变为三个： 运输方式，运输距离和运输量。因而在建立模 型时没有必要考虑所有因素，只需抓住这三个关键因素，进行合理的假设和建模。建立模型对钢管的运输和订购问题进行定量安排，就是从当前实际的钢管产 量和铺设情况出发，选择恰当的订购运输方案，提出合理的订购运输要求和假定， 应用科学的方法，预测出该方案需要花费的总资金， 使总资金尽量达到最小，降 低钢管铺设的成本。（一） 问题1的分析问题一属于运输类求最短路的问题，题目中给出了七个钢管生产厂，十五 个钢管铺设节点以及五十四条可直接连通路线。 我们希望找到一种方案，使从七 个钢管厂中的某几个进行钢管生产， 然后从该厂开始

8、运输，选取运输路线和十五 个节点中的一部分，使在满足题目铺设要求的前提下，取得最小的运输购买费用。 由于题目中说明：钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道 全线）。因此，当钢管运输到节点后，仍然需要考虑节点到全线的运输方法，我 们采用从节点向两个方向运输的方式。在两次路线选择中分别取最小费用路线， 然后将两者结合起来，求的最终路线和订购方案。因此，我们建立零一规划模型， 对问题进行求解。（二） 问题2的分析问题二是讨论钢厂钢管的销价的变化和钢厂钢管的产量的上限的变化对购 运计划和总费用的影响，同时判别哪家钢厂在这两方面发生的变化对购运计划和 总费用的影响最大，其实际上是对问题一

9、中的模型进行灵敏度分析， 使得钢管销 售价和钢管生产上限在发生变化时，能够利用原有模型进行判断，是否需要对购 运计划进行修改，以满足新情况下的最优。由此，我们通过对厂家i的单位钢管 销价和厂家i的最大生产量的数值调整，利用lingo功能求的不同情况下的运输 方案，对各方案结果进行比照，得出结论。（三） 问题3的分析问题三是对问题一的扩展，将线性管道铺设改为树形管道铺设图。我们仍 然采取问题一的建立模型的思路， 对其中第一部分：由生产厂家运往铺设节点的 线路选择模型保留，对第二部分：由节点向铺设全程运输模型进行改变， 将从节 点向两边运输改为在某些节点处向三个方向运输， 以满足问题三的要求。仍然

10、建立零一规划模型，对问题求解。同时，对问题三进行钢厂钢管的销价的变化和钢 厂钢管的产量的上限的变化对购运计划和总费用的影响的灵敏度分析。4.模型的建立4.1模型准备由于本题中所给的路线比较多，又分为三种，一种是铁路，一种是公路，还 有一种是需要铺设的管道线。因此，为了方便叙述和运算，我们对问题一中每 段路进行标号，标号内容如下：1. 线段 i=1,2,14：AA2，A2A3，A14A15 编号；2.线段i=15,16,31：其他公路线段编号；3.线段i=32,33,54:铁路编号。4.同时，对问题一所给图中的每一个节点进行标号，标号如图所示：25对问题三中每一段路进行标号，标号内容如下：1.线

11、段 i=1,2, ,20： Ai A2， A2A3， ， A20 A21 编号;2.线段i=15,16,29：其他公路线段编号；3.线段i=30,33,52：铁路编号。对问题三所给图中的每一个节点进行标号，由于问题三中节点数没有改变, 因此标号仍如上图所示：第一部分：问题1模型的建立4.2约束条件的确定在对钢管订购和运输问题的若干要素进行统一规定后， 下面来分析题目中已知的或隐含的可能约束条件：（1） .生产厂家个数限制题目中共有能生产钢管的厂家七家，得生产厂家个数限制：7 mi 一 7i 4（2） .每个厂家的生产量限制由题目可知，钢厂i如果承担制造这种钢管，至少需要生产500个单位，同 时

12、，每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售 1单位钢管 价格均可由题目中的表查出。因此，得到钢管生产量限制：bmij 二 Xj 二 smj（3）.产销平衡限制为了节约成本，提高钢管利用率，每个厂家所生产的钢管数量应该全部用于 铺设管线。因此，得到每个厂家的钢管产销平衡限制：15 Yj风（4）.管道铺设限制 对于每个卸点来说：该点向左铺设的管道长j 二+临近另一点向右铺设的管道长=两点间距离 用dj表示对点j来讲，该点到下一卸点的距离，注意到问题一所给出的图中，在 A和Al5两点处，A无需向左运输，Al5无需 向右运输，因此对这两处做单独限制：=0，h =0为了保证钢管的充分利用

13、，我们要求运到节点 a的钢管全部用完，贝U得到约束条件:7Y=w- t-J ij vvj Lji A（5）.非负性限制为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢 管量，从卸点Aj往左运的钢管量和从卸点 A往右运的钢管量均大于零。Yj -，Wj-，tj-4.3目标函数的确定由题目可知，该问题主要目标是取得运输费用和订购费用总和最小，因此， 我们决定将钢管的订购成本和运输成本作为两个目标函数， 对其中的运输成本根据题目要求进行进一步的细化，通过约束条件对目标函数的限制， 进行求解，以 期得到较为满意的结果。（1）.钢管的订购费用函数本题中钢管的订购费用主要由各厂家钢管的销售

14、价来决定，而厂家销售额又 是取决于厂家i的实际生产量和厂家i的单位钢管运价。因此，我们得到问题一 中的钢管的订购费用函数：7Xi Pii -1（2）.钢管的运输费用函数本题目中对于钢管的运输费用函数的建立有一定的难度，由于题目中要求 钢管的运输不只是运到点，而是管道全线，而在选定路线时，我们并不知道每次 将钢管运到管道铺设全线的哪一个地方， 因此，为了模型建立的方便，我们将该函数分为两个部分：a.由钢管生产厂运到钢管铺设节点；b.由铺设节点从左右两 个方向向铺设线路运输。a.由钢管生产厂运到钢管铺设节点问题一中共有七个钢管生产厂家，十五个管道铺设节点，我们用 N表示该线段是否被占用，用零一规划

15、进行区分，N =丿，若线段占用，贝U N=1,否则N=0,31 54D表示线段里程数。由此推的：a，DiN为钢管运输中的公路花费，Qi DiNi为i =15 32钢管运输中的铁路花费。对两个表达式再次进行处理，应用图论中的最短路原理， 将铁路最短路矩阵和公路最短路矩阵，统一成总最小费用矩阵。我们用 Cij表示从厂家i运往卸点j的最小运输费用，用Yij表示从厂家i运往卸点j的钢管量，31 54将a7 DiNi DiNi进行转化，则该部分的运输费用函数为：i 5 i =327 15、CjYij j b.由铺设节点从左右两个方向向铺设线路运输进行完第一部运输过程后，我们将钢管运到了各个节点，下面考虑

16、第二部运 输过程 节点运输。对于每个卸点，我们令它可以向左右两个方向进行运输， 其中，设从卸点Aj向左调运的钢管量为tj ,则向右调运的钢管量为 Wj，不妨先考虑向左调运的情 况。考虑一个节点向左调运时的情况，可能会出现多种调运需求，如需要调运 1个单位钢管，2个单位钢管，3个单位钢管. tj个单位钢管，由于一单位钢管t (t +1)等同于运距一公里，则调运总距离为1+2+3+.+ tj =- ，单位距离公路运一 一 t (t +1) 一费为a，则一个节点向左调运的总运费表示为：a-!1 。再考虑向右调运的情况，与向左调运类似，从一个卸点 Aj开始向右铺设的费用同理可表示为:aWj(Wj 1)

17、。则十五个节点向左的总运费为：j m 2向右的总运费为:a J Wj Wj 1所以钢管的运输费用函数可表示为:综合以上两点，又由于我们的目的是要求总费用成本最低， 因此得到问题一的目 标函数为：i j =1 j 珀 i W jW4.4规划模型综上所述，我们得到一个非线性规划模型，如下:乞mi兰7i 4bmiXismi15无Y j；j4Wj 5 = dj7S.T为 Yj 二Wj +tji AW15 = 0,右=0mi =r1Yij “Wj tj =第二部分：问题3模型的建立4.5约束条件的确定问题三与问题一非常类似，其主要区别在于问题三中将线性的管道铺设线变 成了树形的铺设线路，多增加了几个节点

18、。因此，我们仿照问题一中的思路，找 出问题三的约束条件。在问题三的约束条件中，前三个条件与问题一的相同，没有改变，这里不再 赘述，唯一有变化的是约束四。管道铺设限制：对于每个卸点（a9，a11，a17除外）来说：该点向左铺设的管道长+临近另一点向右铺设的管道长 二两点间距离用dj表示对点j来讲，该点到下一卸点的距离，Wj tj 厂 dj注意到问题三所给出的图中，在 a， a， a21, A18处，A, A18无需向左运输，a15, a21无需向右运输，因此对这四处做单独限制：W15=，t0，t18=0， W21 = 0由图可知，在点a16,A18, A21处，只能向一个方向运输，为了提高利用率

19、，得到 以下约束：W20 t21 = 100，W16 二 0为了保证钢管的充分利用，我们要求运到节点 a的钢管全部用完，其中，在a9, a11，a17三点处可以向三个方向运输，则得到约束条件:（5）.非负性限制为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢 管量，从卸点Aj往左运的钢管量，从卸点Aj往右运的钢管量以及向第三方向 运量均大于零。Yij-0，Wj-0， tj-0，|m-4.6目标函数的确定我们将钢管的订购成本和运输成本作为两个目标函数， 对其中的运输成本根 据题目要求进行进一步的细化，通过约束条件对目标函数的限制， 进行求解，以 期得到较为满意的结果。（1）.钢

20、管的订购费用函数本题中钢管的订购费用主要由各厂家钢管的销售价来决定，而厂家销售额又 是取决于厂家i的实际生产量和厂家i的单位钢管运价。因此，我们得到问题一 中的钢管的订购费用函数：7打 Xi Pi（3）.钢管的运输费用函数本题目中对于钢管的运输费用函数的建立有一定的难度，由于题目中要求 钢管的运输不只是运到点，而是管道全线，而在选定路线时，我们并不知道每次 将钢管运到管道铺设全线的哪一个地方， 因此，为了模型建立的方便，我们将该函数分为两个部分：a.由钢管生产厂运到钢管铺设节点；b.由铺设节点从一个或 多个方向向铺设线路运输。a.由钢管生产厂运到钢管铺设节点我们用Cij表示从厂家i运往卸点j的

21、最小运输费用，用Yij表示从厂家i运 往卸点j的钢管量，则该部分的运输费用函数为：7 21 CijYijb.由铺设节点从一个或多个方向向铺设线路运输对于某些卸点，我们令它可以向左右两个方向进行运输， 其运费函数关 系式与问题一相同。节点向左的总运费为：向右的总运费为:Wj Wj 1avj a 2与问题一不同的是，问题三中某些节点可以向三个方向运， 由问题一中的求单方向运费的思路可知，问题三中的这几个节点运费可以表示为a J9（l+lii（li）li7（li1）| 2 2 24.7规划模型从而问题三的模型为：Wj Wj 1 +27 21 21 t t 1 21min CjYj +* 翠 +i生j

22、吕 j总 2 j吕a l 9 l 9 1 . I 11 I 11 1 . I 17 I 17 12227为mi兰7i壬bmi - X s mi21三 Yi = Xij壬7送 Yij =Wj +tj +|m，|m = (jH1,17)i =1S.TWj +td j| 9 +ti6 =42，ti7 +wi8 =13，Wi7 +ti9 = 19|i1 +|i7 OWw +|2 =26，W2+t21 0Wi6 二 ，Wi5 =，W21 =，ti =，ti8 = mi =r15.模型的求解第一部分：问题一中模型的求解5.1总体最小运输费用矩阵的求解在求解模型之前，先对总体最小运输费用矩阵进行确定， 把线

23、段的选择具体到各S点到各A点的路线的选择。1.用floyd算法分别求出铁路最短路矩阵 T和公路最短路矩阵R2.用费用转化公式获得铁路最小费用矩阵 T2和公路最小费用矩阵R23.将两者综合，取值min=T2(i,j),R2(i,j) ，求得总体最小运输费用矩阵C(i,j)总体最小运输费用矩阵C(i,j)如下所示：A1A2A3A4A5A6A7A8A9A10A11A12A13A14A1517016014098.20.21.64.121.S1.7.3.263853.12292961062128142215r 205I19017195.71.114171.S2.7.3.2.61115862.214214

24、615621781922302202001811211059686.48.828696111.118132S3.7.3.2.6.522226025023521615614013111684.62516176.28397S4.7.3.2.6.5.2225524522520614613012111179.57335171.27387S5.7.3).2.6.5.2226525523521615614013112184.62514526.21128S6.7.3.2.6.5.2227526524522616615014113199.76665638.2262S7.7.3.2.6.5.225.2模型求解从

25、上表可看出，从各S点到各A点共有7*15=105条路线，从中选择路线组 合形成最优方案，用lingo求解得最优方案。问题一的模型求解结果：综上所述，问题一的钢管订购及运输的最优方案为：总费用 =1278632万元 每家厂家的生产量：S1S2S3S4S5S6S7800.0000800.00001000.00001297.4281273.5720从每个厂家到每个卸点运送的钢铁管数量:丫（ 1,150.7183.7107.0丫（ 1,丫（ 1,200 丫( 1,265.5 丫( 2,179 丫( 2,4)6323685995)6)7)2)3)213.979.00157.099.90丫( 2,0 丫(

26、 2,丫( 2,300 丫( 3,丫（ 3,丫（ 3,4017358279924)5)8)3)4)5)321.9160.1117.9 丫( 5,282.4 丫( 5,丫( 3,664 丫( 5,丫（ 5,丫（ 5,41532754132 10)275 11)9)3)4)5)丫( 6,68.57 丫( 6,” 丫( 6,丫（ 6,“ 丫( 6,8633362116510)246 12)13)14)15)第二部分：问题二的求解由问题分析知，问题二是对问题一的模型进行灵敏度分析， 因此，在解决问 题二时，我们对每个厂家的单位钢管销售价和钢管总产量上限分别进行调整， 对 比数据，然后判断影响的大小。5.3单位钢管销售价变化的影响p增加p初值总费 用总费用增 长s1s2s3s4s5s6s7128.1253080801298.71272.2-20%-2.00%100000032008911144.126588080P 1298.21272.7-10%-1.00%100000032000496p168.1285080801297.01273.95%0.50%1000001032002575176.1291480801296.51274.410%1.00%100000032001684192.130428080p 1294.91276.020%2.00%10000