一类运输问题的非线性规划模型.pdf

《一类运输问题的非线性规划模型.pdf》由会员分享，可在线阅读，更多相关《一类运输问题的非线性规划模型.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2002211222收稿,2003202209修回。3 广西新世纪高等教育教学改革工程项目,广西民族学院重点科研项目。3 3 桂林电子工业学院计算科学与应用物理系桂林541004(Dept.of Comp.Sci.andApplied Phy.,GuilinU niv.of Elec.Tech.,Guilin,Guangxi,541004,China)。广西科学Guangxi Sciences 2003,10(2):8691一类运输问题的非线性规划模型3A Conti nuum and Nonli near Programm i ngM odel of Transport Problem何登旭

2、曹敦虔莫永向3 3宋学强He DengxuCao DunqianM o YongxiangSong Xueqiang(广西民族学院数学与计算机科学系南宁市大学路80号530006)(Dept.ofM ath.and Comp.Sci.,GuangxiU niv.for N ationalities,80 Daxuelu,N anning,Guangxi,530006,China)摘要针对路费与路线长度的非线性关系、目的地的需求量及货物的未知价格等影响因素,建立钢管定购和运输问题的二次规划模型,并通过L I N GO6.0软件,成功地求解这一类复杂运输问题,从而得到完整的购运计划。该模型具有一般

3、性,可推导至类似问题中。关键词运输问题数学模型非线性规划最省路径中图法分类号O22112:U 116AbstractA second ti me programm ing model for purchase and transportation of steel tubes isdeveloped for a linear programm ing mode of transport cost and path length,demand of destinationsand unknown price of goods,A complex problem are sloved using

4、the software L I N GO6.0.Themodel could be genelized and applied to solution of si m ilar problem s.Key wordstransport problem,mathematicalmodel,nonlinear programm ing,shortest path1问题简述要铺设1条A1A2A15的输送天然气的主管道,如图1所示.附近有7个钢厂S1,S2,S7可以生产这种主管道钢管.图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站

5、,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km).为方便计,1 km主管道钢管称为1单位钢管.1个钢厂如果承担制造这种钢管,至少需要生产500个单位.钢厂Si在指定期限内能生产该钢管的最大数量为si个单位,钢管出厂销价1单位钢管为Pi万元,如表11 单位钢管的铁路运价如表211 000 km以上每表1钢厂钢管产量及单价Table 1Y ield and un it price of steel tubes of a steel m illisi(单位U nit)Pi(万元Tenthousand yuan)1800160280015531 00015542 00016052 000155

6、62 00015073 000160表2铁路运价Table 2Transport costs of railway里程M ileage(km)运价Transport cost(万元Tenthou2sand yuan)里程M ileage(km)运价Transport cost(万元Tenthou2sand yuan)3002050160037301350236017004435140026701800504014502980190055451500329011 0006068Guangxi Sciences,Vol110No12,M ay 2003 1994-2009 China Academ

7、ic Journal Electronic Publishing House.All rights reserved.http:/图1钢管运输路线Fig.1Transport route of steel tubes图2钢管运输路线Fig.2Transport route of steel tubes增加1至100 km运价增加5万元.公路运输费用为1单位钢管每公里0.1万元(不足整km部分按整km计算).钢管可由铁路、公路运往铺设地点(不只是运到A1,A2,A15,而是管道全线).问题1请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用).问题2如果要铺设的管道不是一条线,而一个

8、树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图2按问题1的要求给出模型和结果.2问题分析为了求出定购计划,首先应该知道从各钢厂到各铺设路段运送单位钢管所需费用最小的路径.为此,我们定义:定义1使得从钢厂Si运送单位钢管到铺设端点Aj的费用最小的路径称为从Si到Aj的最省路径.如果可以预先知道运往各铺设端点的钢管量,那么原问题就是一个纯粹的运输问题,而运输问题已经有着比较成熟的解法1,3.然而我们遇到的并非如此简单.各铺设端点只有一个相当大的取值范围(而不是一个确定的值),确定这些值只能由运输和铺设的限制条件以及费用极小来决定.由于需铺设的总长度是相当长的,而一根

9、钢管的长度相对来说就小得多,所以可以认为:从铺设端点运送钢管到铺设地点时,钢管是连续不断、均匀地卸下的.基于以上原因,我们决定,首先求出各钢厂到各铺设端点的最省路径,然后根据限制条件和费用极小建立连续型规划模型,最后求出整个购运计划.3模型假设假设1施工公路与普通公路路况一样;假设2在实际运输时,经过的路径不会出现这样的情况:公路夹于两段铁路之间,或铁路夹于两段公路之间;假设3在实际运输时,总是这样来运输的:先运往铺设端点(指A1,A2,)再运到铺设地点;假设4铺设是均匀、连续的,卸货也是均匀、连续的.在后面的论述中,我们总是假设所有的钢管量以km为单位,所有的费用以万元为单位.4模型建立首先

