中山大学数学建模讲座-PPT课件.ppt

1、优化模型-数学建模华南理工大学理学院数学系刘深泉教授Experimental Mathematics Computer Formula for PiIn 2019,a PSLQ program discovered this formula for pi:Indeed,this formula permits one to directly calculate binary or hexadecimal(base-16)digits of beginning at an arbitrary starting position n,without needing to calculate any

2、 of the first n-1 digits.Srinivasa Ramanujan Optimization-mathematical programming choosing the best element from some set of available alternatives Linear programming Integer programming.Quadratic programming Nonlinear programming.Convex programmingSemidefinite programming Stochastic programming.Ro

3、bust programming.Combinatorial optimization.Infinite-dimensional optimization Heuristic algorithms Constraint satisfactionOptimal control.Dynamic programming.Mathematical programming序数理论，选择理论一般最优化问题 最优化问题的约束数学模型 nxxxfyMax,:210,:211nxxxsSt0,212nxxxs0,21nmxxxsComputational optimization techniques Sing

4、le variables Optimization Multi variables Optimization 优化算法 1.Dijkstra 算法，2.最小生成树 Prim 算法，3.最小费用，4.遗传算法 算法复杂性，P，NP问题，NPC 1000000$Final Submission Countdown Netflix公司公司-成立于成立于2019年的美国最大的在线年的美国最大的在线DVD租赁商租赁商 Contributed by Lester MackeyOnly sixteen minutes remained in the$1 million Netflix Prize compe

5、tition when I handed over the final set of predictions to the Ensemble team captain.The members of our newly minted team had been working furiously through the night,hoping to improve upon our previous days score of.8554.It was hard to believe that just twenty-four hours ago we had passed the four-t

6、eam coalition that had occupied the first place spot for the last 29 days.There was little time to celebrate;the previous leaders would not go down without a fight,so we had to be ready with something better.A call had been issued for any remaining valid predictors,anything that could tip the scale

7、in this final day,and our members around the globe had answered the call:nearly 200 new predictor sets,some previously passed over for their poor performance and others newly conceived only moments prior,had flooded in from all corners of the team.It was now up to our blenders to work some last-minu

8、te magic.数学建模十大算法 蒙特卡罗算法、数据插值拟合、参数估计、层次分析法、线性规划问题 图论算法、动态规划、回溯搜索、分治算法、分支定界等算法 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法Crystal Ball 蒙地卡罗仿真软件蒙地卡罗仿真软件 Crystal Ball 是Microsoft Excel的增益工具，采用Monte Carol仿真功能协助您分析风险与不确定模型。功能包含敏感度分析、相关性分析、tornado分析、精确控制及历史数据的分配。模拟的意义 当我们使用模拟这个字时，代表我们利用分析模型来仿真现实生活的系统。过去仿真软件过于偏重复杂数学造成操作困

9、难。Crystal Ball工作表风险分析结合工作表呈现方式与自动分析模拟，可以清楚的展现因为变量变异造成模型产出的各种情况。如果没有增加仿真功能，那工作表充其量只是揭示单一结果与最一般化的情境。工作表模拟最常用的方法就是蒙地卡罗法，他可随机产生变量在不同情况下的模型结果。蒙地卡罗模拟 蒙地卡罗模拟是由学者蒙地卡罗所提出，一开始主要运作于分析赌博游戏。诸如轮盘、骰子、拉吧等。蒙地卡罗可以模拟这些赌博中的随机行为。当你掷骰子时，你知道共有一至六的数字可能会出现，但是你不知道一个规则。他就像企业主面对问题时，可能知道问题引发的结果与过程，却无法了解每一个变量的严重程度。（例如：利率、员工、股价、存

10、货及来电率）模拟退火算法 模拟退火算法与物理退火过程的相似关系 目标函数能量 控制参数的下降冷却 Metropolis采样过程等温过程 设定初温熔解过程 最优解能量最低GA的计算过程编码编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择选择：选择的目的是为了从当前群体中选出优良的个体，

11、使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。交换交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。优化算法及其分类 枚举法 确定性算法 数学规划算法，单纯形法，分支定界法 随机算法 自

12、然方法，模拟退火法，禁忌搜索法（1）Steiner最小树最小树选址，运输通讯选址，运输通讯斯坦纳（斯坦纳（SteinerSteiner）最小树是可以在给定的点之外再增加若干个点）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳称为斯坦纳点点)，然后将所有这些点连起来。，然后将所有这些点连起来。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。斯坦纳比猜想平面上任意斯坦纳比猜想平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值点集，斯坦纳最小树长与最小生成树之长的比值的最小值是的最小值是 。任意一个

13、斯坦纳点是三条两两夹角为任意一个斯坦纳点是三条两两夹角为120120度的线段的交点度的线段的交点斯坦纳（斯坦纳（SteinerSteiner）最小生成树）最小生成树力学模拟方法23Steiner tree 心脏-人体是空间steiner 2009 Cornells Ithaca campus：1991mcmb-通讯网络的极小生成树通讯网络的极小生成树两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个“虚设站虚设站”并构造一个新的并构造一个新的Steiner树就可以降低由一组站生成树就可以降低由一组站生成Nf自自统的极小生成树

