数学建模——数学建模全国大学生数学建模型竞赛练习题评.ppt
《数学建模——数学建模全国大学生数学建模型竞赛练习题评.ppt》由会员分享,可在线阅读,更多相关《数学建模——数学建模全国大学生数学建模型竞赛练习题评.ppt(35页珍藏版)》请在三一文库上搜索。
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的钢管总数量,j=1,2, ,m; 5.待铺设的管道,记作Pjk(jk),表示Aj与Ak之
3、间有一条待铺设的管道,它的长度也用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中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C,3.将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G,若i,j不连通,则令Gij=+. 4.对于一组(i,j)1,2, ,n1,2, ,m,如果Cij+,且小于Gij,那么就在公路费用图中加一条边,即令Gij=minCij,Gij. 5.利用图的标准最短路算法,求公路费用图中任一个S点到任一个
5、A点的最小费用路径,得出SAP矩阵.如表1所示:,表1 图1的SAP矩阵(待续),表1续,经过这一变换,问题大大简化,下面将原问题用纯数学语言作一个描述,即建立问题的数学模型. 3.3 问题的数学描述 常量:Ri:第i个工厂的钢管单价,Li:第i个工厂的产量上限. 变量表:Si,SAQij, Aj,AAQjk 模型为:,min(c1+c2+c3) S.t.,4 问题的求解 上面的数学描述中,最难处理的是Si=0orSi=500这个条件.求解过程分为三步: A.假设工厂的产量只有上限,下面的三个流网络模型都是针对这种情况的. B.假设工厂的产量有上下限,“产量有下限的模型”一节讨论这种情况. C
6、.工厂的产量0,500,Li,“基于分支定界搜索的求解过程”一节讨论这种情况.,4.1 线性费用流网络模型一 下面建立一个线性费用流网络的模型(图1): Source层 (Li,Ri) S层 (+,SAPij) A层 (1,1),(1,2),(1,3) P层 (1,0) Target层,图1,图中边上的(A,B),A表示边的流量限制,B表示边的单位流量的费用,下同. 1)网络有一个源点Source,从Source到每个S点有一条边,边的流量限制为Si的最大产量Li,单位费用为Si生产钢管的单价Ri. 2)从Si到Aj有一条边,边的流量限制为+,单位费用为SAPij,即从Si到Aj运输单位长度钢
7、管的费用. 3)对于每一条要铺设的管道P,设其长度为Len,两端点为Aj,Ak,则P对应着个Len点,分别表示要铺设的一个单位长度的钢管(如图中P11,P12,P13),从Aj到这Len个点各有一条边,边的流量限制为1,单位费用分别为1,2,3, ,Len,从Ak到这Len个点也各有一条边,边的流量限制为1,单位费用分别为Len,Len-1, ,3,2,1,4)从3)中的点(代表每单位长度的钢管的点)到图的汇点Target各有一条边,流量限制为1,单位费用为0. 这种流网络模型最简单,效率也较低.设铺设的管道共有Tl公里,显然Tln与m.网络中的点数大约为Tl个,边数大约为3Tl,最大流量为T
8、l.标准的网络流算法的时间复杂度为O(V3MaxFlow),因此,这个模型的复杂度为 O(Tl4).对于题中的数据, Tl大约在5000左右, Tl41015,不可承受. (关于算法复杂度问题可以参看资料:谢政,李建平或者,谢金星,刑文训),4.2 线性费用流网络模型二(图2) Source层 (Li,Ri) S层 (+,SAPij) A层 (1,1),(1,2),(1,3) P层 (Pi,0) Target层,模型一之所以效率低,最主要的问题是流网络中的点太多了.通过点的合并,可以大幅减少流网络中点的个数.将线性费用流网络模型一中对应同一段要铺设的管道的点合并成一个点(即模型一图中的P11,
9、P12,P13合并为P1),从A点到这些点的边现在全部转到一个点上(如图),从这些点到Target的边合并为流量限制为Pi(Pi即要铺设的管道的长度),单位费用为0的一条边. 模型二中的点数为n+m+Pcount+2,边数大约为2Tl个.均比模型一有了大幅减少,然而边数仍然太多,而且这张流网络不是一个简单图(A层与P层中两个点之间的边数1),因此,不能直接套用标准最小费用最大流的复杂度计算公式.,4.3 非线性费用流网络模型(图3) Source层 (Li,Ri) S层 (+,SAPij) A层 (Pi,F(F+1)/2) P层 (Pi,0) Target层,第三种模型是非线性费用网络流模型.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 全国大学生 竞赛 练习题
链接地址:https://www.31doc.com/p-2279656.html