管道运输问题论文

1、摘要：本文采用二次规划算法来解决。首先将各钢厂到铺设节点的单位最小运费转化为求最短路的方法，将铁路的 运输费用、钢厂的运价与公路的运费等价转换，即将公路铁路合并成一张网，再利 用求最短路的方法求出我们需要的单位最小运费。对于问题中钢厂产量的约束条 件，采用0-1规划模型解决。第二步求得沿着铺设管道从节点到各施工地单位的最小运费，将待铺设管道 按单位长度分解成n个需求点，直线图考虑左右两个方向的运输，通过构建一个等 差数列得到标函数。笫三问树状图仅需考虑沿各个方向的运输。该运输模型的方 法，避免了问题一和三的差别。最后建立一个二次规划的算法模型，利用ling。软 件进行编程求得最优解。根据上述建

2、模思想，我们求得最优解为127. 84亿元。第二问即为灵敏度分 析，我们得出钢厂钢管的销价的变化对购运讣划和总费用影响最大，S钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字 结果。问题三：第4、7两家钢厂补生产，1、2、3、6四家工厂饱和生产，余下的 由5供应，最优值约为140. 66亿元。最后对模型进行了综合评价，并提出了改进方 向。关键词：二次规划、0-1规划、ling。、最短路、目标函数一、问题的重述要铺设一条 的输送天然气的主管道，如图一所示（见下页）。经筛选后可以生产这种主管道钢管 的钢厂有S凤,s=O图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道

3、（假设沿管道或 者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁 的阿拉伯数字表示里程（单位km） o为方便IT, 1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产300个单位。钢丿S.在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为A万元，如下表：11234567Si80080010002000200020003000A1601551551601551501601单位钢管的铁路运价如下表:里程（km）W300301350351400101430451500运价（万元）2023262932里程（km）501600601700

4、7018008019009011000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里01万元（不足整公里部分按整公里计钢管可山铁路、公路运往铺设地点（不只是运到点（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大, 并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给岀一种解决办法，并对图二按（1）的要

5、求给岀 模型和结果。二、问题的分析本题要铺设一条 A A15 的天然气管道，使得总费用最小。可以这样考虑问题：先把钢厂生产的钢管运到各个站点A J（j丰1）再往两边运送，再计算出总的费用使之最小。第一步：求出各钢厂到各铺设结点的单位最小运费;这部分包括铁路运费和公路运费，但山于铁路、公路运费的不同还有钢管出 厂销价的差别，通过合理的方式可将铁路运费转换成公路运费，再利用求最短路的 方法求出我们需要的单位最小运费。笫二步：沿着铺设管道从各结点到各施工地的单位最小运费。如果这两个运费都能算出，我们就可以将待铺设的主管道全线按照1公里作为一个单位分割成5171个点（对于问题三，可以将树形 图分割成5

6、903个点）。这样问题就变成了一个理想的运输问题，考虑个站点向左 向右两个方向的运输，建立等差数列，即可求出最优解。第三问变为树形图，因此，有些枢纽站点的度不再是1或2,于是将运送到 枢纽站点的钢管总量不能总简单的分为左右两部分，而是应该考虑从它各个方向的 运送量。三、模型的假设1. 钢管运输过程中若用火车则直接把钢管运到公路与铁路交接处，即下了火 车不上火车；2. 假设运输单位可提供足够的火车与汽车；3. 费用计算时按钢管数量算，不考虑其他计费方法及因素。4. 运费中不足整公里部分按整公里计。5. 假设向每个钢管厂都订购钢管。6. 设lkm主管道钢管为1单位钢管。7. 路中铺设的钢管只允许山

7、其相邻站点提供。8. 不汁各个环节中的装卸费用四、符号的说明第i家钢厂的最大供应量/j管道节点A钢管出厂销价1单位钢管为A万元勺第i家钢厂到铺设节点j的订购和运输费用X罗从钢厂i到j的运钢量y从节点j向左铺设的钢管量从节点j向右铺设的钢管量题图一公路网上两点间的单位钢管最少运输费用;D2磺题图二公路网上两点间的单位钢管最少运输费用;五、模型的建立5. 1题一分析求解：由于由任一钢厂发出的钢管不经过中任何一个是无法到达管线上的，因此我们可以依据这点将整个问题一分为二：前 一阶段是钢管由厂Sj运到去，后一阶段是到达的钢管再由公路送到管线上x点去。5. 1. 1第一阶段：总共有7个厂，15个节点，运

