钢管的订购和运输问题(24页).doc

《钢管的订购和运输问题(24页).doc》由会员分享，可在线阅读，更多相关《钢管的订购和运输问题(24页).doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-钢管的订购和运输问题-第 24 页一、问题重述要铺设一条输送天然气的主管道。经筛选后可以生产这种主管道钢管的钢厂有七家。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售1单位钢管价格均已给出。1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）

2、。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。1单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)3744505560（1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2） 请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管

3、道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。二、基本符号说明与基本假设2.1 基本符号说明：厂家i的实际生产量：厂家i的单位钢管销价a：单位距离公路的钢管运费，a=0.1：线段i的里程Q：单位距离铁路钢管运费：卸货节点b：最小生产量，b=500：厂家i的最大生产量：从厂家i运往卸点j的钢管量 ：从厂家i运往卸点j的最小运输费用：从卸点往左运的钢管量：从卸点往右运的钢管量：从卸点往第三方向运的钢管量：生产厂家i是否生产，N：表示该线段是否被占用，2.2 基本假设1) 假设沿管道或者原来有公路，或者建有施工公路。2)所有钢管由七个产地供应。3)钢管在运输

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

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

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

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

8、建立4.1模型准备 由于本题中所给的路线比较多，又分为三种，一种是铁路，一种是公路，还有一种是需要铺设的管道线。因此，为了方便叙述和运算，我们对问题一中每一段路进行标号，标号内容如下：1. 线段i=1,2,14:，编号； 2. 线段i=15,16,31：其他公路线段编号； 3. 线段i=32,33,54：铁路编号。同时，对问题一所给图中的每一个节点进行标号，标号如图所示： 对问题三中每一段路进行标号，标号内容如下：1. 线段i=1,2,20:，编号； 2. 线段i=15,16,29：其他公路线段编号； 3. 线段i=30,33,52：铁路编号。对问题三所给图中的每一个节点进行标号，由于问题三中

9、节点数没有改变，因此标号仍如上图所示：第一部分：问题1模型的建立4.2约束条件的确定在对钢管订购和运输问题的若干要素进行统一规定后，下面来分析题目中已知的或隐含的可能约束条件: （1）.生产厂家个数限制 题目中共有能生产钢管的厂家七家，得生产厂家个数限制： （2）. 每个厂家的生产量限制由题目可知，钢厂i如果承担制造这种钢管，至少需要生产500个单位，同时，每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售1单位钢管价格均可由题目中的表查出。因此，得到钢管生产量限制： （3）. 产销平衡限制为了节约成本，提高钢管利用率，每个厂家所生产的钢管数量应该全部用于铺设管线。因此，得到每个厂家的钢

10、管产销平衡限制： （4）.管道铺设限制对于每个卸点来说： 该点向左铺设的管道长+临近另一点向右铺设的管道长=两点间距离用表示对点j来讲，该点到下一卸点的距离，注意到问题一所给出的图中，在和两点处，无需向左运输，无需向右运输，因此对这两处做单独限制：为了保证钢管的充分利用，我们要求运到节点的钢管全部用完，则得到约束条件： （5）.非负性限制为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢管量 ，从卸点往左运的钢管量和从卸点往右运的钢管量均大于零。4.3目标函数的确定由题目可知，该问题主要目标是取得运输费用和订购费用总和最小，因此，我们决定将钢管的订购成本和运输成本作为两个目标函

11、数，对其中的运输成本根据题目要求进行进一步的细化，通过约束条件对目标函数的限制，进行求解，以期得到较为满意的结果。 （1）.钢管的订购费用函数本题中钢管的订购费用主要由各厂家钢管的销售价来决定，而厂家销售额又是取决于厂家i的实际生产量和厂家i的单位钢管运价。因此，我们得到问题一中的钢管的订购费用函数：（2） .钢管的运输费用函数 本题目中对于钢管的运输费用函数的建立有一定的难度，由于题目中要求钢管的运输不只是运到点，而是管道全线，而在选定路线时，我们并不知道每次将钢管运到管道铺设全线的哪一个地方，因此，为了模型建立的方便，我们将该函数分为两个部分：a.由钢管生产厂运到钢管铺设节点；b.由铺设节