10、,我们针对图1建立数学模型.411最省路径容易知道,要使总费用最小,所走的路径就应该是最省路径.所以我们首先求出各条最省路径.对于在一般赋权图中求最短路径问题已有许多成熟的方法,可以运用到这里.但由于铁路费用比较特殊(单位路长费用不是定值),所以必须做些特殊处理.经过观察我们发现,图1中所有铁路及火车站构成一颗树,要把钢管从任一钢厂运至铺设地点上都必须至少经过一个交接点(Bi),再根据假设2,每一次运输只能经过1个交接点.这样,在一次运输中,经过的铁路将是连接出发点(钢厂)和交接点的那条通路.不妨把它们直接用铁路连起来.这样我们可以按照如下方法构造新图:(?)在图1中将所有的钢厂与交接点全部用

11、铁路连接起来,铁路长度与图1中相应的铁路总长度一样.如果某个点既是钢厂又是交接点,则把它们拆成2个点,1个代表钢厂,1个代表交接点,它们之间的78广西科学2003年5月第10卷第2期 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/铁路长度赋值为0.()略去图1中的铁路及火车站(除交接点外).这样就得到1个新图,重新摆放各点的位置后的形状如图3.图3与图1等效的简化图Fig13Si mplified fig11我们给图3的所有边都赋予边权,它们的值是运送单位钢管经过该边

12、的费用(而不是路的长度).在此必须说明的是,在假设2的前提下,图1与图3是等效的.等效的意思是指:在图1中从任何1个钢厂走到任何1个铺设点,不管所走的是哪一条路,在图3中都有惟一的路径与之相对应,并且费用相等.这样,图3中的所有的边权值都可以从图1及铁路、公路运价求出.譬如,S1B1=160,B1A2=0.3,A1A2=10.4.由于篇幅关系,在此不再一一给出.图3是一个典型的赋权图,可用Dijkstra算法3、逐次逼近法4等算法求出从Si到Aj的最省路径和相应费用,在此我们采用逐次逼近法.为节省篇幅,结果在此将不给出,读者可自行计算,程序可参见文献4.412目标函数(费用表达式)设从钢厂Si

13、运往铺设端点Aj的钢管量为xij,那么,购买费用为71=7i=115j=1Pixij.用wij表示从Si到Aj的最省路径相应的费用,则运输过程中的费用为72=7i=115j=1(wij)xij.因为钢管运到铺设端点Aj后,还要运往铺设地点.在图3中,铺设端点的度最大为2,所以每个端点运送的方向最多有2个,可设Aj向左运送的钢管量为Lj,向右运送的钢管量为Rj,显然有Rj+Lj=7i=1xij,j=1,2,15,R15=0,L1=0.(1)再由假设4,卸货是均匀的,当从铺设端点Aj向左运输钢管走了tkm时,剩余在车上的钢管量为Lj-t,所以将钢管运至Aj后再向左运输需要的费用(73)Lj=eLj

14、0(Lj-t)dt=12eL2j.其中e是运输1单位钢管每公里的公路运费。同理,将钢管运至Aj后再向右运输需要的费用(73)Rj=eRj0(Rj-t)dt=12eR2j.因此这期间的总费用为73=15j=1(73)Lj+(73)Rj)=15j=112e(L2j+R2j).购买费用、从钢厂运往铺设端点的费用、从铺设端点运至铺设地点的费用构成了全部费用的总和.所以,总费用为7=71+72+73=7i=115j=1Pixij+7i=115j=1wijxij+15j=112e(L2j+R2j).(2)413 约束条件 根据需铺设的钢管总长度为5171个单位,而且运输量总是非负的,所以7i=115j=1

15、xij=5171.(3)再根据假设4,铺设是均匀的(不重叠不遗漏),所以有Rj+Lj+1=AjAj+1,j=1,2,14,(4)其中AjAj+1表示从Aj到Aj+1需要铺设钢管的长度.由于钢厂Si的产量上限为si,所以15j=1xijsi,i=1,2,7.(5)而每个钢厂都有自己的产量下限.如果生产,则必须不小于500,否则就不生产,产量为0.即15j=1xij=0,或15j=1xij500,i=1,2,7,(6)为了方便求解,我们将上式改写成如下等价形式(在产量非负的条件下):15j=1xij(15j=1xij-500)0,i=1,2,7.(7)414 数学模型 由(1)(7)可以得到一个连

