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