14、所需的费用。用这种方法可降低费用多达统的极小生成树所需的费用。用这种方法可降低费用多达。而且为。而且为构造一个有构造一个有n个站的网络的费用最低的个站的网络的费用最低的Steiner树绝不需要多于树绝不需要多于(n-2)个个虚设站。下面是两个简单的例子。虚设站。下面是两个简单的例子。对于局部网络而言，有必要用直折线距离或对于局部网络而言，有必要用直折线距离或“棋盘棋盘”距离来代替欧氏距离来代替欧氏直线距离。直线距离。假定你希望设计一个有假定你希望设计一个有9个站个站的局部网络的最低造价生成树。这的局部网络的最低造价生成树。这9个站个站的直角坐标是：的直角坐标是：限定你只能用直线，而且所有的虚设

15、站必须位于格点上限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是即其坐标是整数整数)。每条直线段的造价是其长度值。每条直线段的造价是其长度值。求该网络的一个极小费用树。求该网络的一个极小费用树。假定每个站的费用为假定每个站的费用为，其中，其中d通讯站助度，若通讯站助度，若w=1.2，求极小费，求极小费用树。用树。试推广本问题。试推广本问题。（2）距离优化距离优化线性规划问题图论离散优化图论离散优化 物流配送车辆问题物流配送车辆问题 旅行商问题旅行商问题 最小生成树最小生成树 问题问题 线性规划问题线性规划问题 八皇后问题八皇后问题 背包问题背包问题 整数规划问题整数规划问题实际问题

16、实际问题-数学建模数学建模伦敦地铁拓扑地图伦敦地铁拓扑地图2019HiMCM Smoke Alarms2019HiMCM不同数量烟雾报警器不同数量烟雾报警器。2019年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞。车水马龙停滞在州际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线。正常时轻松的两个小时驱车路要用上18个小时才能开到头。许多车竟然沿途把汽油消耗净尽。幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现。A

17、MCM2019B-逃避飓风怒吼应急管理与应急系统应急管理与应急系统选址、调度与算法选址、调度与算法Taiwan Typhoon Morakot2019全国研究生数学建模全国研究生数学建模A堰塞湖泄洪问题堰塞湖泄洪问题 城市-节点，撤离起始点和结束点 公路 边长，网络最大流问题模型分析步骤 1 South Carolina地理图，公路数据 2 South Carolina沿海地区分布，人口数据 3 高速公路前，汽车POSSION排队模型 4 高速公路上，车辆GREENSHIELD模型 5 South Carolina区域分块，逃离时间分段 6 总逃离时间=排队时间+行走时间 7 区域分块和时间分

18、段的优化 8 安置问题=不同区域和不同时间指派模型 9 优化目标：时间费用最小，公路流量约束19941994全国数学建模竞赛全国数学建模竞赛表一 北 山区地点的高程 _48001350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 1544001370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 2140001380 1410 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370 3536001420

19、 1430 1450 1480 1500 1550 1510 1430 1300 1200 980 850 750 550 5032001430 1450 1460 1500 1550 1600 1550 1600 1600 1600 1550 1500 1500 1550 1552800 950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 1202400 910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 1102000 88

20、0 1060 1230 1390 1500 1500 1400 900 1100 1060 950 870 900 930 951600 830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780 751200 740 880 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650 55 800 650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 35 400 510 620 730 800 850 870 850

21、 780 720 650 500 200 300 350 32 0 730 470 550 600 670 690 670 620 580 450 400 300 100 150 25_ y/x 0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 5200 560-表表 二二 工程种类工程种类 一般路段一般路段 桥梁桥梁 隧隧 道道_ _ _ _ 工程成本工程成本(元元/米米)300 2000 1500()300 2000 1500(长度长度300300米米);3000();3000(长度长度 300 300米米););对坡度

22、对坡度的限制的限制 0.125=0 0.100 (1)(1)对地图网格加密，形成图。对地图网格加密，形成图。(2)(2)计算网格的距离，用费用作为权值。计算网格的距离，用费用作为权值。(3)(3)求赋权图两点间的最短距离。求赋权图两点间的最短距离。参考答案：参考答案：最速下降应用最速下降应用优化模型与数学建模竞赛 2019icmC 器官移植-肾脏交换问题 美国1984年通过国家器官移植法，建立采购和器官移植网 2019研究生D题邮局邮件运输问题拷贝 1990mcm城市扫雪问题中国邮递员问题城市扫雪问题中国邮递员问题 2019灾情巡视路线美国旅行商问题灾情巡视路线美国旅行商问题 1994 山区矿山道路山区矿山道路最速下降应用最速下降应用 2000钢管订购和运输钢管订购和运输 2019 mcm Gerrymandering典型案例分析2000B 钢管订购和运输A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7多谢多谢