16、续非线性规划模型:88Guangxi Sciences,Vol110No12,M ay 2003 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/m in7=7i=115j=1Pixij+7i=115j=1wijxij+15j=112e(L2j+R2j).S.T.7i=115j=1xij=5 171.15j=1xijsi,i=1,2,7,Rj+Lj=7i=1xij,j=1,2,15,R15=0,L1=0.(9)Rj+Lj+1=AjAj+1,j=1,2,14,15j=1x

17、ij(15j=1xij-500)0,i=1,2,7,xij0,i=1,7,j=1,15.这就是我们所要建立的钢管购运计划数学模型.5模型求解这是1个非线性规划模型.由于模型中变量太多,人 工 求 解 很 难 进 行.我 们 使 用 数 学 软 件L I N GO610,成功地求解这个模型,从而得到完整的购运计划.首先是去钢厂购买钢管的计划,表3列出了具体的购买方案,所花费用 71=797 725;然后是将钢管运至铺设端点,运输方案也在表3中给出,运输费 72=399 731.55;最后是把钢管从铺设端点运到铺设地点,表4给出了运输方法,运输费 73=15j=112e(R2j+L2j)=80 9

18、16.45.这样总费用就是7=71+72+73=1 278 373.6模型强化如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,我们的方法同样是适用的,因为在求最省路径时,我们并不排除铁路、公路和管道构成网络的情形.实际上,图2与图1的差别主要是铺设端点的度数不同.因此,只要对第一个模型稍作修改,就可以解决这种更一般的情形了.对图2运用相同的方法进行改造,得到的新图如图4所示,其中的边权可以根据图2求出 1在图4中,铺设路径上的结点的最大度数为3,表3在图1中从钢厂购买钢管然后运到铺设端点的计划Table 3Plans on conveying of the steel t

19、ubes purchased from steel m ill to the paving point in Fig.1钢厂Steelm ill购买量Purchase(单位U nits)购买费用Expenses(万元Tenthousandyuan)运输路径(在图1中)Transport route(in fig 1)运量xijQ uantitesxij(单位U nits)单价U nit price(万元Tenthousandyuan)运费Transport costs(万元Tenthousandyuan)S1800.0128000S1B6B5B4A5334.538.012711.0S1B6B5

20、A6200.020.54100.00S1B7A7265.53.1823.05S2800.0124000S2B8B3B1A2179.0205.336748.70S2B3A4134.1171.623011.56S2B8B7B6B5B4A5186.9111.020745.90S2B8A8300.071.221360.00S31000.0155000S3B9B8B7B6B5B4A5A4333.9181.660636.24S3B9B8B7B6B5B4A52.1121.0254.10S3B9A9664.048.232004.80S40.00无Non0.00.00.00S51015.0157325S5B11

21、B10B9B8B3B2A3508.0225.2114401.60S5B11B10B9B8B7B6B5B4A592.0146.013432.00S5B11A11415.033.013695.00S61556.0233400S6B15B13B10A10351.062.021762.00S6B15B13B12A1286.045.03870.00S6B15B13A13333.026.28724.60S6A14621.011.06831.00S6B15B16A15165.028.04620.00S70.00无Non0.00.00.00合计Total5171.07977255171.01547.93997

22、31.5598广西科学2003年5月第10卷第2期 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/表4从铺设端点到铺设地点的计划Table 4Plan of paving point to paving pointjLj(单位U nits)Rj(单位U nits)费用Transportcost(万元Tenthousandyuan)j(单位U nits)Lj(单位U nits)Rj(单位U nits)费用Transportcost(万元Tenthousandyuan)1

23、0.00.00.09505.0159.014015.32104.075.0822.0510321.030.05197.053226.0282.06530.011270.0145.04696.254468.00.010951.21275.011.0287.35606.09.518366.312513199.0134.02877.856184.515.51714.02514286.0335.09701.057189.576.02084.312515165.00.01361.258125.0175.02312.5合计(Total)80916.45从结点运往铺设地点的方向数最多有3个,分别用D1j,D

24、2j,D3j表示从Aj运往3个方向的运量,各方向的取法如下(其中的方向都是指在图4中的方向):(i)如果结点Aj的度为1,说明从该结点运出的方向只有一个,D1j就是这个方向上的运量,并且令D2j=0,D3j=0.这样的结点有A1,A15,A16,A18,A21;(ii)如果结点Aj的度为2,说明从该结点运出的方向有2个,D1j表示向左方向的运量,D2j表示向右方向的运量,并且令D3j=0.这样的结点有A2,A3,A4,A5,A6,A7,A8,A10,A12,A13,A14,A19,A20.(iii)如果结点Aj的度为3,则D1j表示向左方向的运量,D2j表示向右方向的运量,D3j表示向下的运量