12、点从左右两个方向向铺设线路运输。a.由钢管生产厂运到钢管铺设节点问题一中共有七个钢管生产厂家，十五个管道铺设节点，我们用N表示该线段是否被占用，用零一规划进行区分，若线段占用，则N=1，否则N=0，D表示线段里程数。由此推的：为钢管运输中的公路花费，为钢管运输中的铁路花费。对两个表达式再次进行处理，应用图论中的最短路原理，将铁路最短路矩阵和公路最短路矩阵，统一成总最小费用矩阵。我们用表示从厂家i运往卸点j的最小运输费用，用表示从厂家i运往卸点j的钢管量，将进行转化，则该部分的运输费用函数为：b.由铺设节点从左右两个方向向铺设线路运输进行完第一部运输过程后，我们将钢管运到了各个节点，下面考虑第二

13、部运输过程节点运输。对于每个卸点，我们令它可以向左右两个方向进行运输，其中，设从卸点向左调运的钢管量为,则向右调运的钢管量为，不妨先考虑向左调运的情况。考虑一个节点向左调运时的情况，可能会出现多种调运需求，如需要调运1个单位钢管，2个单位钢管，3个单位钢管.个单位钢管，由于一单位钢管等同于运距一公里，则调运总距离为1+2+3+.+=，单位距离公路运费为a，则一个节点向左调运的总运费表示为：a。再考虑向右调运的情况，与向左调运类似，从一个卸点开始向右铺设的费用同理可表示为：a。则十五个节点向左的总运费为：a向右的总运费为：a所以钢管的运输费用函数可表示为：a+a+综合以上两点，又由于我们的目的是

14、要求总费用成本最低，因此得到问题一的目标函数为：=+a+a+ 4.4 规划模型综上所述，我们得到一个非线性规划模型，如下：=+a+a+S.T第二部分：问题3模型的建立4.5约束条件的确定 问题三与问题一非常类似，其主要区别在于问题三中将线性的管道铺设线变成了树形的铺设线路，多增加了几个节点。因此，我们仿照问题一中的思路，找出问题三的约束条件。 在问题三的约束条件中，前三个条件与问题一的相同，没有改变，这里不再赘述，唯一有变化的是约束四。 管道铺设限制：对于每个卸点（除外）来说： 该点向左铺设的管道长+临近另一点向右铺设的管道长=两点间距离用表示对点j来讲，该点到下一卸点的距离，注意到问题三所给

15、出的图中，在，, 处，,无需向左运输，,无需向右运输，因此对这四处做单独限制：由图可知，在点处，只能向一个方向运输，为了提高利用率，得到以下约束：为了保证钢管的充分利用，我们要求运到节点的钢管全部用完，其中，在三点处可以向三个方向运输，则得到约束条件： （5）.非负性限制为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢管量 ，从卸点往左运的钢管量，从卸点往右运的钢管量以及向第三方向运量均大于零。4.6目标函数的确定我们将钢管的订购成本和运输成本作为两个目标函数，对其中的运输成本根据题目要求进行进一步的细化，通过约束条件对目标函数的限制，进行求解，以期得到较为满意的结果。 （1

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

17、家i运往卸点j的钢管量，则该部分的运输费用函数为：b.由铺设节点从一个或多个方向向铺设线路运输 对于某些卸点，我们令它可以向左右两个方向进行运输，其运费函数关系式与问题一相同。节点向左的总运费为：a向右的总运费为：a与问题一不同的是，问题三中某些节点可以向三个方向运，由问题一中的求单方向运费的思路可知，问题三中的这几个节点运费可以表示为a4.7规划模型从而问题三的模型为：=+a+a+ aS.T五模型的求解第一部分：问题一中模型的求解5.1 总体最小运输费用矩阵的求解 在求解模型之前，先对总体最小运输费用矩阵进行确定，把线段的选择具体到各S点到各A点的路线的选择。 1.用floyd算法分别求出铁

