1、61m inii.(,)8ijiijjstdij 30oi16minmaxii minZ.,2ijijijijijsti03 0i0003 0 某厂生产一种弹子锁具，每个锁具的钥匙有某厂生产一种弹子锁具，每个锁具的钥匙有5 5个槽，个槽，每个槽的高度从每个槽的高度从1 1，2 2，3 3，4 4，5 5，6 6这这6 6个数中任取一数。个数中任取一数。由于工艺及其它原因，制造锁具时对由于工艺及其它原因，制造锁具时对5 5个槽的高度还有两个槽的高度还有两个限制：至少有个限制：至少有3 3个不同的数；相邻两槽的高度之差不能个不同的数；相邻两槽的高度之差不能为为5 5。满足以上条件的所有互不相同的锁
2、具称为一批。满足以上条件的所有互不相同的锁具称为一批。从顾客的利益出发，自然希望在每批锁具中从顾客的利益出发，自然希望在每批锁具中“一把钥一把钥匙开一把锁匙开一把锁”。但是在当前工艺条件下，对于同一批中两。但是在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的个锁具是否能够互开，有以下试验结果：若二者相对应的5 5个槽的高度中有个槽的高度中有4 4个相同，另一个槽的高度差为个相同，另一个槽的高度差为1 1，则可，则可能互开；在其他情况下，不可能互开。能互开；在其他情况下，不可能互开。论文一（电子科大）论文一（电子科大）一、问题的重述与分析一、问题的重述与分析 每
3、个锁具的钥匙有每个锁具的钥匙有5 5个槽，令个槽，令hi为第为第i个槽的高度，用个槽的高度，用 12345(,)h h h h h记一个锁具，则一批锁具应满足如下条件：记一个锁具，则一批锁具应满足如下条件：条件条件1 1 1,2,3,4,5,6;ih 条件条件2 12345,h h h h h中至少有三个数不相同；中至少有三个数不相同；条件条件3 14,2,3,4,5iih hi满足以下条件的两个锁具满足以下条件的两个锁具 1234512345(,)(,)h hhhhhhhhh与可以互开，并把这两个锁具称为一个可以互开，并把这两个锁具称为一个互开对互开对：521()1iiihh（*）我们所关心
4、的问题是：每一批锁具共有多少个，如何衡量随我们所关心的问题是：每一批锁具共有多少个，如何衡量随机装箱造成的团体顾客的抱怨程度以及采取何种方案装箱来尽量机装箱造成的团体顾客的抱怨程度以及采取何种方案装箱来尽量避免团体顾客的抱怨。避免团体顾客的抱怨。二、模型假设二、模型假设1、钥匙的每个槽的高度在生产过程中能够严格控制；、钥匙的每个槽的高度在生产过程中能够严格控制；2、满足条件（、满足条件（*）的两个锁具一定能够互开。）的两个锁具一定能够互开。三、模型建立与求解三、模型建立与求解1、确定一批锁具的总数、确定一批锁具的总数 一批锁具的总数为一批锁具的总数为7776-（6+450+456+792+19
5、2）=5880 个个装箱总数为装箱总数为 5880/60=98 箱箱 2、装箱方案、装箱方案 设槽高之和为设槽高之和为H，则，则 1234512345(,)(,)h h h h hhhhhh与是互开对是互开对 1HH设设 12345(,)h h h h h是一个锁具，则是一个锁具，则 12345(7,7,7,7,7)hhhhh也是一个锁具，并且也是一个锁具，并且 ih(7)ih与锁具，故所有锁具分为两部分：奇类与偶类，且数量相等，各占锁具，故所有锁具分为两部分：奇类与偶类，且数量相等，各占一半。一半。奇偶性恰好相反，称为对偶奇偶性恰好相反，称为对偶 分奇、偶类分别装箱，一批锁具中奇偶各装分奇、
6、偶类分别装箱，一批锁具中奇偶各装49箱，作上标记，箱，作上标记，则只要团体顾客购买不超过则只要团体顾客购买不超过49箱，就可以保证不会出现互开现象。箱，就可以保证不会出现互开现象。3、方案最优性的证明、方案最优性的证明 用计算机对互开对数进行穷举计算得到在一批锁具中互开对用计算机对互开对数进行穷举计算得到在一批锁具中互开对总数为总数为22778对。对。用顶点表示锁具，用边表示可互开，得到图用顶点表示锁具，用边表示可互开，得到图 0(,)G V E，其中其中 588022778VE，记记 V1=奇类锁具，奇类锁具，V2=偶类锁具，则偶类锁具，则G0是是一个二分图，一个二分图，记作记作 012(,
7、).G V V E 要证明要证明49箱是最优结果，等价于证明图箱是最优结果，等价于证明图G0的最大点无关集含的最大点无关集含2990点，或等价于证明图点，或等价于证明图G0存在完美匹配。存在完美匹配。引理引理1 二分图二分图 12(,)G V V E含有覆盖含有覆盖V1的每个顶点的匹配的充要的每个顶点的匹配的充要条件是对任意条件是对任意 01VV有有 00()1GNVV（）定理定理 二分图二分图 012(,)G V VE的的V1，V2是它的两个最大点无关集。是它的两个最大点无关集。证证 由奇类锁具与偶类锁具的对称性可知由奇类锁具与偶类锁具的对称性可知 012(,)GV VE满足满足（1），即）
8、，即G0中含有覆盖中含有覆盖V1中每个顶点的匹配中每个顶点的匹配M，显然，显然M也覆盖了也覆盖了V2中的每个顶点，于是中的每个顶点，于是M是完美匹配，亦即是完美匹配，亦即G0的最大点无关集包的最大点无关集包含点数不可能超过含点数不可能超过2980，所以我们的销售方案是最优的。，所以我们的销售方案是最优的。评注评注 证明有误，例如右图证明有误，例如右图.结论是正确的，已有计算机证明结论是正确的，已有计算机证明.但尚未见到理论证明。但尚未见到理论证明。4.定量分析顾客抱怨互开的程度定量分析顾客抱怨互开的程度(1)对于随机装箱的方案对于随机装箱的方案 互开对总数为互开对总数为m=22778对，平均每
9、个锁具与其它锁具能组成对，平均每个锁具与其它锁具能组成的互开对数为的互开对数为 7.752940mE 对。对。随机装箱时，某一个指定的锁具与箱中的其余随机装箱时，某一个指定的锁具与箱中的其余59个组成互开个组成互开对的平均数为对的平均数为 1597.750.0785879E（个）（个）一箱中平均互开对数为一箱中平均互开对数为 1160()2.332EE m（对）（对）同理可知：同理可知：k箱锁具中，能与某一个指定锁具互开的锁具个数平均为箱锁具中，能与某一个指定锁具互开的锁具个数平均为 6015879kkEE（个）（个）于是于是k箱中平均含有的互开对数为箱中平均含有的互开对数为 6022778(
10、)(601)2587998kkkEE mkk显然，显然，E(mk)越大，顾客抱怨程度越大。越大，顾客抱怨程度越大。（2）对于奇偶分类装箱的方案对于奇偶分类装箱的方案当购买量不超过当购买量不超过49箱时，不会抱怨。箱时，不会抱怨。当购买量超过当购买量超过49箱时，先从奇类中取出箱时，先从奇类中取出49箱，再从偶类中箱，再从偶类中任取出任取出k-49箱出售，平均互开对数为箱出售，平均互开对数为 2277849()60(49)22778294049kkE mk（对）（对）故奇偶分类装箱后团体顾客的抱怨程度减少了。故奇偶分类装箱后团体顾客的抱怨程度减少了。模型评价：模型评价：（1）分析出色，结构完整、
11、严谨，较圆满地解决题；分析出色，结构完整、严谨，较圆满地解决题；（2）转化为图论问题，转化出色，但最优性证明有误；（）转化为图论问题，转化出色，但最优性证明有误；（3）销售）销售方案不大符合实际；（方案不大符合实际；（4）抱怨程度的分析不够深入。）抱怨程度的分析不够深入。论文二（兰州铁道学院）论文二（兰州铁道学院）较实际的一种销售方案：序贯销售。较实际的一种销售方案：序贯销售。装箱分奇偶两类，按槽高装箱分奇偶两类，按槽高H及字典序从小到大装箱。及字典序从小到大装箱。H8：（11123）（）（11132）（）（11213）（）（11231）（）（11321）H9：（11124）（）（11142）
12、（）（11214）（）（11223）这样，每一个锁具在一批锁具中的位置是唯一确定的。计算这样，每一个锁具在一批锁具中的位置是唯一确定的。计算任一锁具的最小可互开距离，再对所有最小距离求极小值，得到任一锁具的最小可互开距离，再对所有最小距离求极小值，得到计算结果为：计算结果为：2562.2563/60=42.7 故序贯销售时团体顾客最大购买量为故序贯销售时团体顾客最大购买量为42箱时不会出现互开现象。箱时不会出现互开现象。启示：从实际背景出发，深入一步思考，寻找创新点。启示：从实际背景出发，深入一步思考，寻找创新点。论文三（合肥工大）论文三（合肥工大）顾客的抱怨程度一方面取决于购买的总数量，另一
13、方面取决顾客的抱怨程度一方面取决于购买的总数量，另一方面取决于检验的结果，并且从心理学的角度考虑，顾客更偏重于检验结果。于检验的结果，并且从心理学的角度考虑，顾客更偏重于检验结果。检验方法：从购买的检验方法：从购买的T箱中取出箱中取出t箱，再从这箱，再从这t箱中每箱各取箱中每箱各取m把，把，对取出的对取出的tm把锁具作完全互开试验。把锁具作完全互开试验。定义抱怨函数为：定义抱怨函数为：21(,)nKnKC TeT其中，其中，K1：表示购买箱数在整个抱怨程度中所占的比重；表示购买箱数在整个抱怨程度中所占的比重；K2：表示检验结果在整个抱怨程度中所占的比重；表示检验结果在整个抱怨程度中所占的比重；
14、n：顾客检验到有顾客检验到有n次互开的比率次互开的比率21 0 0%ntmnC对购买一箱，对购买一箱，m10的情形进行具体分析的情形进行具体分析。210100%nnC如果如果 为确定参数为确定参数K1，K2，认为：，认为：122,TT(1)(2),nn则则(1)(2)122(,)(,)nnC TC T所以所以 11K 当互开率达到当互开率达到 2106215C时，抱怨达到极值，设为时，抱怨达到极值，设为100.所以所以 215ln1002K 所以，所以，15ln10021(,)nnC TeT以下就购买以下就购买1、2箱情形作具体分析。箱情形作具体分析。用计算机进行用计算机进行1000次模拟检验
15、，得互开次数统计结果为：次模拟检验，得互开次数统计结果为：互开次数互开次数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把）：把）：6110.04nnnP6210.01nnnP故购买一、二箱的平均抱怨程度分别为：故购买一、二箱的平均抱怨程度分别为：1(1,)3.98C2(2,)0.71C即购买一箱的团体顾客抱怨程度更大。即购买一箱的团体顾客抱怨程度更大。启示：从实际出发，察人所未察，见人所未见。启示：从实际出发，察人所未察，见人所未见。论文论文
16、4（中国科大）（中国科大）抱怨程度与互开的锁具对数抱怨程度与互开的锁具对数x，能够被其它锁具打开的锁具个，能够被其它锁具打开的锁具个数数y以及必须报废的锁具的最小数目以及必须报废的锁具的最小数目有关。例如，有两对互开，有关。例如，有两对互开，可以有两种情形：可以有两种情形：它们分别对应它们分别对应x2，y4以及以及x2，y3.另外，在一箱锁具中，出现一个锁具被至少三个其它锁具打另外，在一箱锁具中，出现一个锁具被至少三个其它锁具打开的概率开的概率p0充分小，证明如下：充分小，证明如下：设一个给定锁具被至少三个其它设一个给定锁具被至少三个其它锁具打开的概率为锁具打开的概率为p1，则，则 13587
17、959max:4100.0001587959kikkiipk 所以，所以，01600.006pp故故p0可以忽略，只考虑一箱中每一个锁具至多与两个锁具可以互可以忽略，只考虑一箱中每一个锁具至多与两个锁具可以互开的情形，定义抱怨函数为：开的情形，定义抱怨函数为：2xy则一箱：则一箱：(2)9.09Exy二箱：二箱：(2)36.19Exy启示：精巧，于细微处见功力。启示：精巧，于细微处见功力。问题一：试分析确定合理的评价指标体系，用以评价该问题的病问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。床安排模型的优劣。问题二：试就该住院部当前的情况，建立合理的病床安排模型，问题
18、二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系作出评价。人住院。并对你们的模型利用问题一中的指标体系作出评价。我们引入处理器调度中的我们引入处理器调度中的最高响应比优先（最高响应比优先（HRRN）调度策）调度策略略。这是现代计算机操作系统中常用的调度算法，它很好地提高了。这是现代计算机操作系统中常用的调度算法，它很好地提高了系统的运行效率，是一种非常优秀的调度算法。系统的运行效率，是一种非常优秀的调度算法。Brinch Hansen
19、开发的最高响应比优先（开发的最高响应比优先（HRRN）策略中，每个）策略中，每个进程的优先级不仅取决于它的服务时间，还要取决于它花在等待服进程的优先级不仅取决于它的服务时间，还要取决于它花在等待服务上的时间，即动态优先级的计算公式为务上的时间，即动态优先级的计算公式为 等待时间 服务时间优先级服务时间由于服务时间做分母，所以较短的进程将被优先照顾；又由于等由于服务时间做分母，所以较短的进程将被优先照顾；又由于等待时间在分子中出现，所以等待时间较长的进程也会得到合理的待时间在分子中出现，所以等待时间较长的进程也会得到合理的对待，从而防止了无限延期的情况出现。对待，从而防止了无限延期的情况出现。效率与公平兼顾效率与公平兼顾启示：他山之石，可以攻玉。启示：他山之石，可以攻玉。
