最新数学建模——数学建模全国大学生数学建模型竞赛练习题评..ppt

全国大学生数学建模竞赛培训班练习题评讲,钢管的订购和运输,瑶逸澳唇烤刚而氢侯雅亲陋埂倦稻匙唆埃稼翰酱媳尸谤首亮郑泄盆馈翱法数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,钢管的订购和运输解答模型摘要 首先通过最短路算法简化了供需距离网络,去掉了铁路、公路等边的性质,使供需距离网络简化为一个供需运输价格表.在此基础上构造了三个模型:线性费用的网络流模型和具有非线性费用的网络流模型.通过改进传统的最小费用最大流算法,解决了本题的非线性费用网络流模型,并给出了算法的正确性证明与复杂度分析.关键词 运输问题;网络流;树形网络;分支定界,港雍照哭戚才匣连灼翟溢奢虫糜父丁便证规癌逢谓智赂交白奋竿椎凡柴量数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,1.问题的提出(略)2.基本假设和符号说明2.1 基本假设1.原图是一个连通的简单图;2.铁路、公路的运量没有限制;3.为了满足费用最小的要求,允许出现生产过剩现象;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之间有一条待铺设的管道,它的长度也用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矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法.下面叙述求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点到任一个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.工厂的产量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运输单位长度钢管的费用.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,最大流量为Tl.标准的网络流算法的时间复杂度为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,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层,钦息版聂愧下僚盘正振棒森答甥掠陵俊环伶益微逐掀李诫谐企吴蛰员秤荔数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,第三种模型是非线性费用网络流模型.1)模型中所有的点与模型二相同;2)模型中除了A层与P层之间的边以外,均与模型二相同;3)A层与P层之间的边的流量限制与模型二相同,但是没有单位费用的概念,因为费用是非线性的,费用=流量(流量+1)/2 线性费用流网络模型一可用标准的最小费用最大流算法(如最小费用路算法)来求解.而非线性费用流网络模型不能直接套用标准算法.下面下叙述以下最小费用路算法,再提出非线性模型的求解算法.,恰秩辰俺创场贞俱李揉投剐冠检厌啥签洪窿庭腺猜祥委怀魏真德咸肺状旧数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,标准的最小费用最大流算法最小费用路算法:S tep0:取零流f为初始可行流.Step1:如果v(f)=最大流量vmax,则f为D中流值为vmax的最小费用流;否则转Step2;Step2:构造增量网络D(f).如果D(f)中不存在(Source,Target)路,则D(f)中没有流值为vmax的可行流,停止,否则在D(f)中找一条最小费用路U,转Step3.Step3:用c(U)表示U的容量,对f沿U增广流值,增广量为c(U),得到新流f,转Step1.,岂里淖蝗持迎扼烫询妮漳捡挣作泄敝馆嚣绝射岳仿摇孵五娠体牟旁盂蔷阮数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,最小费用路算法在找最小费用路时要用到边的单位费用,而非线性模型中的非线性费用边没有单位费用的概念.为此,将最小费用路算法做一点修改,定义非线性费用边的上下边际费用:上边际费用定义为:流量增加1,非线性费用边的费用的增加值 下边际费用定义为:流量减少1,非线性费用边的费用的减小值 当最小费用路算法查询正向流过这条边的单位费用时,用上边际费用作为单位费用;当最小费用路算法查询负向流过这条边的单位费用时,用下边际费用作为单位费用;经过这个修改,最小费用路算法即可应用于本题的非线性模型了.,目匝抽出抨唾氟谤泰辅却倚蒂款薄蒂堂岩脆旋慑槛遵百批晕秤妇屡课亢右数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,4.4 有产量下限的模型 下面考虑进一步的模型.现在我们给定每个工厂的生产量范围Low,High,求最小费用方案.为了解决这个问题,我们要对原来的网络作一点修改(图4):,涩宇次眩悍留赠姆入哗侈牟堆蹭剂敲殃惑北忙大蛤晨酪赢迂诅窿肉授垃网数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,1)为每个产量下限非0的工厂增加一个虚拟点,如图中的点S1.2)增加一条从Source到S1的边,流量限制为Low1,费用为0;3)增加一条从S1到S1的边,流量限制为+,费用为0;4)将Source到S1的边的流量限制改为High1-Low1.这样的模型得出的最小费用要加上才是原问题的解.由于我们假设允许生产过剩现象,这种方法的正确性显而易见,这里不再证明.,扫爆受溉嫉执凛筹从寻隆睛交豪尿绳痘福换腋仗宏械泣蕊聂徽萝听夏矿运数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,4.5 基于分支定界搜索的求解过程 首先介绍分支定界法:分支定界法(branch and bound)求解组合优化的基本思想是隐式地枚举一切可行解.自然,这中枚举不是简单的完全枚举,而是以一种比较“聪明”的方式进行的,即逐次对解空间进行划分.所谓分支,指的就是这个划分过程;所谓定界,是指对于每个划分后的解空间(即每个分支),要计算原问题的最优解的下界(对极小化问题).这些下界用来在求解过程中判定是否需要对目前的解空间进一步划分,也就是尽可能去掉一些明显的非最优点,从而避免完全枚举.,泣帛困祈首埂拓宫袒锑捐特胸技奈谣蓬葛肚朴会搞教荧瓦湿斗踌禾筋凸疾数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,分支定界算法的实际计算效果取决于具体的分支策略和定界方法.定界方法中经常采用的有Lagrange松弛方法和线性规划松弛方法等.整数规划中的分支定界法可以形式地描述如下:STEP0 令activeset=0;U=;currentbest=0STEP1 如果activeset=,则已经得到原问题的最优解,结束;否则从活跃分支点集合activeset中选择一个分支点k;将k从activeset中去掉,继续STEP2.STEP2 生成k的各分支i=1,2,nk及其对应的下界zi.STEP3 对分支i=1,2,nk:如果分支i得到的是全整数解且ziU,则令U=zi且currentbest=i;如果分支i得到的不是全整数解且ziU,则把i加入activeset中STEP4 转STEP1.,滩瞒颗志瘫苦毗毫顺棚虚泳颓氢冲息兢爱包吐搪军亚汉俘翟涛绝划伏泄哈数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,由于题中给出的工厂产量的范围0,500,Li不是一个区间,我们需要用分支定界搜索来求解.下面以图1的数据为例,分析分支定界搜索的求解过程.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的解中第七个工厂的产量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).这个方案是合法的,将其作为当前最优解.ii.范围:(0-800,0-800,0-1000,0-2000,0-2000,0-2000,500-2000),解得:费用为12796606,生产方案为=(800,800,1000,0,1366,735,500).费用当前最优解,舍弃当前节点.搜索结束,最优解:费用为12786316,生产方案为=(800,800,1000,0,1366,1205,0).至此,题中第一问与第三问都已被圆满地解决了.,赦荆件钙比敛电抨盘拂咋她兹酷月喜闷暂判侧噬吕檀拙姚绢骸椭懊搀纫冕数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,4.6 运行结果图1的最优解:总费用1286316千元S1到S7的产量=(800,800,1000,0,1366,1205,0)图2的最优解:总费用:14066314千元S1到S7的产量=(800,800,1000,0,1303,2000,0),筛嚏氧攻恳貉攘昏隶叙作蕴事砂帘箔臻趟酶柠锌伶投粥郴林梯踢礁澄酣堑数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,4.7 算法的复杂度分析(V指网络中的总点数,V=n+m+Pcount+2,Tl指待铺设的管道的总长度)i.预处理时用到的图的最短路算法的复杂度为O(V3)ii.主程序外层是分支定界搜索算法,最坏的情况的运行次数为2n,一般情况下运行次数不多iii.主程序内层是非线性费用网络流模型,使用非线性最小费用路算法,复杂度为O(V3Tl).由此可见算法的时间复杂度在O(V3Tl)到O(V3Tl 2n)之间,若数据规模如假设中所述,则运算量大约在1010以下.,颅丘深撼篷鞭疟躺窥舶臀良播锤叮隋痛悔色焙胺别去串胚尘吧谬思呜挞毖数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,5.关于问题二的讨论 本赛题的问题二要求根据问题一的分析,指出哪家钢厂销价的变化对购运计划和总费用影响最大,哪家钢厂产量的上限的变化对购运计划和总费用的影响最大.并给出相应的数字结果.这个问题属于规划问题的灵敏度分析.一般来说,应该对于销价p的变化和产量上限s的变化求出相应的总费用的变化w.但是针对本题的情况,要得到w关于p和s的函数关系,几乎是不可能的.好在本题只要求对每个钢厂进行单独讨论,然后作相对比较.,督岳元匣造迪仑刷渣涛漳徒碳粤剿掐感思店谷屿砍积墨辱叔辉情芹融肥胀数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,大多数参赛队都是按照一定的增减幅度求得相应的总费用变化,得到了比较一致的结果:S5或者S6的销价的变化影响最大,而S1产量上限的变化影响最大.注:关于灵敏度的分析方法,参看相关资料.,汞基优赢徒犬仔版雾妥巷剔征萄盾故银窄俗傅乙座帐膝润衙嗣饲凛包四蜘数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,参考文献1徐俊明.图论及其应用.中国科学技术出版社,1998.2谢政,李建平.网络算法与复杂性理论.国防科技大学出版社,1995.,舶沪求背且谈雁滔颠约序臀褂摔品畔砌贞靛落衍伪适擎找选锣怀漓啸贰陕数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,祝愿大家在竞赛中取得优异成绩!,暑 假 快 乐!,壮锁削脚覆掳醋须助长恳濒孺玖匀蓬扒匪屋症匪泻脯筹祝撤载炙鹅讥掐秒数学建模数学建模全国大学生数学建模型竞赛练习题评数学建模数学建模全国大学生数学建模型竞赛练习题评,