数学建模中的创新案例课件

,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学建模中的创新案例,2011年7月,1,数学建模中的创新案例2011年7月1,创造性是灵魂，文章要有闪光点。,好创意、好想法应当既在人意料之外，又在人,意料之中。,新颖性（独特性）与合理性皆备。,数学建模中的创新性,2,数学建模中的创新性2,误区之一：,数学用得越高深，越有创造性,。,解决问题是第一原则，最合适的方法是最好的方法。,误区之二：,创造性主要体现在建模与求解上。,创造性可以体现在建模的各个环节上，并且可以有多种表现形式。,3,误区之一：数学用得越高深，越有创造性。3,误区之三：,好创意来自于灵感，可遇不可求,。,好创意来自于对数学方法的掌握程度与对问题理解的透彻程度。,4,误区之三：好创意来自于灵感，可遇不可求。4,在高空中一个边长为160公里的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据。当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞。如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：,案例一：飞行管理问题（95A）,5,在高空中一个边长为160公里的正方形区域内，经常,不碰撞的标准为任意两架飞机的距离大于8公里；,每架飞机飞行方向角调整的幅度不应超过30度；,所有飞机飞行速度均为800公里/小时；,欲进入飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上；,最多需考虑6架飞机；,不必考虑飞机离开此区域后的状况。,请你建立数学模型，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。（数据略）,6,不碰撞的标准为任意两架飞机的距离大于8公里；6,模型建立与求解,模型一：设第,i,架飞机在调整时的 方向角为,i,调整角度为,i,（,i,1，2，,，6）,。设任意两架飞机在区域内的最短距离为,d,ij,(,i,j,),，那么问题的非线性规划模型为,7,模型建立与求解7,解法：能量梯度法、惩罚函数法、序列无约束最小 化方法、逐步逼近搜索法等,模型二：,模型三：,8,解法：能量梯度法、惩罚函数法、序列无约束最小 化方,利用相对运动的方法得到以上模型，再简化为线性规划问题求解。,启示：转换角度看问题，也会带来创新点。,9,9,关键是计算速度与计算精度的平衡问题。牛顿迭代法有很高的精度，但速度较慢；线性近似法速度很快，可以满足实时要求，但精度稍差。,“Rabbit,Turtle and Hunter”,抓住了问题的主要方面速度。,启示：创造性体现在对问题的理解程度上，,进而体现在建模思路上。,案例二：螺旋线交点问题（95mcmA）,10,案例二：螺旋线交点问题（95mcmA）10,案例三：110警车配置及巡逻方案,（研究生09D）,11,案例三：110警车配置及巡逻方案 11,某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：,D1.,警车在接警后三分钟内赶到现场的比例不低于 90；而赶到重点部位的时间必须在两分钟之内。,D2.,使巡逻效果更显著；,D3.,警车巡逻规律应有一定的隐蔽性。,12,某城市拟增加一批配备有GPS卫星定位系统及先进通,请回答以下问题：,一.若要求满足D1,该区最少需要配置多少辆警车巡逻？,二.请给出评价巡逻效果显著程度的有关指标。,三,请给出满足D1且尽量满足D2条件的警车巡逻方案及 其评价指标值。,四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。,五 如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？,六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。,七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。,13,请回答以下问题：13,第三问,本问的主要技术难点在于要求二十几辆车在“动态巡逻”条件下保持“分布均匀性”，求最优解的计算复杂度太高，因此，寻找可接受的计算复杂度与结果的优化之间的平衡点，是本问的关键所在。本问的求解充分体现了建模方法的多样性，为参赛者充分发挥创造性提供了很好的机会。主要解题方法概述如下：,14,解题思路第三问,第三问 本问的主要技术难点在于要求二,1）,单车分区法,：按照覆盖率要求作区域划分，每个区域固定一辆警车巡逻。此方法主要特点是计算简单，但是其代价是需要车辆数较多。例如静态时17辆车即能满足覆盖率要求，如果分成17个区域，每个区域1辆车，则在动态时要保持满足覆盖率要求就非常困难了，所以不得不增加划分区域。此种方法通常要求配置3辆车以上，才能达到覆盖率要求。,15,解题思路第三问,1）单车分区法：按照覆盖率要求作区域划分，每个区域固,2）,多车分区法,：为了改进以上单车分区法的缺点，可以考虑每个区域设置若干辆警车共同巡逻的方法，这样可以减少一些车辆，但代价是计算难度的增加，且每一区域配置的车辆越多，计算难度就越大。,16,解题思路第三问,2）多车分区法：为了改进以上单车分区法的缺点，可以考虑,3）,动静结合法,：有的参赛队单纯从满足车辆数最少的目标出发，让有的车静止不动，这样即能满足覆盖率要求，车辆数又少。但这样做，见警率指标就很差了，于是就再安排一些车跑见警率。从覆盖率与见警率效果来看，此方法很不错，车辆数还不多（大约或辆），计算也相对简单，似乎是一种好方法。但是这样做，违背了问题本身的实际意义，所以未能得到评委们的认可。数学建模不是解数学题，一定要考虑问题的实际意义是什么，不能为了追求指标的好看而罔顾其实际背景。,17,解题思路-第三问,3）动静结合法：有的参赛队单纯从满足车辆数最少的目标出,4）,软分区法,：此方法由方法）延伸而来。与方法）一样，本方法先划分区域，每个区域配置一辆警车，与方法）不同的是，每个区域配置的警车并不是一定不能跨区域巡逻，而是设置了一个跨区域因子，此因子随着周围区域警车的位置以及其本身的位置关系而变化。再设置一个区域中心引力因子，以保证该车不会离开自己的区域中心太远。此方法的思想有创意，但在实现时由于各个因子之间较难平衡，所以效果改进不大。,18,解题思路第三问,4）软分区法：此方法由方法）延伸而来。与方法）一样,5）,蚁群算法,：此方法属于启发式搜索算法，在此次竞赛中成为主流解法，其思想是：在道路上设置一个“气味因子”，某段道路上跑过的车越多，则该段道路的“气味”变大，并且“气味”随时间变长而衰减。巡逻车每到一个路口，根据路口其它各段道路的“气味”大小，朝“气味”最小的方向前进。想法蛮有创意，在具体实现时还要处理好多辆车的协同问题等细节。如果细节处理得好，此方法所需要的车辆数大约为辆左右，不失为一种比较理想的方案。,19,解题思路第三问,5）蚁群算法：此方法属于启发式搜索算法，在此次竞赛中成,6）,引力场方法,：此方法与上一方法有类似之处，即每段道路依据走过的警车多少有一个“引力因子”，走过的车辆越多，则“引力”越小；同时，任两辆车之间依据距离远近有一个“斥力因子”，距离越近，则斥力越大。对每一辆警车而言，道路对它的“引力”与其它车辆对它的的“斥力”共同构成了一个“引力场”，它将向着“合成引力”最大的方向前进。这也是一种挺有创意的想法，难处在于细节的处理（例如引力与斥力的合成）及计算上的复杂性，对计算能力有较高的要求。,20,解题思路第三问,6）引力场方法：此方法与上一方法有类似之处，即每段道路,7）,切片叠加法,：由于静态时车辆数较少，并且车辆可以达到“均匀分布”状态，因此一种想法是对时间进行“切片”处理：每一时刻为一个切片，在一个切片上给出所有车辆的一个“均匀分布”，构造出充分多（例如：张）的不同切片，并且通过筛选使这些切片上的车辆分布点尽量分散，这是出于提高切片“叠加”后的车辆到达率指标的考虑。然后对这些切片按照“择近”原则进行排序，再对排序后的切片依次叠加，便得到一个班次（小时或小时）的巡逻方案。,21,解题思路第三问,7）切片叠加法：由于静态时车辆数较少，并且车辆可以达,这个方案的特点是车辆在巡逻时的速度可以不同，但每辆车的平均速度仍为公里/小时，其难点在于对切片的“择近”排序的计算量很大。这是一种很有创意的方法，效果也不错。大约需要辆车，可以使覆盖率及到达率指标都比较令人满意。可惜此种解法在本次竞赛论文中未发现使用。,启示：通往罗马的道路不止一条，但有些需 要实力的支撑。,22,解题思路第三问,这个方案的特点是车辆在巡逻时的速度可以不同，但每辆车的平均速,案例四：锁具装箱（94B）,某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6这6个数中任取一数。由于工艺及其它原因，制造锁具时对5个槽的高度还有两个限制：至少有3个不同的数；相邻两槽的高度之差不能为5。满足以上条件的所有互不相同的锁具称为一批。,从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”。但是在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其他情况下，不可能互开。,23,案例四：锁具装箱（94B）某厂生产一种弹子,原来，销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱，他们抱怨购得的锁具会出现互开的情形。现聘你为顾问，回答并解决以下的问题：,（1）每一批锁具有多少个，装多少箱。,（2）为销售部门提出一种方案，包括如何装箱，如何给箱子以标志，出售时如何利用这些标志，使团体顾客不再或减少抱怨。,（3）采取你的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形。,（4）按照原来的装箱办法，如何定量地衡量团体顾客抱怨互开的程度（试对购买一、二箱者给出具体结果）。,24,原来，销售部门在一批锁,将锁具按照槽高之和H为奇数与偶数分为两大类，每一类装49箱。最优性证明。,随机销售方式与序贯销售方式。,抱怨程度的度量。,三个创新点：,25,三个创新点：25,论文一（电子科大）,一、问题的重述与分析,每个锁具的钥匙有5个槽，令,h,i,为第,i,个槽的高度，用,记一个锁具，则一批锁具应满足如下条件：,条件1,条件2,中至少有三个数不相同；,条件3,满足以下条件的两个锁具,可以互开，并把这两个锁具称为一个,互开对,：,（*）,26,论文一（电子科大）一、问题的重述与分析 每个锁具的钥,我们所关心的问题是：每一批锁具共有多少个，如何衡量随,机装箱造成的团体顾客的抱怨程度以及采取何种方案装箱来尽量,避免团体顾客的抱怨。,二、模型假设,1、钥匙的每个槽的高度在生产过程中能够严格控制；,2、满足条件（*）的两个锁具一定能够互开。,三、模型建立与求解,1、确定一批锁具的总数,一批锁具的总数为,7776-（6+450+456+792+192）=5880 个,装箱总数为 5880/60=98 箱,27,我们所关心的问题是：每一批锁具共有多少个，如,2、装箱方案,设槽高之和为,H,，则,是互开对,设,是一个锁具，则,也是一个锁具，并且,锁具，故所有锁具分为两部分：奇类与偶类，且数量相等，各占,一半。,奇偶性恰好相反，称为对偶,分奇、偶类分别装箱，一批锁具中奇偶各装49箱，作上标记，,则只要团体顾客购买不超过49箱，就可以保证不会出现互开现象。,28,2、装箱方案 设槽高之和为H，则 是互开对 设 是一个锁具，,3、方案最优性的证明,用计算机对互开对数进行穷举计算得到在一批锁具中互开对总数为22778对。,用顶点表示锁具，用边表示可互开，得到图,其中,记,V,1,=奇类锁具，,V,2,=偶类锁具，则,G,0,是,一个二分图，,记作,要证明49箱是最优结果，等价于证明图,G,0,的最大点无关集含,2990点，或等价于证明图,G,0,存在完美匹配