25、.这样的结点有A9,A11,A17.用类似于前面建立模型的方法对问题三建立模型如下:m in7=7i=121j=1Pixij+7i=115j=1wijxij+21j=112e(D12j+D22j+D32j).S.T.7i=121j=1xij=5 903,21j=1xijsi,i=1,2,7,21j=1xij(21j=1xij-500)0,i=1,2,7,D1j+D2j+D3j=7i=1xij,j=1,2,21,D2j+D1j+1=AjAj+1,j=1,2,14,D39+D116=42,D311+D117=10,D217+D118=130,D317+D119=190,D219+D120=260,

26、D220+D121=100,D11=D215=D216=D316=D218=0,D318=D319=D320=D221=D321=0,D3j=0,j=1,8,10,12,15.xij0,i=1,7,j=1,21.求解以上模型得到表5、表6的购买和运输计划.由此可知 71=910 515,72=412 089.55,73=21j=112e(D12j+D22j+D32j)=86 087.15,总费用7=71+72+73=1 408 691.7.7模型评价本文所讨论的问题用线性规划来求解是无法得到满意结果的,这主要是因为钢管从铺设端点运往铺设地点时的运费不与路长成线性关系,为此我们建立二次规划模型,

27、为的是真实反映实际操作中的各种条件限制和费用,结果是合理可用的.虽然我们求解的只是一个特定的实际问题,但其中的方法具有一般性,容易推广到类似的问题中.如果只是运输路线图的不同,则只需修改相应数据就可以了.图4与图2等效的简化图Fig 4Si mplified fig.209Guangxi Sciences,Vol110No12,M ay 2003 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/表5在图2中从钢厂购买钢管然后运到铺设端点的计划Table 5Plans o

28、n conveying of the steel tubes purchased from steel m ill to paving point in f ig.2钢厂Steelm ill购买量Purchase(单位U nits)购买费用Expenses(万元Tenthou2sand yuan)运输路径(在图1中)Transport route(in fig 1)运量xijQ uantitesxij(单位U nits)单价U nit price(万元Tenthou2sand yuan)运费Transport costs(万元Tenthou2sand yuan)S1800.0128000S1B

29、6B5B4A5334.538.012711.00S1B6B5A6200.020.54100.00S1B7A7265.53.1823.05S2800.0124000S2B8B3B1A2179.0205.336748.70S2B8B3B2A3321.0190.261054.20S2B8A8300.071.221360.00S31000.0155000S3B9B8B3B2A380.0200.216016.00S3B9B8B7B6B5B4A5214.0121.025894.00S3B9A9664.048.232004.80S3A1642.044.01848.00S40.00无Non0.00.00.00

30、S51613249938S5B11B10B9B8B3B2A3107.0225.224096.40S5B11B10B9B8B7B6B5A5A4468.0206.696688.80S5B11B10B9B8B7B6B5A567.0146.09782.00S5B11B10A10351.057.020007.00S5B11A11415.033.013695.00S5A17205.032.06560.00S61690.0294000S6B13B18B12A1286.045.03870.00S6B13A13333.016.25394.60S6A14621.011.06831.00S6B15B16A15165

31、.028.04620.00S6B13A1865.037.02405.00S6B15B13B18A1970.044.03080.00S6A20250.010.02500.00S6A21100.00.00.00S70.00无Non0.00.00.00合计Toltal590391051559031832.70412089.55表6从铺设端点到铺设地点的计划Table 6Plan of paving point to paving pointjD1j(单位U nits)D2j(单位U nits)D3j(单位U nits)费用Transportcost(万元Tenthou2sand yuan)jD1j(

32、单位U nits)D2j(单位U nits)D3j(单位U nits)费用Transportcost(万元Tenthou2sand yuan)10.00.000.01275.011.00287.32104.075.00822.0513199.034.002877.83226.082.0065301486.0335.009701.04468.00.0010951.215165.0001361.255606.09.5018366.3121642.00088.26184.515.501714.0251710.065.0 130.0 1061.257189.576.002084.3121865.000

33、211.258125.0175.002312.51960.010.001859505.0159.0014015.320250.000312510321.030.005197.0521100.00050011270.0145.004696.25合计(Total)86087.1参考文献1张莹.运筹学基础.北京:清华大学出版社,1999.5253.2戴一奇,胡冠中,陈卫.图论与代数结构.北京:清华大学出版社,1995.8.3胡运权.运筹学教程.北京:清华大学出版社,1998.238239.4楼世博,金晓龙,李鸿祥.图论及其应用.北京:人民邮电出版社,1982.437439.(责任编辑:黎贞崇)19广西科学2003年5月第10卷第2期 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/