资源描述：
《钢管的订购和运输解答模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第31卷第1期数学的实践与认识Vol131No112001年1月MATHEMATICSINPRACTICEANDTHEORYJan.2001钢管的订购和运输解答模型邵铮,周天凌,马健兵指导老师:扈志明(清华大学,北京100084)编者按:本文把B题的问题1和3归结为网络最小费用流问题,建立了线性和非线性最小费用流模型,并运用相应的解法和分支定界法求解,叙述清晰,简洁,层次分明.本刊予以部分发表.我们指出:本文的网络流模型和线性规划中标号运输问题模型是等价的.摘要:首先通过最短路算法简化了供需距离
2、网络,去掉了铁路、公路等边的性质,使供需距离网络简化为一个供需运输价格表.在此基础上构造了三个模型:线性费用的网络流模型、改进的线性费用的网络流模型和具有非线性费用的网络流模型.通过改进传统的最小费用最大流算法,解决了本题的非线性费用网络流模型,并给出了算法的正确性证明与复杂度分析.关键词:运输问题;网络流;树形网络;分支定界1问题的提出(略)2基本假设和符号说明2.1基本假设1.原图是一个连通的简单图;2.铁路、公路的运量没有限制;3.为了满足费用最小的要求,允许出现生产过剩现象;4.工厂的数
3、目(图中S点的个数)不太多,约在10个以下;5.待铺设的钢管长度不太长,约在10000公里以下;6.待铺设的线路的段数不太多,约在40段以下;7.公路运输不足整公里部分按整公里算.2.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.待
4、铺设的管道,记作Pjk(j≠k),表示Aj与Ak之间有一条待铺设的管道,它的长度也用Pjk来表示,如果Aj与Ak之间没有待铺设的管道,则Pjk=0;6.SAQij表示从Si到Aj的运输量,i=1,⋯n,j=1,⋯m;7.SAPij表示从Si到Aj运输单位长度钢管的最小费用,i=1,⋯n,j=1,⋯m;8.AAQjk表示Aj提供的用于铺设Aj与Ak之间管道的长度,j,k=1,⋯m.显然有68数学的实践与认识31卷AAQjk+AAQkj=Pjk;9.下文所有费用的单位均为千元.3问题的分析与简化3.
5、1问题的分析整个铺设管道的工程看似错综复杂,其实可分为三个部分:1.各个工厂(S点)生产一定数量的钢管2.把钢管从工厂(S点)运送到铺设管道的关节点(A点)3.从关节点(A点)将管道运至铺设地点这三个部分是相互依赖的,不能简单地把三个部分孤立开来讨论.但是通过仔细观察,我们发现第二部分中的运费事实上只与出发点(S点)、目标点(A点)和运量有关,并且是运量的线性函数,具备可叠加性.nm运输总费用:W=∑∑SAQij×SAPij.i=1j=1因此,我们可以简化第二部分的计算,即先从铁路与公路网络得出
6、SAP矩阵.3.2问题的简化求SAP矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法.下面叙述求SAP矩阵的过程:1.利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如果两个点之间不连通,认为它们之间的最短路长度为+∞).2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C.3.将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G
7、,若i,j不连通,则令Gij=+∞.4.对于任一组(i,j)∈{1,⋯n}×{1,⋯m}如果Cij<+∞,且小于Gij,那么就在公路费用图中加一条边.即令Gij=min{Cij,Gij}.5.利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用路径,得出SAP矩阵.如表1所示:表1图1的SAP矩阵A123456789101112131415S117071603140298638020531212642920960106012121280142022157205319021716
8、1110955860712114214201460156017121780192032307220320021816121010559608624828208609601112118013204260725032352216615601405131011628426205106107628309705255724532252206614601305121011127925703305107127308706265725532352216615601405131012128426205104502