8、到4最小费用路必经过,可不考虑：7 157 15/=! J-2f=l J2第二阶段：管道上左右每公里的运费是一个首项0.1,公差0.1的一个等差级数，乂因 为题目明确要求公路运费为0.1万元/km,且足整数按整数公里计算，所以（少伉）山+ 1 右+匕）匕+ 1）*0.05 才是精确的计费运算公式。此时，厲表示不超过 的最大数，（）表示 的小数部分。关于节点j求和从2开始，因为节点4,钢管到达他后无需向其他点运送了。这样向A输送的钢管可以向左铺ykm,向右铺zkm。此外由A向A铺的部分与A向A的部分应覆盖线段AA,故z+y且有y这里应当注意的是若A|4?-力】|忆5 =0A中右段钢管全经过&qu

9、ot;j+2 而来，则上式就不成立了，但如果发生这种情况，去掉Aj +节点即可。本问题中由管线外到达A点要经过600km的路程，耗资60万元/km,因此由 到心Z中的点的最小费用路经过4，故A节点可以去掉。山物理意义y>0总之，该模型为：min（工£无 p +工工勺 ） +（丹+ （刀）（刀卜1+同+ （z/店小】） 0.05 i=l/«=! /a2冋S. t£x(,e0<j500,.y/p=l,2,.,7工旳= Fj + Zj,/ = 2,3,.,15 /=!氐-4 J"，15=|5-4|y2|& -4|占5 = oy>0&g

10、t; j=2, 3, 515；x>0J = l.,7> =2,3,5,.,! 5对最小运费的求解，我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点9的最短路线的长度,用mat lab求得对应的铁路单位运费q;同理用Floyd算法求出公路网上的任意两点的最短公路路线的长度厶k,结果乘以0.1得到公路运费Oc-j. =min(Df/+Z)l#),j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运 输费用。约束条件：产量约束：Je0u500,4/ = U.,7铺设约束条件:工勺=兀+引,丿=2,.,15; /=!52题三分析求解:如铺设的管道是一个树形图，

11、铁路、公路和管道构成网络对于题图二，我们 可以延用问题一里面的思想，在题图一的基础上多儿条铺设路段，9, 11, 17节点 的铺设方向变为X, Y, Z三个方向，其他不变。第一阶段:总费用为:7 217 21戶2/=1 J=2”4笫二阶段：山于树形图的出现，则某些管道处会出现多支路。则模型一中模型的Zj不再适用，此时可考虑多增加支路变量 X,并增加约束，在LI标函数中增加相应的铺设费。min旷=£ 七严.述伽+（儿）贱抑+引+（引）血打曲*（x/）llb/*lj）e005Z /-2Z /-IzQ-9JIJ7）s. t.£xveokj500,p=l,2,.,77ZX=X+Zj

12、J=：2,3,5z=i八2,15Z3+J5=|5-A|14? -Ml，% =o>0,j=2, 3, 515；六、模型的求解1 出厂销价、铁路运费向公路运费的转换:1. 1运输费用等价转换原则：按单位运费相等原则将任意两点的最短铁路线转化为公路线。对于铁路线上的任意两点,用Floyd算法找出两点间最短铁路路线的长度厶j,查铁路运价表求得厶j对应的铁路单位运费/：.:乂设与该段铁路等费用的公路长度为，则：fa由此，我们就在匕和巧之间用一条等价的公路线代替间的最短铁路线。如果vv.之间原来就有公路，就选择新旧公路中简短的一条。这样我们就把铁路运输网络转 换成了公路运输网络。1. 2销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为单位运价。对于钢丿 的销售单价P：,我们可以虚设一条公路线，连接钢厂 及另一虚设钢厂'的销售价为0.2特殊约束条件的处理：山于约束条件15以J-2"02500, Sa,i二1,7的存在，因此模型的求解不能简单地调用线性规划或者二次规划的 软件。引进0-1变量f _钢厂Z生产Ji (0,钢厂i不生产于是约束条件转换为：500/=,7.七、模型的评价与改进