2009中山大学数学建模讲座演示教学.ppt

优化模型-数学建模华南理工大学理学院数学系刘深泉教授ExperimentalMathematicsComputerFormulaforPiIn1996,aPSLQprogramdiscoveredthisformulaforpi:Indeed,thisformulapermitsonetodirectlycalculatebinaryorhexadecimal(base-16)digitsofbeginningatanarbitrarystartingpositionn,withoutneedingtocalculateanyofthefirstn-1digits.SrinivasaRamanujanOptimization-mathematicalprogrammingchoosingthebestelementfromsomesetofavailablealternativesLinearprogrammingIntegerprogramming.QuadraticprogrammingNonlinearprogramming.ConvexprogrammingSemidefiniteprogrammingStochasticprogramming.Robustprogramming.Combinatorialoptimization.Infinite-dimensionaloptimizationHeuristicalgorithmsConstraintsatisfactionOptimalcontrol.Dynamicprogramming.Mathematicalprogramming序数理论，选择理论Computationaloptimizationtechniques SinglevariablesOptimization MultivariablesOptimization 优化算法1.Dijkstra算法，2.最小生成树Prim算法，3.最小费用，4.遗传算法 算法复杂性，P，NP问题，NPC 1000000$FinalSubmissionCountdownNetflix公司-成立于1997年的美国最大的DVD租赁商ContributedbyLesterMackeyOnlysixteenminutesremainedinthe$1millionNetflixPrizecompetitionwhenIhandedoverthefinalsetofpredictionstotheEnsembleteamcaptain.Themembersofournewlymintedteamhadbeenworkingfuriouslythroughthenight,hopingtoimproveuponourpreviousdaysscoreof.8554.Itwashardtobelievethatjusttwenty-fourhoursagowehadpassedthefour-teamcoalitionthathadoccupiedthefirstplacespotforthelast29days.Therewaslittletimetocelebrate;thepreviousleaderswouldnotgodownwithoutafight,sowehadtobereadywithsomethingbetter.Acallhadbeenissuedforanyremainingvalidpredictors,anythingthatcouldtipthescaleinthisfinalday,andourmembersaroundtheglobehadansweredthecall:nearly200newpredictorsets,somepreviouslypassedoverfortheirpoorperformanceandothersnewlyconceivedonlymomentsprior,hadfloodedinfromallcornersoftheteam.Itwasnowuptoourblenderstoworksomelast-minutemagic.数学建模十大算法 蒙特卡罗算法、数据插值拟合、参数估计、层次分析法、线性规划问题 图论算法、动态规划、回溯搜索、分治算法、分支定界等算法 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法CrystalBall蒙地卡罗仿真软件CrystalBall是MicrosoftExcel的增益工具，采用MonteCarol仿真功能协助您分析风险与不确定模型。

功能包含敏感度分析、相关性分析、tornado分析、精确控制及历史数据的分配模拟的意义当我们使用模拟这个字时，代表我们利用分析模型来仿真现实生活的系统过去仿真软件过于偏重复杂数学造成操作困难CrystalBall工作表风险分析结合工作表呈现方式与自动分析模拟，可以清楚的展现因为变量变异造成模型产出的各种情况如果没有增加仿真功能，那工作表充其量只是揭示单一结果与最一般化的情境工作表模拟最常用的方法就是蒙地卡罗法，他可随机产生变量在不同情况下的模型结果蒙地卡罗模拟蒙地卡罗模拟是由学者蒙地卡罗所提出，一开始主要运作于分析赌博游戏诸如轮盘、骰子、拉吧等蒙地卡罗可以模拟这些赌博中的随机行为当你掷骰子时，你知道共有一至六的数字可能会出现，但是你不知道一个规则他就像企业主面对问题时，可能知道问题引发的结果与过程，却无法了解每一个变量的严重程度例如：利率、员工、股价、存货及来电率）模拟退火算法 模拟退火算法与物理退火过程的相似关系 目标函数能量 控制参数的下降冷却 Metropolis采样过程等温过程 设定初温熔解过程 最优解能量最低GA的计算过程编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。

初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成一个群体GA以这N个串结构数据作为初始点开始迭代适应性值评估检测：适应性函数表明个体或解的优劣性不同的问题，适应性函数的定义方式也不同选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大选择实现了达尔文的适者生存原则交换：交换操作是遗传算法中最主要的遗传操作通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性交换体现了信息交换的思想变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间变异为新个体的产生提供了机会优化算法及其分类 枚举法 确定性算法 数学规划算法，单纯形法，分支定界法 随机算法 自然方法，模拟退火法，禁忌搜索法（1）Steiner最小树选址，运输通讯斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。

