锁具互开.doc

锁具互开国防科技大学 电子科学与工程学院 向为 王瑛 伍微摘要：我们求出一批锁具的锁数后，依照奇偶锁、槽高总和以及字典排序的原则对锁具进行编号，并由此给出具体的装箱方案和销售方案。对于顾客抱怨度的衡量，我们考虑的是其数学期望，从顾客角度出发，给出了合理的模型。一 问题描述（略）二 锁具总数此问用排列组合、递推、图论、甚至遍历的方法都能做出。我们用计算机遍历，求得一批锁具总数为5880，可装5880/60=98箱。三 锁具装箱合理的装箱方案应该满足以下两个条件： 1每一箱内的锁具相互之间不能互开；2给98箱锁具加以适当的标志，使得销售商（或顾客）能方便的辨认出哪些箱放在一起出售，也不会出现互开情形。考虑条件2，一种自然的标志方案即为：将98箱锁具从198顺次编号，通过适当的装箱，使得销售商按编号从小到大的顺序依次销售（可循环，即按以下顺序卖：1,98, (下一批)1,98, (下一批)1,），且无论从哪一个编号开始卖，都可连续销售n箱（n有一个上界，我们会在实施阶段给出）。 准备阶段：基于以上分析，我们给出两个关键变量和两个关键名词的定义：每批锁具（5880把）都按某种标准排序，各批锁按此序排成一列，且前一批的批尾接后一批的批首；从第把锁开始，由前往后依次取锁，最多能取出把不互开的锁；：装箱后，每批锁具（98箱）都按某种标准排序，各批锁按此序排成一列，且前一批的批尾接后一批的批首；从第箱锁开始，由前往后依次取锁，最多能取出箱不互开的锁； 奇锁：一把锁的槽高总和若为奇数，则称其为奇锁；偶锁：一把锁的槽高总和若为偶数，则称其为偶锁。由计算机遍历可得：奇锁、偶锁各2940把。分析互开条件，易得以下结论： 结论1：槽高总和不相邻的两把锁一定不互开。 结论2：奇锁之间不互开，偶锁之间也不互开。 结论3：某槽高差大于或等于2的两把锁不互开。另外的一个重要结论是：2940为最大不互开锁集的上界，即顾客购买量超过49箱时，一定有互开。证明如下：定理：2m把锁中，若可找出m对互开锁（互不重复），则最大不互开锁数不大于m。此定理显然成立。要找出最大互开对数，涉及图论中二分图的最大匹配问题，可用匈牙利算法计算，但由于计算规模太大，可考虑另一种近似算法：设第i把锁能与n(i)把锁互开。Step1：在奇锁中找一把锁i，使得n(i)最小；Step2：在与锁i对应得偶锁中找一把锁j，使得n(j)最小； Step3：将锁i、j记录下来，并从锁集中去掉；重复Step1Step3，直至找出所有互不重复的互开锁对。在计算机上实现之，找出了2940对互不重复的互开对；结合上面的定理，可得2940为最大不互开锁集的上界。实施阶段：以准备阶段得到的结论为基础，按以下原则对锁具进行分组：原则1：奇锁、偶锁分开，按其槽高总和从小到大排序；原则2：一把锁的槽高序列构成一个五位数，称为该锁的权值。在原则1的前提下，按权值从小到大排序。（见表1）偶锁奇锁槽高总和81012141618202224269111315171921232527具体锁序11123，11132，66645，66654 表1按照已排好得具体锁序装箱，每60把锁装一箱。然后由计算机遍历可得及的具体关系，从而得出、的下限：（把）（箱）及的图示如下（图1、图2）： 图1 图2由此可提出销售方案如下（设顾客需求量为箱）： 当箱时，可从任意一箱开始依次提货，可保证所有锁具不互开； 当箱时，按如表2所示的顺序提货，可保证所有锁具不互开； 当箱时，无论如何提货，总有锁具互开，但按照下法提货可减小互开概率：从一批中取出所有奇锁（49箱），再从另一批中取出若干箱奇锁。 4948474646464545444444444444434343424343434343434342424242424243434343434343424343444444444445464649484747474646464646454444444444444444434343434343434344434343434343434344444444444444464646464747 表2四 顾客抱怨程度的衡量 我们将此问题定位为随机装箱情况下一般顾客的抱怨程度，即求其数学期望。模型建立： 设顾客买了n把锁，检查了k把锁，抱怨度为y，且设顾客有一定的承受能力。下面分析各因素对抱怨度y的影响：1 顾客在k把锁中发现的互开对数期望值为： （其中，p为互开率，可求出）显然，若增大，则y增大。2 若顾客购买的锁数n增加，其承受能力会增加，致使y增大。3 当顾客购买的锁数n增加时，其检查的锁数k不会相应增加，即随n的增大，k的增加趋势变小。分析如下：当n很大时，顾客不可能穷举找出所有的互开对，故可设k有一个上界u。由数学中已有函数及经验可定kn关系为： （、为常数） 综合上述因素，可得抱怨度的表示式如下： （、为待定系数）其中，分子项来源于对因素1、3的考虑，分母项来源于对因素2的考虑定性分析： 应用上述模型，对本问题进行定性分析如下：1 y（1）=0；2 n=6000并增大时，y趋近于0；3 y为不小于0的实数且有界；4 y有一个极大值。 由尝试及经验可得：当、时，结果较好（如图3）： 图3 由此模型可得： 购买一箱的抱怨度为：2.4804； 购