中山大学数学建模讲座课件

优化模型-数学建模华南理工大学理学院数学系刘深泉教授ExperimentalMathematicsComputerFormulaforPiIn2019,aPSLQprogramdiscoveredthisformulaforpi:Indeed,thisformulapermitsonetodirectlycalculatebinaryorhexadecimal(base-16)digitsofbeginningatanarbitrarystartingpositionn,withoutneedingtocalculateanyofthefirstn-1digits.SrinivasaRamanujanOptimization-mathematicalprogrammingchoosingthebestelementfromsomesetofavailablealternativesLinearprogrammingIntegerprogramming.QuadraticprogrammingNonlinearprogramming.ConvexprogrammingSemidefiniteprogrammingStochasticprogramming.Robustprogramming.Combinatorialoptimization.Infinite-dimensionaloptimizationHeuristicalgorithmsConstraintsatisfactionOptimalcontrol.Dynamicprogramming.Mathematicalprogramming序数理论，选择理论一般最优化问题最优化问题的约束数学模型ComputationaloptimizationtechniquesSinglevariablesOptimizationMultivariablesOptimization优化算法1.Dijkstra算法，2.最小生成树Prim算法，3.最小费用，4.遗传算法算法复杂性，P，NP问题，NPC1000000$FinalSubmissionCountdownNetflix公司公司-成立于成立于2019年的美国最大的在线年的美国最大的在线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最小树最小树选址，运输通讯选址，运输通讯斯坦纳（斯坦纳（SteinerSteiner）最小树是可以在给定的点之外再增加若干个点）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳称为斯坦纳点点)，然后将所有这些点连起来。，然后将所有这些点连起来。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。斯坦纳比猜想平面上任意斯坦纳比猜想平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的点集，斯坦纳最小树长与最小生成树之长的比值的最小值是最小值是 。任意一个斯坦纳点是三条两两夹角为任意一个斯坦纳点是三条两两夹角为120120度的线段的交点度的线段的交点斯坦纳（斯坦纳（SteinerSteiner）最小生成树）最小生成树力学模拟方法Steinertree心脏-人体是空间steiner2009CornellsIthacacampus：1991mcmb-通讯网络的极小生成树通讯网络的极小生成树两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个“虚设站虚设站”并构造一个新的并构造一个新的Steiner树就可以降低由一组站生成树就可以降低由一组站生成Nf自统自统的极小生成树所需的费用。用这种方法可降低费用多达的极小生成树所需的费用。用这种方法可降低费用多达。而且为构造。而且为构造一个有一个有n个站的网络的费用最低的个站的网络的费用最低的Steiner树绝不需要多于树绝不需要多于(n-2)个虚设个虚设站。下面是两个简单的例子。站。下面是两个简单的例子。对于局部网络而言，有必要用直折线距离或对于局部网络而言，有必要用直折线距离或“棋盘棋盘”距离来代替欧氏直距离来代替欧氏直线距离。线距离。假定你希望设计一个有假定你希望设计一个有9个站个站的局部网络的最低造价生成树。这的局部网络的最低造价生成树。这9个站个站的直角坐标是：的直角坐标是：限定你只能用直线，而且所有的虚设站必须位于格点上限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整即其坐标是整数数)。每条直线段的造价是其长度值。每条直线段的造价是其长度值。求该网络的一个极小费用树。求该网络的一个极小费用树。假定每个站的费用为假定每个站的费用为，其中，其中d通讯站助度，若通讯站助度，若w=1.2，求极小费，求极小费用树。用树。试推广本问题。试推广本问题。（2）距离优化距离优化线性规划问题图论离散优化图论离散优化物流配送车辆问题物流配送车辆问题旅行商问题旅行商问题最小生成树最小生成树问题问题线性规划问题线性规划问题八皇后问题八皇后问题背包问题背包问题整数规划问题整数规划问题实际问题实际问题-数学建模数学建模伦敦地铁拓扑地图伦敦地铁拓扑地图2019HiMCMSmokeAlarms2019HiMCM不同数量烟雾报警器不同数量烟雾报警器烟雾报警器数量-费用增长变化最优解的确定标准：烟雾报警器数量-报警距离缓慢变化离散形成模型-不同房间计算求解。2019年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞。车水马龙停滞在州际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线。正常时轻松的两个小时驱车路要用上18个小时才能开到头。许多车竟然沿途把汽油消耗净尽。幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现。AMCM2019B-逃避飓风怒吼应急管理与应急系统应急管理与应急系统选址、调度与算法选址、调度与算法TaiwanTyphoonMorakot2019全国研究生数学建模全国研究生数学建模A堰塞湖泄洪问题堰塞湖泄洪问题城市-节点，撤离起始点和结束点公路边长，网络最大流问题模型分析步骤1SouthCarolina地理图，公路数据2SouthCarolina沿海地区分布，人口数据3高速公路前，汽车POSSION排队模型4高速公路上，车辆GREENSHIELD模型5SouthCarolina区域分块，逃离时间分段6总逃离时间=排队时间+行走时间7区域分块和时间分段的优化8安置问题=不同区域和不同时间指派模型9优化目标：时间费用最小，公路流量约束19941994全国数学建模竞赛全国数学建模竞赛山区修建公路山区修建公路山区修建公路山区修建公路 要在一山区修建公路要在一山区修建公路要在一山区修建公路要在一山区修建公路,首先测得一些地点的高程首先测得一些地点的高程首先测得一些地点的高程首先测得一些地点的高程,数据见表数据见表数据见表数据见表1(1(1(1(平面区域平面区域平面区域平面区域0 0 0 0 x5600,0y4800,x5600,0y4800,x5600,0y4800,x5600,0y4800,表中数据为坐标点的高程表中数据为坐标点的高程表中数据为坐标点的高程表中数据为坐标点的高程,单位单位单位单位:米米米米).).).).数据显示数据显示数据显示数据显示:在在在在 y=3200 y=3200 y=3200 y=3200 处有一东西走向的山峰处有一东西走向的山峰处有一东西走向的山峰处有一东西走向的山峰;从坐标从坐标从坐标从坐标(2400,2400)(2400,2400)(2400,2400)(2400,2400)到到到到(4800,0)(4800,0)(4800,0)(4800,0)有一西北有一西北有一西北有一西北-东南走向的山谷东南走向的山谷东南走向的山谷东南走向的山谷;在在在在(2000,2800)(2000,2800)(2000,2800)(2000,2800)附近有一山口湖附近有一山口湖附近有一山口湖附近有一山口湖,其最高水位略高于其最高水位略高于其最高水位略高于其最高水位略高于 1350 1350 1350 1350 米米米米,雨雨雨雨季在山谷中形成一溪流季在山谷中形成一溪流季在山谷中形成一溪流季在山谷中形成一溪流.经调查知经调查知经调查知经调查知,雨量最大时溪流水面宽度雨量最大时溪流水面宽度雨量最大时溪流水面宽度雨量最大时溪流水面宽度 w w w w 与与与与(溪流最深处溪流最深处溪流最深处溪流最深处)的的的的 x x x x 坐标的关系可近似表示为坐标的关系可近似表示为坐标的关系可近似表示为坐标的关系可近似表示为 w(x)=(x-2400 3/4)/2)+5(2400 x4000).w(x)=(x-2400 3/4)/2)+5(2400 x4000).w(x)=(x-2400 3/4)/2)+5(2400 x4000).w(x)=(x-2400 3/4)/2)+5(2400 x4000).公路从山脚公路从山脚公路从山脚公路从山脚(0,800)(0,800)(0,800)(0,800)处开始处开始处开始处开始,经居民点经居民点经居民点经居民点(4000,2000)(4000,2000)(4000,2000)(4000,2000)至矿区至矿区至矿区至矿区(2000,4000).(2000,4000).(2000,4000).(2000,4000).已知路已知路已知路已知路段工程成本及对路段坡度段工程成本及对路段坡度段工程成本及对路段坡度段工程成本及对路段坡度(上升高程与水平距离之比上升高程与水平距离之比上升高程与水平距离之比上升高程与水平距离之比)的限制如表的限制如表的限制如表的限制如表 2.2.2.2.1)1)1)1)试给出一种线路设计方案试给出一种线路设计方案试给出一种线路设计方案试给出一种线路设计方案,包括原理、方法及比较精确的线路位置包括原理、方法及比较精确的线路位置包括原理、方法及比较精确的线路位置包括原理、方法及比较精确的线路位置(含桥梁、隧含桥梁、隧含桥梁、隧含桥梁、隧道道道道),),),),并估算该方案的总成本并估算该方案的总成本并估算该方案的总成本并估算该方案的总成本.2)2)2)2)如果居民点改为如果居民点改为如果居民点改为如果居民点改为3600 x4000,2000y24003600 x4000,2000y24003600 x4000,2000y24003600 x4000,2000y2400的居民区的居民区的居民区的居民区,公路只须经过居民区公路只须经过居民区公路只须经过居民区公路只须经过居民区即可即可即可即可,那么你的方案有什么改变那么你的方案有什么改变那么你的方案有什么改变那么你的方案有什么改变.表一北 山区地点的高程_4800135013701390140014109609408808006905704302902101544001370139014101430144011401110105095082069054038030021400013801410143014501470132012801200108094078062046037035360014201430145014801500155015101430130012009808507505505032001430145014601500155016001550160016001600155015001500155015528009501190137015001200110015501600155013801070900105011501202400910109012701500120011001350145012001150101088010001050110200088010601230139015001500140090011001060950870900930951600830980118013201450142014001300700900850840380780751200740880108011301250128012301040900500700780750650558006507608809701020105010208308007003005005504803540051062073080085087085078072065050020030035032073047055060067069067062058045040030010015025_y/x040080012001600200024002800320036004000440048005200560-表表 二二 工程种类工程种类 一般路段一般路段 桥梁桥梁 隧隧 道道_ _ _ _ 工程成本工程成本(元元/米米)300 2000 1500()300 2000 1500(长度长度300300米米);3000();3000(长度长度 300 300米米););对坡度对坡度的限制的限制0.125=00.100(1)(1)对地图网格加密，形成图。对地图网格加密，形成图。(2)(2)计算网格的距离，用费用作为权值。计算网格的距离，用费用作为权值。(3)(3)求赋权图两点间的最短距离。求赋权图两点间的最短距离。参考答案：参考答案：最速下降应用最速下降应用优化模型与数学建模竞赛2019icmC器官移植-肾脏交换问题美国1984年通过国家器官移植法，建立采购和器官移植网2019研究生D题邮局邮件运输问题拷贝1990mcm城市扫雪问题中国邮递员问题城市扫雪问题中国邮递员问题2019灾情巡视路线美国旅行商问题灾情巡视路线美国旅行商问题1994山区矿山道路山区矿山道路最速下降应用最速下降应用2000钢管订购和运输钢管订购和运输2019mcmGerrymandering典型案例分析2000B钢管订购和运输A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7多谢多谢谢谢！