18、路最短路矩阵T和公路最短路矩阵R 2.用费用转化公式获得铁路最小费用矩阵T2和公路最小费用矩阵R2 3.将两者综合，取值min=T2(i,j),R2(i,j)，求得总体最小运输费用矩阵C(i,j)总体最小运输费用矩阵C(i,j)如下所示：A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1170.7160.3140.298.63820.53.121.264.29296106121.2128142S2215.7205.3190.2171.611195.58671.2114.2142146156171.2178192S3230.7220.3200.2181.6121105.

19、59686.248.2828696111.2118132S4260.7250.3235.2216.6156140.5131116.284.262516176.28397S5255.7245.3225.2206.6146130.5121111.279.257335171.27387S6265.7255.3235.2216.6156140.5131121.284.262514526.21128S7275.7265.3245.2226.6166150.5141131.299.276665638.22625.2 模型求解 从上表可看出，从各S点到各A点共有7*15=105条路线，从中选择路线组合形成最

20、优方案，用lingo求解得最优方案。问题一的模型求解结果： 综上所述，问题一的钢管订购及运输的最优方案为：总费用=1278632万元每家厂家的生产量：S1S2S3S4S5S6S7800.0000 800.0000 1000.000 0 1297.428 1273.572 0从每个厂家到每个卸点运送的钢铁管数量：Y( 1, 4) 150.7632 Y( 1, 5) 183.7368 Y( 1, 6) 200 Y( 1, 7) 265.5 Y( 2, 2) 179 Y( 2, 3) 107.0599 Y( 2, 4) 0 Y( 2, 5) 213.9401 Y( 2, 8) 300 Y( 3, 3

21、) 79.00735 Y( 3, 4) 157.0827 Y( 3, 5) 99.90992 Y( 3, 9) 664 Y( 5, 3) 321.9327 Y( 5, 4) 160.154 Y( 5, 5) 117.9132Y( 5, 10) 282.4275Y( 5, 11) 415Y( 6, 10) 68.57246Y( 6, 12) 86Y( 6, 13) 333Y( 6, 14) 621Y( 6, 15) 165第二部分：问题二的求解由问题分析知，问题二是对问题一的模型进行灵敏度分析，因此，在解决问题二时，我们对每个厂家的单位钢管销售价和钢管总产量上限分别进行调整，对比数据，然后判断影

22、响的大小。5.3 单位钢管销售价变化的影响p增加p初值总费用总费用增长s1s2s3s4s5s6s7p1-20%128.0 1253032-2.00%800800100001298.7891272.2110-10%144.0 1265832-1.00%800800100001298.2041272.79605%168.0 12850320.50%800800100001297.0251273.975010%176.0 12914321.00%800800100001296.5161274.484020%192.0 13042322.00%800800100001294.9561276.0440p

23、2-20%124.0 1253832-1.94%800800100001298.1731272.8270-10%139.5 1266232-0.97%800800100001297.921273.0805%162.8 12848720.49%800800100001294.9751276.025010%170.5 12910320.97%800800100001291.7741279.226020%186.0 13034321.94%800800100001297.4651273.5350p3-20%124.0 1247632-2.42%800800100001295.4911275.5090

24、-10%139.5 1263132-1.21%800800100001297.4071273.59305%162.8 12864320.61%800800100001292.7321278.268010%170.5 12941321.21%800800100001287.1541283.846020%186.0 13074362.25%800800507.10401592.6471471.2490p4-20%128.0 1255861-1.78%80080010001482010890-10%144.0 1275883-0.21%8008001000871500120005%168.0 127

25、86320.00%800800100001299.8641271.136010%176.0 12786320.00%800800100001295.0381275.962020%192.0 12786320.00%800800100001305.6141265.3860p5-20%124.0 1231067-3.72%800800599.687701952.31210190-10%139.5 1256718-1.71%800800100001474.51096.505%162.8 12851180.51%800800100005712000010%170.5 12895150.85%80080

