数学建模培训讲稿----线性规化-2000B题.doc
36页
四.钢管订购和运输（2000年网易杯全国大学生数学建模竞赛B题） 要铺设一条入的输送天然气的主管道，如图所示经筛选后可 以生产这种主管道钢管的钢厂有S|,S2，・・・S7图中粗线表示铁路，单细线表示公路， 双线表示要铺设的管道（假设沿管道或者原有公路，或者建有施工公路），圆圈（点） 表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）为方便计，lkm主管道钢管称为1单位钢管一个钢厂如果承担制造这种钢管，至少需要生产500个单位钢厂S,在指定期限钢管可由铁路、公路运往•Ai5,而是管道全线）I1234567©80080010002000200020003000Pi160155155160155150160内能生产该钢管的最大数量为匚个单位，钢管出厂销价1单位钢管为出万元，如下表:一单位钢管的铁路运价如下表:里程（km）W300301〜350351〜400401〜450451〜500运价（万元）2023262932里程（km）501〜600601〜700701〜800801〜900901〜1000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0 • 1万元（不足整公里部分按整公里计算）1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）2） 请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大, 并给出相应的数字结果C（3）如果要铺设的管道并是一条线，而是一个树形图，铁路、公路和管道构成网 络，请就这种更一般的情况给出一种解决办法，并对图二按（1）的要求给出 模型和结果.模型一1・分析：（1）制定订购和运输计划，意思是指在钢厂S. （1=1,2, 3, 4, 5, 6,7）处订购多 /少钢管以及确定相应的运输路线lkm长的钢管为1单位的钢管，如果把管网分成每lkm—段，设共有r段，编号为h二1,2…r,则现在问题变为：如何从这7个工厂订购总数为r段（单位）钢管，使得费用】小即:每一段（共厂段）应从哪个工厂订购以及怎样组织运输路线才使总费用］小总费用包括购买钢管的费用与运输费用其中购买钢管的费用只与向各钢厂订购的钢管的数量有关，与运输路线无关运输费用包括从钢厂经铁路、 公路到管道结点，再沿管道旁的公路到施工处的运输费用。
因此可以把运输费 用分为从钢厂到管道结点的费用和沿管道旁的公路到施工处的运输费用注意：在之间的一段上，钢管经A或A |运到施工处丿 丿+1 J 丿+12.假设：（1） m, n分别是钢厂数和管网中的结点数个单位钢管从钢厂S,到管网结点A,的】小运价⑶tjk表示管网上相邻结点4与4之间的边长44 （里程数）⑷ 勺力表示钢厂S.到编号为h这一段的最低费用（包括订购和运输费用）I⑸Z.、in0,表示第力段不用钢厂S,的钢管1,表示第/I段用钢厂S的钢管则在S处订购钢管的数量为zih（h二1,2…r）中1的个数F面以Z?为决策变量in建摸2.建立模型:（1）求C ：求出各钢厂到各火车站的最短里程（这个涉及求最短路径的问题，在复U杂的情形下，用Dijkstra算法求解，但本题较简单可直接从图中看出最短路径求出这个最短路径后再根据铁路运价得到每单位钢管由钢厂到火车站的最低运价类似的方法可以得到火车站到各管网结点的最低运价把这二者结合起来便可以得到O（2）求匕「编号为h的一段可能是从S.运到A•后沿方向运到施工处，或者是从ih I J kS运到A后沿A方向运到施工处设编号h这一段在管网的边A. A上从A算起的Z K J J k J第q段,则eih = min{p + c.. +0.1/pi + cik +0.1*匕一q +1） }（对于管网是直线的情形，念入可依次编号，k取j+i） 以Z, （1=1, 2-m, h=l,2-r）作决策变量建立模型:(D0illS. T. 工 Z.‘ = 1 h=l,2-rminYzih e {0} o[500,5.],z = 1,2---m ③h=\z7 e{0,1}, ④1114•模型求解：（启发式算法）若没有约束条件③对每个h计算min匕，若匕在zo（/z）达到最小,即：盒阳=砸1匕（表示h这一段从磁（力个钢厂订购所需的费Qy力)1, i = i0(h)是问题①，②，④的最优解。
再逐步调整使满足③，每调一次使总费用最小的原则模型二（a）（问题一）若以c..记一个单位钢管从第i个钢厂s运到第j个枢纽站点A的最小购运费U f d J用，X..为s•到4.的运量再把A.得到的钢管分解为向A 路段铺设和向U J J 丿 丿-1A.A.+1路段铺设的两部分，记两部分的数量分别为兀和Z厂 A.A.+|路段的长度（即需铺设的钢管数量）为于是根据题意有：J7 15从$.到A的购运总费用为 工工cX.,而向两边铺设的费用为z（Z +i） y（y +1）O.lx— + 0.1X— ,于是问题的目标为：2 27 15 （J. 1 15w=zzcxy.+TE[Z7（z7+i）+y.（r+i）]（i）约束条件有:£X"W{0}U[500di = 1,2, • ••工 （2）7工X.. = Z. +K, （3）（A.处的钢管向左右铺设）気" 丿 丿 7b+Zj （4） （A,处钢管向右铺设的数量与Am处的钢管向左铺设的数量的和等于A A ,路段的长度（即需铺设的钢管数量） J 丿+1乙,=0,乙=104, （5）X（y>0,y >0,Zy >0,z = l,2,...7J = l,2,...,15, （6）关于模型的求解：由于约束条件(2)£X"・w{0}U[500eJ， 心12・・・7J=l J的存在，因此模型的求解不能简单地调用二次规划的软件，一种合理的解决办法是首先将该约束条件改为松弛条件于是模型便成为典型的二次规划，如果其最优解符合原有的约束条件，则便是问题的最优解，如果存在个别的7,使XX g (0,500),则可以针对这些，作调整。
1 y在求解过程中关键是要求出q：SIS2S3S4S5S6S7Al330. 7000370.7000385.7000420.7000410.7000410.7000435.7000A2320.3000360. 3000375.3000410.3000400. 3000405. 3000425. 3000A3300. 2000345. 2000355.2000395.2000380. 2000385.2000405.2000A425& 6000326.6000336.3000376.6000361.6000366. 6000386. 6000A519& 0000266. 0000276.0000316.0000301.0000306. 0000326. 0000A6180. 5000250.5000260.5000300. 5000285.5000295. 5000310.5000A7163. 1000241. 0000251. 0000291. 0000276. 0000281. 0000301. 0000A8181.2000226.2000241. 2000276.2000266. 2000271.2000291. 2000A9224. 2000269.2000203. 2000244. 2000234. 2000234. 2000259.2000A10252.0000297.0000237.0000222. 0000212.0000212.0000236. 0000All256.0000301.0000241. 0000211.0000188. 0000201.0000226. 0000A12266. 0000311.0000251. 0000221. 0000206. 0000195.0000216.0000A13281.2000362.2000266. 2000236.2000226. 2000176.200019& 2000A1428& 0000333.0000273. 0000243. 0000228. 0000161.0000186. 0000A15302. 0000347.0000287. 0000257.0000242. 000017& 0000162. 0000下面利用quadprog函数来计算 quadprog函数简介：minxTHx+fTx.s. t. A* x
