《中山大学数学建模讲座.ppt》由会员分享，可在线阅读，更多相关《中山大学数学建模讲座.ppt（35页珍藏版）》请在三一文库上搜索。
1、优化模型-数学建模,华南理工大学理学院数学系 刘深泉教授,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 cal
2、culate 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 programming Semidefinite programming Stochastic
3、 programming. Robust programming Combinatorial optimization. Infinite-dimensional optimization Heuristic algorithms Constraint satisfaction Optimal control. Dynamic programming. Mathematical programming 序数理论，选择理论,一般最优化问题,最优化问题的约束数学模型,Computational optimization techniques,Single variables Optimizatio
4、n Multi variables Optimization 优化算法 1. Dijkstra 算法，2.最小生成树 Prim 算法，3. 最小费用，4. 遗传算法 算法复杂性，P，NP问题，NPC 1000000$,Final Submission Countdown Netflix公司-成立于1997年的美国最大的在线DVD租赁商 Contributed by Lester Mackey Only sixteen minutes remained in the $1 million Netflix Prize competition when I handed over the final
5、 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 that had occupied
6、 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 final day, and our
7、 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 magic.,数学建模十大算法,蒙特
8、卡罗算法、数据插值拟合、参数估计、层次分析法、线性规划问题 图论算法、动态规划、回溯搜索、分治算法、分支定界等算法 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法,Crystal Ball 蒙地卡罗仿真软件,Crystal Ball 是Microsoft Excel的增益工具，采用Monte Carol仿真功能协助您分析风险与不确定模型。功能包含敏感度分析、相关性分析、tornado分析、精确控制及历史数据的分配。 模拟的意义 当我们使用模拟这个字时， 代表我们利用分析模型来仿真现实生活的系统。过去仿真软件过于偏重复杂数学造成操作困难。Crystal Ball工作表风险分析结合工作
9、表呈现方式与自动分析模拟，可以清楚的展现因为变量变异造成模型产出的各种情况。如果没有增加仿真功能，那工作表充其量只是揭示单一结果与最一般化的情境。工作表模拟最常用的方法就是蒙地卡罗法， 他可随机产生变量在不同情况下的模型结果。 蒙地卡罗模拟 蒙地卡罗模拟是由学者蒙地卡罗所提出，一开始主要运作于分析赌博游戏。诸如轮盘、骰子、拉吧等。蒙地卡罗可以模拟这些赌博中的随机行为。当你掷骰子时，你知道共有一至六的数字可能会出现，但是你不知道一个规则。他就像企业主面对问题时，可能知道问题引发的结果与过程，却无法了解每一个变量的严重程度。（例如：利率、员工、股价、存货及来电率）,模拟退火算法,模拟退火算法与物理
10、退火过程的相似关系 目标函数能量 控制参数的下降冷却 Metropolis采样过程等温过程 设定初温熔解过程 最优解能量最低,GA的计算过程 编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。 初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。 适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过
11、程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。,优化算法及其分类, 枚举法 确定性算法 数学规划算法，单纯形法，分支定界法 随机算法 自然方法，模拟退火法，禁忌搜索法,（1）Steiner最小
12、树 选址，运输通讯,斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。 斯坦纳比猜想 平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 。 任意一个斯坦纳点是三条两两夹角为120度的线段的交点 斯坦纳（Steiner）最小生成树 力学模拟方法,Steiner tree,心脏-人体是空间steiner 2009 Cornells Ithaca campus：,1991mcmb-通讯网络的极小生成树,两个通讯站间通讯线路的费用与线路的长度成正比。通过引入若
13、干个“虚设站”并构造一个新的Steiner树就可以降低由一组站生成Nf自统的极小生成树所需的费用。用这种方法可降低费用多达 。而且为构造一个有n个站的网络的费用最低的Steiner树绝不需要多于(n-2)个虚设站。下面是两个简单的例子。 对于局部网络而言，有必要用直折线距离或“棋盘”距离来代替欧氏直线距离。 假定你希望设计一个有9个站的局部网络的最低造价生成树。这9个站的直角坐标是： 限定你只能用直线，而且所有的虚设站必须位于格点上(即其坐标是整数)。每条直线段的造价是其长度值。 求该网络的一个极小费用树。 假定每个站的费用为 ，其中d通讯站助度，若w=1.2，求极小费用树。 试推广本问题。,
14、（2）距离优化线性规划问题,图论离散优化 物流配送车辆问题 旅行商问题 最小生成树 问题 线性规划问题 八皇后问题 背包问题 整数规划问题,实际问题-数学建模 伦敦地铁拓扑地图,2007HiMCM Smoke Alarms,2007HiMCM不同数量烟雾报警器,烟雾报警器数量-费用增长变化 最优解的确定标准： 烟雾报警器数量-报警距离缓慢变化 离散形成模型-不同房间计算求解。,1999年，在Floyd飓风预报登陆之前，撤离南卡罗来纳州沿海地区的行动导致一场永垂青史的交通拥塞。车水马龙停滞在州际公路I-26上，那是内陆上从Charleston通往该州中心Columbia相对安全处所的主要干线。正
15、常时轻松的两个小时驱车路要用上18个小时才能开到头。许多车竟然沿途把汽油消耗净尽。幸运的是，Floyd飓风掉头长驱北上，这次放过了南卡罗来纳州，但是，公众的喧嚷正在迫使该州官员们寻找各种办法，以避免这场交通恶梦再度出现。,AMCM2001B - 逃避飓风怒吼,应急管理与应急系统 选址、调度与算法,Taiwan Typhoon Morakot,2008全国研究生数学建模A 堰塞湖泄洪问题,城市 - 节点，撤离起始点和结束点 公路 边长，网络最大流问题,模型分析步骤,1 South Carolina地理图，公路数据 2 South Carolina沿海地区分布，人口数据 3 高速公路前，汽车POS
16、SION排队模型 4 高速公路上，车辆GREENSHIELD模型 5 South Carolina区域分块，逃离时间分段 6 总逃离时间=排队时间+行走时间 7 区域分块和时间分段的优化 8 安置问题=不同区域和不同时间指派模型 9 优化目标：时间费用最小，公路流量约束,1994全国数学建模竞赛山区修建公路,要在一山区修建公路, 首先测得一些地点的高程, 数据见表1(平面区域0 x5600,0y4800,表中数据为坐标点的高程, 单位:米).数据显示: 在 y=3200 处有一东西走向的山峰; 从坐标 (2400,2400) 到 (4800,0) 有一西北 - 东南走向的山谷; 在 (2000
17、,2800) 附近有一山口湖, 其最高水位略高于 1350 米, 雨季在山谷中形成一溪流. 经调查知, 雨量最大时溪流水面宽度 w 与(溪流最深处) 的 x 坐标的关系可近似表示为 w(x)=(x-2400 3/4 )/2 ) + 5 (2400x4000). 公路从山脚 (0,800) 处开始, 经居民点 (4000,2000) 至矿区 (2000,4000). 已知路段工程成本及对路段坡度 (上升高程与水平距离之比) 的限制如表 2. 1) 试给出一种线路设计方案, 包括原理、方法及比较精确的线路位置(含桥梁、隧道), 并估算该方案的总成本. 2) 如果居民点改为3600x4000, 20
18、00y2400的居民区, 公路只须经过居民区即可, 那么你的方案有什么改变.,表一 北 山区地点的高程 _ 48001350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 15 44001370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 21 40001380 1410 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370 35 36001420 1430 1450 1480 1500 1550 1
19、510 1430 1300 1200 980 850 750 550 50 32001430 1450 1460 1500 1550 1600 1550 1600 1600 1600 1550 1500 1500 1550 155 2800 950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 120 2400 910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 110 2000 880 1060 1230 1390 1500 1
20、500 1400 900 1100 1060 950 870 900 930 95 1600 830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780 75 1200 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 780 720 650 500 200
21、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米); 3000(长度 300米); 对坡度的限制 0.125= 0 0.100,(1) 对地图网格加密，形成图。 (2) 计算网格的距离，用费用作为权值。 (3) 求赋权图两点间的最短距离。 参考答案：最速下降应用,优化模型与数学建模竞赛,2007icmC 器官移植-肾脏交换问题 美国1984年通过国家器官移植法，建立采购和器官移植网 2007研究生D题邮局邮件运输问题拷贝 1990mcm城市扫雪问题中国邮递员问题 1998灾情巡视路线美国旅行商问题 1994 山区矿山道路最速下降应用 2000钢管订购和运输 2007 mcm Gerrymandering,典型案例分析,2000B 钢管订购和运输,多谢,