吴孟达教授-数学建模中的创新案例

数学建模中的创新案例国防科技大学吴孟达2012年7月13日2好创意、好想法应当既在意料之外，又在情理之中。新颖性（独特性）与合理性皆备。数学建模中的创新性3误区之一：数学用得越高深，越有创造性。解决问题是第一原则，最合适的方法是最好的方法。误区之二：创造性主要体现在建模与求解上。创造性可以体现在建模的各个环节上，并且可以有多种表现形式。4误区之三：好创意来自于灵感，可遇不可求。好创意来自于对数学方法的掌握程度与对问题理解的透彻程度。从实际出发往往是创新的源泉。5在高空中一个边长为160公里的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据。当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞。如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：案例一：飞行管理问题（95－A）6不碰撞的标准为任意两架飞机的距离大于8公里；每架飞机飞行方向角调整的幅度不应超过30度；所有飞机飞行速度均为800公里/小时；欲进入飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上；最多需考虑6架飞机；不必考虑飞机离开此区域后的状况。请你建立数学模型，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。（数据略）7模型建立与求解模型一：设第i架飞机在调整时的方向角为θi,调整角度为Δθi（i＝1，2，…，6）。设任意两架飞机在区域内的最短距离为dij(θi,θj)，那么问题的非线性规划模型为61minii..(,)8ijiijjstdij30oi8解法：能量梯度法、惩罚函数法、序列无约束最小化方法、逐步逼近搜索法等模型二：模型三：16minmaxii9利用相对运动的方法得到以上模型，再简化为线性规划问题求解。启示：转换角度看问题，也会带来创新点。minZ..,2ijijijijijsti030i0003010案例二：眼科病床的合理安排（09－B）某医院眼科门诊住院部共有病床79张。该医院眼科手术主要分四大类：白内障、视网膜疾病、青光眼和外伤。周一、三做白内障手术，双眼的话，周一做一只，周三做另一只。外伤通常属于急症，入院第二天安排手术，其他病人一般不安排在周一、三做手术。现在医院按照先到先服务的方式安排入院顺序，导致等待入院的病人越来越多，排队时间越来越长。11问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系作出评价。……对等待病人的优先级排序是关键。常见的做法是公平性指标与病床使用效率指标两方面综合排序，然后按排序结果安排当日入院病人，由此得到公平合理的住院方案。一种具体做法如下：12列出每天入院的病人在手术前的无效等待时间如表：13周一周二周三周四周五周六周日白内障１０４３２１０白内障双眼６５４３２１０青光眼１００００１０视网膜疾病１００００１０利用公式y＝（10－x）/10，将上表中的数值x转化为排序的效率优先值y，列表如下:周一周二周三周四周五周六周日白内障0.910.60.70.80.91白内障双眼0.40.50.60.70.80.91青光眼0.911110.91视网膜疾病0.911110.91公平指标值具体计算方法如下：当前队列中最早到门诊的病人权值为1，接下来每晚到一天，权值减0.1。综合考虑以上两级指标，排序公式定义为：排序值=λ×效率指标值+（1－λ）×公平指标值排序值高的将排在队列前面。1415引入处理器调度中的最高响应比优先（HRRN）调度策略。这是现代计算机操作系统中常用的调度算法,它是一种非常优秀的调度算法。在（HRRN）策略中，每个进程的优先级不仅取决于它的服务时间，还要取决于它花在等待服务上的时间，即动态优先级的计算公式为等待时间服务时间优先级服务时间由于服务时间做分母，所以较短的进程将被优先照顾；又由于等待时间在分子中出现，所以等待时间较长的进程也会得到合理的对待，从而防止了无限延期的情况出现。效率与公平兼顾启示：他山之石，可以攻玉。16案例三：锁具装箱（94－B）某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6这6个数中任取一数。由于工艺及其它原因，制造锁具时对5个槽的高度还有两个限制：至少有3个不同的数；相邻两槽的高度之差不能为5。满足以上条件的所有互不相同的锁具称为一批。从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”。但是在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其他情况下，不可能互开。17原来，销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱，他们抱怨购得的锁具会出现互开的情形。现聘你为顾问，回答并解决以下的问题：（1）每一批锁具有多少个，装多少箱。（2）为销售部门提出一种方案，包括如何装箱，如何给箱子以标志，出售时如何利用这些标志，使团体顾客不再或减少抱怨。（3）采取你的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形。（4）按照原来的装箱办法，如何定量地衡量团体顾客抱怨互开的程度（试对购买一、二箱者给出具体结果）。18①将锁具按照槽高之和H为奇数与偶数分为两大类，每一类装49箱。最优性证明。②随机销售方式与序贯销售方式。③抱怨程度的度量。三个创新点：19论文一（电子科大）一、问题的重述与分析每个锁具的钥匙有5个槽，令hi为第i个槽的高度，用12345(,,,,)hhhhh记一个锁具，则一批锁具应满足如下条件：条件11,2,3,4,5,6;ih条件212345,,,,hhhhh中至少有三个数不相同；条件314,2,3,4,5iihhi满足以下条件的两个锁具1234512345(,,,,)(',',',',')hhhhhhhhhh与可以互开，并把这两个锁具称为一个互开对：521(')1iiihh（*）20我们所关心的问题是：每一批锁具共有多少个，如何衡量随机装箱造成的团体顾客的抱怨程度以及采取何种方案装箱来尽量避免团体顾客的抱怨。二、模型假设1、钥匙的每个槽的高度在生产过程中能够严格控制；2、满足条件（*）的两个锁具一定能够互开。三、模型建立与求解1、确定一批锁具的总数一批锁具的总数为7776-（6+450+456+792+192）=5880个装箱总数为5880/60=98箱212、装箱方案设槽高之和为H，则1234512345(,,,,)(',',',',')hhhhhhhhhh与是互开对'1HH设12345(,,,,)hhhhh是一个锁具，则12345(7,7,7,7,7)hhhhh也是一个锁具，并且ih(7)ih与锁具，故所有锁具分为两部分：奇类与偶类，且数量相等，各占一半。奇偶性恰好相反，称为对偶分奇、偶类分别装箱，一批锁具中奇偶各装49箱，作上标记，则只要团体顾客购买不超过49箱，就可以保证不会出现互开现象。223、方案最优性的证明用计算机对互开对数进行穷举计算得到在一批锁具中互开对总数为22778对。用顶点表示锁具，用边表示可互开，得到图0(,)GVE，其中588022778VE，记V1=奇类锁具，V2=偶类锁具，则G0是一个二分图，记作012(,,).GVVE要证明49箱是最优结果，等价于证明图G0的最大点无关集含2990点，或等价于证明图G0存在完美匹配。引理1二分图12(,,)GVVE含有覆盖V1的每个顶点的匹配的充要条件是对任意01VV有00()1GNVV（）定理二分图012(,,)GVVE的V1，V2是它的两个最大点无关集。23[证]由奇类锁具与偶类锁具的对称性可知012(,,)GVVE满足（1），即G0中含有覆盖V1中每个顶点的匹配M，显然M也覆盖了V2中的每个顶点，于是M是完美匹配，亦即G0的最大点无关集包含点数不可能超过2980，所以我们的销售方案是最优的。[评注]证明有误，例如右图.结论是正确的，已有计算机证明.但尚未见到理论证明。4.定量分析顾客抱怨互开的程度(1)对于随机装箱的方案互开对总数为m=22778对，平均每个锁具与其它锁具能组成的互开对数为7.752940mE对。24随机装箱时，某一个指定的锁具与箱中的其余59个组成互开对的平均数为1597.750.0785879E（个）一箱中平均互开对数为1160()2.332EEm（对）同理可知：k箱锁具中，能与某一个指定锁具互开的锁具个数平均为6015879kkEE（个）于是k箱中平均含有的互开对数为6022778()(601)2587998kkkEEmkk25显然，E(mk)越大，顾客抱怨程度越大。k1249E(mk)2.339.415693.5（2）对于奇偶分类装箱的方案当购买量不超过49箱时，不会抱怨。当购买量超过49箱时，先从奇类中取出49箱，再从偶类中任取出k-49箱出售，平均互开对数为2277849'()60(49)22778294049kkEmk（对）故奇偶分类装箱后团体顾客的抱怨程度减少了。模型评价：（1）分析出色，结构完整、严谨，较圆满地解决题；（2）转化为图论问题，转化出色，但最优性证明有误；（3）销售方案不大符合实际；（4）抱怨程度的分析不够深入。26论文二（兰州铁道学院）较实际的一种销售方案：序贯销售。装箱分奇偶两类，按槽高H及字典序从小到大装箱。H＝8：（11123）（11132）（11213）（11231）（11321）……H＝9：（11124）（11142）（11214）（11223）……这样，每一个锁具在一批锁具中的位置是唯一确定的。计算任一锁具的最小可互开距离，再对所有最小距离求极小值，得到计算结果为：2562.2563/60=42.7故序贯销售时团体顾客最大购买量为42箱时不会出现互开现象。启示：从实际背景出发，深入一步思考，寻找创新点。27论文三（合肥工大）顾客的抱怨程度一方面取决于购买的总数量，另一方面取决于检验的结果，并且从心理学的角度考虑，顾客更偏重于检验结果。检验方法：从购买的T箱中取出t箱，再从这t箱中每箱各取m把，对取出的tm把锁具作完全互开试验。定义抱怨函数为：21(,)nKnKCTeT其中，K1：表示购买箱数在整个抱怨程度中所占的比重；K2：表示检验结果在整个抱怨程度中所占的比重；δn：顾客检验到有n次互开的比率2100%ntmnC28对购买一箱，m＝10的情形进行具体分析。210100%nnC如果为确定参数K1，K2，认为：122,TT(1)(2),nn则(1)(2)122(,)(,)nnCTCT所以11K当互开率达到2106215C时，抱怨达到极值，设为100.所以215ln1002K所以，15ln10021(,)nnCTeT29以下就购买1、2箱情形作具体分析。用计算机进行1000次模拟检验，得互开次数统计结果为：互开次数n0123456≥7概率Pn（%）13.726.928.617.98.72.90.90购买一、二箱的平均互开率为（每箱抽样10把）：6110.04nnnP6210.01nnnP故购买一、二箱的平均抱怨程度分别为：1(1,)3.98C2(2,)0.71C即购买一箱的团体顾客抱怨程度更大。启示：从实际出发，察人所未察，见人所未见。30论文四（中国科大）抱怨程度与互开的锁具对数x，能够被其它锁具打开的锁具个数y以及必须报废的锁具的最小数目α有关。例如，有两对互开，可以有两种情形：它们分别对应x＝2，y＝4以及x＝2，y＝3.另外，在一箱锁