26、0100005712000020%186.0 12918291.03%8008001000571020000p6-20%120.0 1220664-4.53%8008001000057120000-10%135.0 1250664-2.19%80080010000571200005%157.5 12875280.70%800800100001403.51167.5010%165.0 12960201.36%8008001000014721099020%180.0 13119432.61%80080010000154710240p7-20%128.0 12786320.00%8008001000

27、01297.4281273.5720-10%144.0 12786320.00%800800100001297.4281273.57205%168.0 12786330.00%800800100001297.4281273.572010%176.0 12786330.00%800800100001297.4281273.572020%192.0 12786340.00%800800100001297.4281273.5720由上表可知，无论各个厂家的单位钢管销售价如何变化，在85%情况下订购方案不包含厂家s4，100%不包含厂家s7；同时，当厂家s5和厂家s6的单位钢管销售价发生变化时，对方案

28、中总运费的影响最大，厂家s1，s2，s3发生变化时，对总运费的影响较小。上图显示的是各个厂家的单位钢管销售价变化所造成的总费用的变化。其中，横轴为各个钢厂单位钢管销售价变化百分比，纵轴为总费用的变化百分比。纵轴变化百分比等于零，说明钢厂单位钢管销售价变化对总费用无影响，曲线越接近总费用变化百分比=0这条直线，说明钢厂单位钢管销售价变化对总费用影响越小，反之越大。观察图中曲线与该直线的的关系，p7与直线重合，p4在剩余曲线中最接近;p5,p6离直线最远，由此也可得到同样的结论。5.4钢厂钢管总产量上限变化的影响s增加s值总费用总费用增长S1S2S3S4S5S6S7s110%8801270392-

29、0.64%880800100001156.2571334.743020%9601262152-1.29%960800100001149.7591261.2410s210%8801275832-0.22%800880100001223.4411267.559020%9601273032-0.44%800960100001100.4991310.5010s310%11001276132-0.20%800800110001206.7031264.297020%12001273632-0.39%800800120001059.891311.110s410%220012786320.00%8008001

30、00001357.5231213.477020%240012786320.00%800800100001357.5271213.4730s510%220012786320.00%800800100001248.5011322.499020%240012786320.00%800800100001216.7891354.2110s610%220012786320.00%800800100001305.5671265.433020%240012786320.00%800800100001237.3851333.6150s710%330012786320.00%800800100001357.523

31、1213.477020%360012786320.00%800800100001357.5231213.4770由上表可知，厂家s4，s5，s6，s7的钢管总产量上限变化对总费用没有影响。厂家s1的钢管总产量上限变化对总费用影响最大，s2，s3的变化对总费用有一定影响。第三部分：问题三中模型的求解5.5 总体最小运输费用矩阵的求解 在求解模型之前，先对总体最小运输费用矩阵进行确定，把线段的选择具体到各S点到各A点的路线的选择。 1.用floyd算法分别求出铁路最短路矩阵T和公路最短路矩阵R 2.用费用转化公式获得铁路最小费用矩阵T2和公路最小费用矩阵R23.将两者综合，取值min=T2(i,j

32、),R2(i,j)，求得总体最小运输费用矩阵C(i,j)总体最小运输费用矩阵C(i,j)如下所示：A1A2A3A4A5A6A7A8A9A10S1170.7160.3140.298.63820.53.121.264.292S2215.7205.3190.2171.611195.58671.2114.2142S3230.7220.3200.2181.6121105.59686.248.282S4260.7250.3235.2216.6156140.5131116.284.262S5255.7245.3225.2206.6146130.5121111.279.257S6260.7250.3235.2

33、216.6156140.5128.1116.284.261S7275.7265.3245.2226.6166150.5141131.299.276A11A12A13A14A15A16A17A18A19A20A21S196106121.21281426095100105115125S2146156171.2178192110145150155165175S38696111.211813244859095105115S4516176.28397805055607080S5335171.27387753245506575S6473716.2112880463336100S7645638.226295

