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