如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树斯坦纳比猜想平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 任意一个斯坦纳点是三条两两夹角为120度的线段的交点斯坦纳（Steiner）最小生成树 力学模拟方法Steinertree 心脏-人体是空间steiner 2009CornellsIthacacampus：1991mcmb-通讯网络的极小生成树两个通讯站间通讯线路的费用与线路的长度成正比通过引入若干个“虚设站”并构造一个新的Steiner树就可以降低由一组站生成Nf自统的极小生成树所需的费用用这种方法可降低费用多达而且为构造一个有n个站的网络的费用最低的Steiner树绝不需要多于(n-2)个虚设站下面是两个简单的例子对于局部网络而言，有必要用直折线距离或“棋盘”距离来代替欧氏直线距离假定你希望设计一个有9个站的局部网络的最低造价生成树这9个站的直角坐标是：限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整数)每条直线段的造价是其长度值求该网络的一个极小费用树假定每个站的费用为，其中d通讯站助度，若w=1.2，求极小费用树试推广本问题。

2）距离优化线性规划问题图论离散优化 物流配送车辆问题 旅行商问题 最小生成树问题 线性规划问题 八皇后问题 背包问题 整数规划问题实际问题-数学建模伦敦地铁拓扑地图2007HiMCMSmokeAlarms2007HiMCM不同数量烟雾报警器 烟雾报警器数量烟雾报警器数量- -费用增长变化费用增长变化 最优解的确定标准：最优解的确定标准： 烟雾报警器数量烟雾报警器数量- -报警距离缓慢变化报警距离缓慢变化 离散形成模型离散形成模型- -不同房间计算求解不同房间计算求解 1999年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞车水马龙停滞在州际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线正常时轻松的两个小时驱车路要用上18个小时才能开到头许多车竟然沿途把汽油消耗净尽幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现AMCM2001B-逃避飓风怒吼应急管理与应急系统选址、调度与算法TaiwanTyphoonMorakot2008全国研究生数学建模A堰塞湖泄洪问题 城市-节点，撤离起始点和结束点 公路边长，网络最大流问题模型分析步骤 1SouthCarolina地理图，公路数据 2SouthCarolina沿海地区分布，人口数据 3高速公路前，汽车POSSION排队模型 4高速公路上，车辆GREENSHIELD模型 5SouthCarolina区域分块，逃离时间分段 6总逃离时间=排队时间+行走时间 7区域分块和时间分段的优化 8安置问题=不同区域和不同时间指派模型 9优化目标：时间费用最小，公路流量约束1994全国数学建模竞赛山区修建公路山区修建公路 要在一山区修建公路要在一山区修建公路, , 首先测得一些地点的高程首先测得一些地点的高程, , 数据见表数据见表1(1(平面区域平面区域0 0 x5600,0y4800,x5600,0y4800,表中数据为坐标点的高程表中数据为坐标点的高程, , 单位单位: :米米).).数据显示数据显示: :在在 y=3200 y=3200 处有一东西走向的山峰处有一东西走向的山峰; ; 从坐标从坐标 (2400,2400) (2400,2400) 到到 (4800,0) (4800,0) 有一西北有一西北 - - 东南走向的山谷东南走向的山谷; ; 在在 (2000,2800) (2000,2800) 附近有一山口湖附近有一山口湖, , 其最高水位略高于其最高水位略高于 1350 1350 米米, , 雨雨季在山谷中形成一溪流季在山谷中形成一溪流. . 经调查知经调查知, , 雨量最大时溪流水面宽度雨量最大时溪流水面宽度 w w 与与( (溪流最深处溪流最深处) ) 的的 x x 坐标的关系可近似表示为坐标的关系可近似表示为 w(x)=(x-2400 3/4 )/2 ) + 5 (2400 x4000).w(x)=(x-2400 3/4 )/2 ) + 5 (2400 x4000). 公路从山脚公路从山脚 (0,800) (0,800) 处开始处开始, , 经居民点经居民点 (4000,2000) (4000,2000) 至矿区至矿区 (2000,4000). (2000,4000). 已知路已知路段工程成本及对路段坡度段工程成本及对路段坡度 (。