数学建模中的创新案例市公开课一等奖百校联赛特等奖课件.pptx

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