34、63505532265.6 模型求解 从上表可看出，从各S点到各A点共有7*21=147条路线，从中选择路线组合形成最优方案，用lingo求解得最优方案。问题三的模型求解结果： 综上所述，问题一的钢管订购及运输的最优方案为：总费用=1403233万元。每家厂家的生产量：S1S2S3S4S5S6S7800.0000 800.0000 1000.000 01303.000 2000.000 0从每个厂家到每个卸点运送的钢铁管数量： Y( 1, 4) 1.341489 Y( 1, 5) 333.1585 Y( 1, 6) 200 Y( 1, 7) 265.5 Y( 2, 2) 179 Y( 2, 3

35、) 51.0179 Y( 2, 4) 53.03363 Y( 2, 5) 216.9485 Y( 2, 8) 300 Y( 3, 4) 228.607 Y( 3, 5) 65.39302 Y( 3, 9) 664.5 Y( 3, 16) 41.5 Y( 5, 3) 456.9821 Y( 5, 4) 185.0179 Y( 5, 10) 126 Y( 5, 11) 380 Y( 5, 17) 155 Y( 6, 10) 225 Y( 6, 12) 111 Y( 6, 13) 393 Y( 6, 14) 571 Y( 6, 15) 165 Y( 6, 18) 80 Y( 6, 19) 95 Y(

36、 6, 20) 260 Y( 6, 21) 100六.模型评价与推广此模型是针对钢管订购运输问题的处理方案,其中主要方面在于运输路径的选择，模型中将路径的选择分成两大部分处理，先将货物运到节点，再从节点向全线运输。同时，在解决第一个问题时，把铁路和公路分开计算，最后进行统一，简化了运算。但模型也存在一些不足之处，在对铁路运费矩阵和公路运费矩阵进行统一时，取的还是相对近似值。另外，由于我们在建立约束条件时要求从节点向其他方向运输时，相邻两节点运量加和恰好等于两点间线路距离，因此忽略了跨节点运输的情况，而这里面可能出现较之更优的方案。在解决本题时，我们主要采用的是通过点来表示线路的，同时应用图论中

37、的floyd算法解决最短路径问题。在生活中，求最短路径的问题常常会碰到，我们可以对模型稍加修改，使之符合问题的条件，进而进行求解。七 .参考文献1 曾建军，matlab语言与数学建模，安徽大学出版社，2005年。2 姜启源，数学模型（第三版），高等教育出版社，2003年8月。3 肖华勇，实用数学建模与软件应用，西北工业大学大学出版社，2008年11月。4 牛映武，运筹学（第二版），西安交通大学出版社，2006年5月。5 王海英，图论算法及其MATLAB实现，北京航空航天大学出版社，2010年2月。附录:问题一程序：Matlab程序%求问题一最小费用矩阵clear;clc;n=39; %总共39

38、个点%S1,S2,.,S3分别标号为1,2,.,7%中间站分别标号为8,9,.,24%A1,A2,.,A15标号为25,26,.,39%输入铁路路程矩阵A=zeros(n,n);for i=1:n for j=1:n if i=j A(i,j)=0; else A(i,j)=inf; end endend A(8,10)=450;A(9,10)=80;A(10,11)=1150;A(11,16)=1100;A(12,13)=306;A(13,14)=195;A(1,14)=20;A(1,16)=202;A(2,16)=1200;A(16,17)=720;A(3,17)=690;A(17,18)

39、=520;A(18,19)=170;A(4,19)=690;A(19,20)=160;A(5,15)=462;A(15,19)=88;A(20,21)=70;A(20,22)=320;A(22,23)=160;A(6,23)=70;A(23,24)=290;A(7,24)=30;for j=1:n for i=1:j-1 A(j,i)=A(i,j); endend %求铁路最短路T=A;m=1;while mT(i,m)+T(m,j) T(i,j)=T(i,m)+T(m,j); end end end m=m+1;end%求铁路费用矩阵T2=zeros(n,n);for i=1:n for j=1:n if T