《中山大学数学建模讲座演示课件》由会员分享，可在线阅读，更多相关《中山大学数学建模讲座演示课件（35页珍藏版）》请在金锄头文库上搜索。
1、1,优化模型-数学建模,华南理工大学理学院数学系 刘深泉教授,2,Experimental Mathematics Computer Formula for Pi,In 1996, 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
2、 calculate any of the first n-1 digits.,Srinivasa Ramanujan,3,Optimization- mathematical programming choosing the best element from some set of available alternatives,Linear programming Integer programming. Quadratic programming Nonlinear programming. Convex programming Semidefinite programming Stoc
3、hastic programming. Robust programming. Combinatorial optimization. Infinite-dimensional optimization Heuristic algorithms Constraint satisfaction Optimal control. Dynamic programming. Mathematical programming 序数理论，选择理论,4,一般最优化问题,最优化问题的约束数学模型,5,Computational optimization techniques,Single variables
4、Optimization Multi variables Optimization 优化算法 1. Dijkstra 算法，2.最小生成树 Prim 算法，3. 最小费用，4. 遗传算法 算法复杂性，P，NP问题，NPC 1000000$,6,7,Final Submission Countdown Netflix公司-成立于1997年的美国最大的在线DVD租赁商 Contributed by Lester Mackey Only sixteen minutes remained in the $1 million Netflix Prize competition when I handed
5、 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-team coalition th
6、at 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 in this fin
7、al 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-minute mag
8、ic.,8,数学建模十大算法,蒙特卡罗算法、数据插值拟合、参数估计、层次分析法、线性规划问题 图论算法、动态规划、回溯搜索、分治算法、分支定界等算法 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法,9,Crystal Ball 蒙地卡罗仿真软件,CrystalBall是MicrosoftExcel的增益工具，采用MonteCarol仿真功能协助您分析风险与不确定模型。功能包含敏感度分析、相关性分析、tornado分析、精确控制及历史数据的分配。 模拟的意义 当我们使用模拟这个字时，代表我们利用分析模型来仿真现实生活的系统。过去仿真软件过于偏重复杂数学造成操作困难。CrystalBa
9、ll工作表风险分析结合工作表呈现方式与自动分析模拟，可以清楚的展现因为变量变异造成模型产出的各种情况。如果没有增加仿真功能，那工作表充其量只是揭示单一结果与最一般化的情境。工作表模拟最常用的方法就是蒙地卡罗法，他可随机产生变量在不同情况下的模型结果。 蒙地卡罗模拟 蒙地卡罗模拟是由学者蒙地卡罗所提出，一开始主要运作于分析赌博游戏。诸如轮盘、骰子、拉吧等。蒙地卡罗可以模拟这些赌博中的随机行为。当你掷骰子时，你知道共有一至六的数字可能会出现，但是你不知道一个规则。他就像企业主面对问题时，可能知道问题引发的结果与过程，却无法了解每一个变量的严重程度。（例如：利率、员工、股价、存货及来电率）,10,模
10、拟退火算法,模拟退火算法与物理退火过程的相似关系 目标函数能量 控制参数的下降冷却 Metropolis采样过程等温过程 设定初温熔解过程 最优解能量最低,11,GA的计算过程 编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。 初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。 适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代
11、为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。,12,优化算法及其分类, 枚举法 确定性算法 数学规划算法，单纯形法，分支定界法 随机算法 自然方法，模拟退
12、火法，禁忌搜索法,13,14,15,（1）Steiner最小树选址，运输通讯,斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。 斯坦纳比猜想平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 。 任意一个斯坦纳点是三条两两夹角为120度的线段的交点 斯坦纳（Steiner）最小生成树 力学模拟方法,16,Steiner tree,心脏-人体是空间steiner 2009 Cornells Ithaca campus：,17,1991mcmb-通讯网络的
13、极小生成树,两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若干个“虚设站”并构造一个新的Steiner树就可以降低由一组站生成Nf自统的极小生成树所需的费用。用这种方法可降低费用多达 。而且为构造一个有n个站的网络的费用最低的Steiner树绝不需要多于(n-2)个虚设站。下面是两个简单的例子。 对于局部网络而言，有必要用直折线距离或“棋盘”距离来代替欧氏直线距离。 假定你希望设计一个有9个站的局部网络的最低造价生成树。这9个站的直角坐标是： 限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整数)。每条直线段的造价是其长度值。 求该网络的一个极小费用树。 假定每个站的费用为
14、 ，其中d通讯站助度，若w=1.2，求极小费用树。 试推广本问题。,18,（2）距离优化线性规划问题,图论离散优化 物流配送车辆问题 旅行商问题 最小生成树 问题 线性规划问题 八皇后问题 背包问题 整数规划问题,实际问题-数学建模 伦敦地铁拓扑地图,19,2007HiMCM Smoke Alarms,20,21,22,2007HiMCM不同数量烟雾报警器,烟雾报警器数量-费用增长变化 最优解的确定标准： 烟雾报警器数量-报警距离缓慢变化 离散形成模型-不同房间计算求解。,23,1999年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞。车水马龙停滞在州
15、际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线。正常时轻松的两个小时驱车路要用上18个小时才能开到头。许多车竟然沿途把汽油消耗净尽。幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现。,AMCM2001B -逃避飓风怒吼,24,应急管理与应急系统选址、调度与算法,25,Taiwan Typhoon Morakot,2008全国研究生数学建模A 堰塞湖泄洪问题,26,城市 - 节点，撤离起始点和结束点 公路 边长，网络最大流问题,27,模型分析步骤,1 So
16、uth Carolina地理图，公路数据 2 South Carolina沿海地区分布，人口数据 3 高速公路前，汽车POSSION排队模型 4 高速公路上，车辆GREENSHIELD模型 5 South Carolina区域分块，逃离时间分段 6 总逃离时间=排队时间+行走时间 7 区域分块和时间分段的优化 8 安置问题=不同区域和不同时间指派模型 9 优化目标：时间费用最小，公路流量约束,28,29,1994全国数学建模竞赛山区修建公路,要在一山区修建公路, 首先测得一些地点的高程, 数据见表1(平面区域0 x5600,0y4800,表中数据为坐标点的高程, 单位:米).数据显示:在 y=3200 处有一东西走向的山峰; 从坐标 (2400,2400) 到 (4800,0) 有一西北 - 东南走向的山谷; 在 (2000,2800) 附近有一山口湖, 其最高水位略高于 1350 米, 雨季在山谷中形成一溪流. 经调查知, 雨量最大时溪流水面宽度 w 与(溪流最深处) 的 x 坐标的关系可近似表示为 w(x)=(x-2400 3/4 )/2 ) + 5 (24
