中山大学数学建模讲座-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 calcula

2、te any 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 progr

3、amming. Robust programming. Combinatorial optimization. Infinite-dimensional optimization Heuristic algorithms Constraint satisfactionOptimal control. Dynamic programming. Mathematical programming序数理论，选择理论一般最优化问题最优化问题的约束数学模型 Computational optimization techniques Single variables OptimizationMulti va

4、riables Optimization优化算法 1. Dijkstra 算法，2.最小生成树 Prim 算法，3. 最小费用，4. 遗传算法 算法复杂性，P，NP问题，NPC1000000$ Final Submission Countdown Netflix公司-成立于2019年的美国最大的在线DVD租赁商 Contributed by Lester MackeyOnly sixteen minutes remained in the $1 million Netflix Prize competition when I handed over the final set of predi

5、ctions 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-team coalition that had occupied the first pl

6、ace 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 in this final day, and our members arou

7、nd 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-minute magic.数学建模十大算法蒙特卡罗算法、数据插值拟合、参数估

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

9、变异造成模型产出的各种情况。如果没有增加仿真功能，那工作表充其量只是揭示单一结果与最一般化的情境。工作表模拟最常用的方法就是蒙地卡罗法，他可随机产生变量在不同情况下的模型结果。 蒙地卡罗模拟 蒙地卡罗模拟是由学者蒙地卡罗所提出，一开始主要运作于分析赌博游戏。诸如轮盘、骰子、拉吧等。蒙地卡罗可以模拟这些赌博中的随机行为。当你掷骰子时，你知道共有一至六的数字可能会出现，但是你不知道一个规则。他就像企业主面对问题时，可能知道问题引发的结果与过程，却无法了解每一个变量的严重程度。（例如：利率、员工、股价、存货及来电率） 模拟退火算法模拟退火算法与物理退火过程的相似关系目标函数能量控制参数的下降冷却Me

10、tropolis采样过程等温过程设定初温熔解过程最优解能量最低GA的计算过程编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代

11、的概率大。选择实现了达尔文的适者生存原则。交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。优化算法及其分类 枚举法 确定性算法 数学规划算法，单纯形法，分支定界法 随机算法 自然方法，模拟退火法，禁忌搜索法（1）Steiner最小树选址，运输通讯斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(

12、称为斯坦纳点)，然后将所有这些点连起来。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。斯坦纳比猜想平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 。任意一个斯坦纳点是三条两两夹角为120度的线段的交点斯坦纳（Steiner）最小生成树力学模拟方法Steiner tree心脏-人体是空间steiner2009 Cornells Ithaca campus：1991mcmb-通讯网络的极小生成树两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个“虚设站”并构造一个新的Steiner树就可以降低由一组站生成Nf自统的极小生成树所需的费用。用这种方法

13、可降低费用多达 。而且为构造一个有n个站的网络的费用最低的Steiner树绝不需要多于(n-2)个虚设站。下面是两个简单的例子。对于局部网络而言，有必要用直折线距离或“棋盘”距离来代替欧氏直线距离。假定你希望设计一个有9个站的局部网络的最低造价生成树。这9个站的直角坐标是： 限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整数)。每条直线段的造价是其长度值。 求该网络的一个极小费用树。 假定每个站的费用为 ，其中d通讯站助度，若w=1.2，求极小费用树。 试推广本问题。（2）距离优化线性规划问题图论离散优化物流配送车辆问题 旅行商问题 最小生成树 问题线性规划问题八皇后问题 背包问

14、题 整数规划问题实际问题-数学建模伦敦地铁拓扑地图2019HiMCM Smoke Alarms2019HiMCM不同数量烟雾报警器烟雾报警器数量-费用增长变化最优解的确定标准：烟雾报警器数量-报警距离缓慢变化离散形成模型-不同房间计算求解。2019年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞。车水马龙停滞在州际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线。正常时轻松的两个小时驱车路要用上18个小时才能开到头。许多车竟然沿途把汽油消耗净尽。幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳

15、州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现。 AMCM2019B -逃避飓风怒吼应急管理与应急系统选址、调度与算法Taiwan Typhoon Morakot2019全国研究生数学建模A堰塞湖泄洪问题 城市 - 节点，撤离起始点和结束点公路 边长，网络最大流问题模型分析步骤1 South Carolina地理图，公路数据2 South Carolina沿海地区分布，人口数据3 高速公路前，汽车POSSION排队模型4 高速公路上，车辆GREENSHIELD模型5 South Carolina区域分块，逃离时间分段6 总逃离时间=排队时间+行走时间7 区域分块

16、和时间分段的优化8 安置问题=不同区域和不同时间指派模型9 优化目标：时间费用最小，公路流量约束1994全国数学建模竞赛山区修建公路要在一山区修建公路, 首先测得一些地点的高程, 数据见表1(平面区域0 x5600,0y4800,表中数据为坐标点的高程, 单位:米).数据显示:在 y=3200 处有一东西走向的山峰; 从坐标 (2400,2400) 到 (4800,0) 有一西北 - 东南走向的山谷; 在 (2000,2800) 附近有一山口湖, 其最高水位略高于 1350 米, 雨季在山谷中形成一溪流. 经调查知, 雨量最大时溪流水面宽度 w 与(溪流最深处) 的 x 坐标的关系可近似表示为

17、w(x)=(x-2400 3/4 )/2 ) + 5 (2400 x4000).公路从山脚 (0,800) 处开始, 经居民点 (4000,2000) 至矿区 (2000,4000). 已知路段工程成本及对路段坡度 (上升高程与水平距离之比) 的限制如表 2. 1) 试给出一种线路设计方案, 包括原理、方法及比较精确的线路位置(含桥梁、隧道), 并估算该方案的总成本. 2) 如果居民点改为3600 x4000, 2000y2400的居民区, 公路只须经过居民区即可, 那么你的方案有什么改变.表一 北 山区地点的高程 _48001350 1370 1390 1400 1410 960 940 8

18、80 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 1430 1450 1480 1500 1550 1510 1430 1300 1200 980 850 750 550 5032001430 1450 1460 1500 1550 1600 1550 1600 1600 1600 1550

19、 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 880 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 55800 650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 35400 510 620 730 800 850 870 850 780 720 650 500 200 300 350 32 0 730 470 550 600