1、第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001钢管的订购和运输解答模型邵铮,周天凌,马健兵指导老师:扈志明(清华大学,北京100084)编者按:本文把B题的问题1和3归结为网络最小费用流问题,建立了线性和非线性最小费用流模型,并运用相应的解法和分支定界法求解,叙述清晰,简洁,层次分明.本刊予以部分发表.我们指出:本文的网络流模型和线性规划中标号运输问题模型是等价的.摘要:首先通过最短路算法简化了供需距离网络,去掉了铁路、公路等边的性质,使供需距离网络简化为一个供需运输价格表.在此基础
2、上构造了三个模型:线性费用的网络流模型、改进的线性费用的网络流模型和具有非线性费用的网络流模型.通过改进传统的最小费用最大流算法,解决了本题的非线性费用网络流模型,并给出了算法的正确性证明与复杂度分析.关键词:运输问题;网络流;树形网络;分支定界1问题的提出(略)2基本假设和符号说明2.1基本假设1.原图是一个连通的简单图;2.铁路、公路的运量没有限制;3.为了满足费用最小的要求,允许出现生产过剩现象;4.工厂的数目(图中S点的个数)不太多,约在10个以下;5.待铺设的钢管长度不太长,约在10000公里以下;6.待铺设的线路的段数不太多,约在40段以下;7.公路运输不足整公里部分按整公里算.2
3、.2符号说明1.工厂(图中S点),设有n个,记作S1、S2,Sn;2.在不至于混淆的情况下,Si同时用来表示每个工厂的产量,i=1,n;3.待铺设线路的端点(图中A点,以后简称关节点),设有m个,记作A1、A2,Am;4.在不至于混淆的情况下,Aj同时用来表示从各个工厂运到Aj的钢管总数量,j=1,m;5.待铺设的管道,记作Pjk(jk),表示Aj与Ak之间有一条待铺设的管道,它的长度也用Pjk来表示,如果Aj与Ak之间没有待铺设的管道,则Pjk=0;6.SA Qij表示从Si到Aj的运输量,i=1,n,j=1,m;7.SA Pij表示从Si到Aj运输单位长度钢管的最小费用,i=1,n,j=1
4、,m;8.A A Qjk表示Aj提供的用于铺设Aj与Ak之间管道的长度,j,k=1,m.显然有A A Qjk+A A Qkj=Pjk;9.下文所有费用的单位均为千元.3问题的分析与简化3.1问题的分析整个铺设管道的工程看似错综复杂,其实可分为三个部分:1.各个工厂(S点)生产一定数量的钢管2.把钢管从工厂(S点)运送到铺设管道的关节点(A点)3.从关节点(A点)将管道运至铺设地点这三个部分是相互依赖的,不能简单地把三个部分孤立开来讨论.但是通过仔细观察,我们发现第二部分中的运费事实上只与出发点(S点)、目标点(A点)和运量有关,并且是运量的线性函数,具备可叠加性.运输总费用:W=ni=1mj=
5、1SA QijSA Pij.因此,我们可以简化第二部分的计算,即先从铁路与公路网络得出SA P矩阵.3.2问题的简化求SA P矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法.下面叙述求SA P矩阵的过程:1.利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如果两个点之间不连通,认为它们之间的最短路长度为+).2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C.3.将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G,若i,j
6、不连通,则令Gij=+.4.对于任一组(i,j)1,n1,m如果Cij+,且小于Gij,那么就在公路费用图中加一条边.即令Gij=m inCij,Gij.5.利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用路径,得出SA P矩阵.如表1所示:表1图1的SAP矩阵SA12345678910111213141511707160314029863802053121264292096010601212128014202215720531902 1716111095586071211421420146015601712178019203230722032002 1816121010
7、559608624828208609601112118013204260725032352 216615601405131011628426205106107628309705255724532252 206614601305121011127925703305107127308706265725532352 216615601405131012128426205104502621102807275726532452 226616601505141013129927606605603822602086数学的实践与认识31卷经过这一变换,问题大大简化,下面将原问题用纯数学语言做一个描述.3.3问
8、题的数学描述常量:Ri:第i个工厂的钢管单价,Li:第i个工厂的产量上限.变量表:Si,SA Qij,Aj,A A Qjkm in(c1+c2+c3)s.t.c1=ni=1SiRic2=ni=1mj=1SA QijSA Pijc3=mj=1mk=1(A A Qjk(A A Qjk+1)?2)Si=mj=1SA QijAj=ni=1SA QijAj=mk=1A A QjkA A Qjk+A A Qkj=PjkSi=5004问题的求解上面的数学描述中,最难处理的是Si=0 orSi=500这个条件.求解过程分为三步:A.假设工厂的产量只有上限,下面的三个流网络模型都是针对这种情况的.B.假设工厂的
9、产量有上下限,“产量有下限的模型”一节讨论这种情况.C.工厂的产量0,500,L i,“基于分支定界搜索的求解过程”一节讨论这种情况.4.1线性费用流网络模型一下面建立一个线性费用流网络的模型(图1):图中边上的(A,B),A表示边的流量限制,B表示边的单位流量的费用,下同.1)网络有一个源点Source,从Source到每个S点有一条边,边的流量限制为S i的最大产量L i,单位费用为Si生产钢管的单价Ri.2)从Si到Aj有一条边,边的流量限制为+,单位费用为SA Pij,即从Si到Aj运输单位长度钢管的费用.3)对于每一条要铺设的管道P,设其长度为L en,两端点为Aj,Ak,则P对应着
10、L en个点,分别表示要铺设的一个单位长度的钢管(如图中P11,P12,P13),从Aj到这L en个点各有一条边,边的流量限制为1,单位费用分别为1,2,3,L en,从Ak到这L en个点也各有一条边,边的流量限制为1,单位费用分别为L en,L en-1,3,2,1.4)从3)中的点(代表每单位长度的钢管的点)到图的汇点Target各有一条边,流量限961期邵铮等:钢管的订购和运输解答模型图1线性费用流网络模型一制为1,单位费用为0.这种流网络模型最简单,效率也较低.设铺设的管道共有T l公里,显然T l n与m.网络中的点数大约为T l个,边数大约为3T l,最大流量为T l.标准的网
11、络流算法的时间复杂度为O(V3M ax F low),因此,这个模型的复杂度为O(T l4).对于题中的数据,T l大约在5000左右,T l41015,不可承受.4.2线性费用流网络模型二(图2)模型一之所以效率低,最主要的问题是流网络中的点太多了.通过点的合并,可以大幅减小流网络中点的个数.将线性费用流网络模型一中对应同一段要铺设的管道的点合并成一个点(即模型一图中的P11,P12,P13合并为P1),从A点到这些点的边现在全部转到一个点上(如图),从这些点到T arget的边合并为流量限制为Pi(Pi即要铺设的管道的长度),单位费用为0的一条边.模型二中的点数为n+m+Pcount+2,
12、边数大约为2T l个.均比模型一有了大幅减小.然而边数仍然太多,而且这张流网络不是一张简单图(A层与P层中两个点之间的边数 1),因此,不能直接套用标准最小费用最大流的复杂度计算公式.4.3非线性费用流网络模型(图3)第三种模型是非线性费用网络流模型.1)模型中所有的点与模型二相同;2)模型中除了A层与P层之间的边以外,均与模型二相同;3)A层与P层之间的边的流量限制与模型二相同,但是没有单位费用的概念,因为费用是非线性的,费用=流量(流量+1)?2.07数学的实践与认识31卷图2线性费用流网络模型二图3非线性费用流网络模型线性费用流网络模型一可用标准的最小费用最大流算法(如最小费用路算法)来
13、求解.而非线性费用流网络模型不能直接套用标准算法.下面我们先叙述一下最小费用路算法,171期邵铮等:钢管的订购和运输解答模型再提出非线性模型的求解算法.标准的最小费用最大流算法最小费用路算法:Step 0:取零流f为初始可行流.Step 1:如果v(f)=最大流量vmax,则f为D中流值为vmax的最小费用流;否则转Step 2;Step 2:构造增量网络D(f).如果D(f)中不存在(Source,Target)路,则D(f)中没有流值为vmax的可行流,停止,否则在D(f)中找一条最小费用路U,转Step 3.Step 3:用c(U)表示U的容量,对f沿U增广流值,增广量为c(U),得到新
14、流f,转Step 1.最小费用路算法在找最小费用路时要用到边的单位费用,而非线性模型中的非线性费用边没有单位费用的概念.为此,将最小费用路算法做一点修改:定义非线性费用边的上下边际费用:上边际费用 定义为:流量增加1,非线性费用边的费用的增加值下边际费用定义为:流量减小1,非线性费用边的费用的减小值当最小费用路算法查询正向流过这条边的单位费用时,用上边际费用作为单位费用;当最小费用路算法查询负向流过这条边的单位费用时,用下边际费用作为单位费用;经过这个修改,最小费用路算法就能应用于本题的非线性模型了.4.4有产量下限的模型下面考虑进一步的模型.现在我们给定每个工厂的生产量范围Lowi,H ig
15、hi,求最小费用方案.为了解决这个问题,我们要对原来的网络作一点修改(图4):图4产量有上下限的非线性费用流网络模型1)为每个产量下限非0的工厂增加一个虚拟点,如图中的S1点,2)增加一条从Source到S1的边,流量限制为Low1,费用为0,3)增加一条从S1到S1的边,流量限制为+,费用为0,4)将Source到S1的边的流量限制改为H igh12Low1这样的模型得出的最小费用要加上ni=1LowiRi才是原问题的解.由于我们假设允许生产过剩现象,这种方法的正确性显而易见,这里不再证明.4.5基于分支定界搜索的求解过程由于题中给出的工厂产量的范围0,500,L i不是一个区间,我们需要用
16、分支定界搜索来求解.下面以图1中的数据为例,分析分支定界搜索的求解过程.27数学的实践与认识31卷1)将工厂产量的范围设定为(0-800,0-800,0-1000,0-2000,0-2000,0-2000,0-2000),求得一个解:费用为12753516,生产方案为=(800,800,1000,0,1366,960,245).2)由于1的解中第7个工厂的产量245(0,500),要将问题分解为两部分:i.范围:(0-800,0-800,0-1000,0-2000,0-2000,0-2000,0-0)解得:费用为12786316,生产方案为(800,800,1000,0,1366,1205,0
17、),这个方案是合法的,将其作为当前最优解ii.范围:(0-800,0-800,0-1000,0-2000,0-2000,0-2000,500-2000)解得:费用为12796606,生产方案为(800,800,1000,0,1336,735,500)费用当前最优解,舍弃当前节点搜索结束,最优解:费用为12786316,生产方案为(800,800,1000,0,1366,1205,0)至此,题中第一问与第三问都已被圆满的解决了.4.6运行结果 图1的最优解:总费用12786316千元S1到S7的产量=(800,800,1000,0,1366,1205,0)图2的最优解:总费用:14066314千
18、元S1到S7的产量=(800,800,1000,0,1303,2000,0)4.7算法的复杂度分析(V指网络中的总点数,V=n+m+Pcount+2,T l指待铺设的管道的总长度)i.预处理时用到的图的最短路算法的复杂度为O(V3)ii.主程序外层是分支定界搜索算法,最坏情况的运行次数为2n.一般情况下运行次数不多iii.主程序内层是非线性费用网络流模型,使用非线性最小费用路算法,复杂度为O(V3T l),;由此可见算法的时间复杂度在O(V3T l)到O(V3T l2n)之间.若数据规模如假设中所述,则运算量大约在1010以下.参考文献:1徐俊明.图论及其应用.中国科学技术大学出版社,1998
19、.2谢政,李建平.网络算法与复杂性理论.国防科技大学出版社,1995.M odel for Ordering and Transportation of Steel PipeSHAO Zheng,ZHOU T ian2ling,MA Jian2bing(T singhua U niversity,Beijing100084)Abstract:First we si mplified the supply2demand distance network by using the shortest2pathalgorithm.W e got rid of the properties of the
20、 railways and roads,reduced the supply2demand371期邵铮等:钢管的订购和运输解答模型第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001distance network to a supply2demand transportation price table.Based on this,we constructedthree models:the linear2cost2network2flow model,the developed lin
21、ear2cost2network2flowmodel and the non2linear2cost2network2flow model.By generlizing the traditional m ini mum2cost2maxi mum2flow algorithm,we solved the non2linear2cost2network2flow model.W e alsogave the truth proving and the complexity2analysis to our algorithm.订 购 和 运 输 钢 管 的 最 优 方 案陆维新,林皓,陈晓东指导
22、老师:周杰(四川大学,成都610064)编者按:该文建立了用于天燃气管道铺设的钢管订购和运输总费用最省的二次规划模型.总费用作为目标函数,钢管生产厂的产量限制等作为约束条件.所建模型通过定性分析与使用L ingo软件求解获得了满意的方案,并且计算量大大减少了.整篇文章理由描述充分,层次清楚,洞察力强而篇幅较短.摘要:本文研究铺设天燃气钢管的最优方案问题.我们建立了一个以总费用为目标函数的二次规划模型.1问题的重述与分析(略)2模型的假设与符号说明1)基本假设:要铺设的管道侧有公路,可运送所需钢管;钢管在运输中由铁路运转为公路运时不计换车费用;所需钢管均由Si(i=1,7)钢厂提供;假设运送的钢管路途中没有损耗.2)符号说明(i=1,2,7,j=1,2,15):si:钢厂Si的最大生产能力;pi:钢厂Si的出厂钢管单位价格(单位:万元);d:公路上一单位钢管的每公里运费(d=0.1万元);e:铁路上一单位钢管的运费(分段函数见表1);cij:1单位钢管从钢厂Si运到Aj的最小费用(单位:万元);bj:从Aj到Aj+1之间的距离(单位:千米);xij:钢厂Si运到Aj的钢管数;yj:运到Aj地的钢管向左铺设的数目;zj:运到Aj地的钢管向右铺设的数目;ti:=1,钢厂Si提供钢管0,钢厂Si不提供钢管;
