资源描述：
《数学建模——数学建模全国大学生数学建模型竞赛练习题评》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、全国大学生数学建模竞赛培训班练习题评讲钢管的订购和运输钢管的订购和运输解答模型摘要首先通过最短路算法简化了供需距离网络,去掉了铁路、公路等边的性质,使供需距离网络简化为一个供需运输价格表.在此基础上构造了三个模型:线性费用的网络流模型和具有非线性费用的网络流模型.通过改进传统的最小费用最大流算法,解决了本题的非线性费用网络流模型,并给出了算法的正确性证明与复杂度分析.关键词运输问题;网络流;树形网络;分支定界1.问题的提出(略)2.基本假设和符号说明2.1基本假设1.原图是一个连通的简单图;2.铁路、公路的运量没有限制;3.为了满足
2、费用最小的要求,允许出现生产过剩现象;4.工厂的数目(图中S点的个数)不太多,约在10个以下;5.待铺设的钢管长度不太长,约在10000公里以下;6.待铺设的线路的段数不太多,约在40段以下;7.公路运输不足整公里部分按整公里计算.2.2符号说明1.工厂(图中S点)设有n个,记作S1,S2,…,Sn;2.在不至于混淆的情况下,Si同时用来表示每个工厂的产量,i=1,2,…,n;3.待铺设线路的端点(图中A点,以后简称关节点),设有m个,记作A1,A2,…,Am;4.在不至于混淆的情况下,Aj同时用来表示从各个工厂运到Aj的钢管总数量
3、,j=1,2,…,m;5.待铺设的管道,记作Pjk(j≠k),表示Aj与Ak之间有一条待铺设的管道,它的长度也用Pjk来表示,如果Aj与Ak之间没有待铺设的管道,则Pjk=0;6.SAQij表示从Si到Aj的运输量,i=1,2,…,n,j=1,2,…,m;7.SAPij表示从Si到Aj运输单位长度钢管的最小费用,i=1,2,…,n,j=1,2,…,m;8.AAQjk表示Aj提供的用于铺设Aj与Ak之间管道的长度,j,k=1,2,…,m,.显然有:AAQjk+AAQkj=Pjk;9.下文所有费用的单位均为千元.3.2问题的简化求SAP
4、矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法.下面叙述求SAP矩阵的过程:1.利用图的标准最短路算法,从铁路网得出图中任两个点之间的最短路径表T(如果两个点之间不连通,认为它们之间的最短路长度为+∞).2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C3.将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G,若i,j不连通,则令Gij=+∞.4.对于一组(i,j)∈{1,2,…,n
5、}×{1,2,…,m},如果Cij<+∞,且小于Gij,那么就在公路费用图中加一条边,即令Gij=min{Cij,Gij}.5.利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用路径,得出SAP矩阵.如表1所示:表1图1的SAP矩阵(待续)AS12345671234567170721572307260725572657275716032053220325032453255326531402190220022352225223522452986171618162166206621662266380111012101
6、56014601560166020595510551405130514051505318609601310121013101410表1续8910111213141521271286211621112121213126421142482842792842992920142082062057062076096014608605103305106601060156096061051045056012121712111276271226238212801780118083073011026014201920132097087028020经过
7、这一变换,问题大大简化,下面将原问题用纯数学语言作一个描述,即建立问题的数学模型.3.3问题的数学描述常量:Ri:第i个工厂的钢管单价,Li:第i个工厂的产量上限.变量表:Si,SAQij,Aj,AAQjk模型为:min(c1+c2+c3)S.t.4问题的求解上面的数学描述中,最难处理的是Si=0orSi>=500这个条件.求解过程分为三步:A.假设工厂的产量只有上限,下面的三个流网络模型都是针对这种情况的.B.假设工厂的产量有上下限,“产量有下限的模型”一节讨论这种情况.C.工厂的产量∈{0,[500,Li]},“基于分支定界搜索
8、的求解过程”一节讨论这种情况.4.1线性费用流网络模型一下面建立一个线性费用流网络的模型(图1):Source层(Li,Ri)S层…(+∞,SAPij)A层…(1,1),(1,2),(1,3)P层…(1,0)Target层Source
