锁 具 装 箱-论文点评2

《锁 具 装 箱-论文点评2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、锁具装箱2（94—CMCM—B）某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6这六个数中任取一数（单位略）。由于工艺及其它原因，制造锁具时对5个槽的高度还有两个限制：至少有3个不同的数；相邻两槽的高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”。但是在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下试验结果：若两者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其它情形下，不可能互开。原来，

2、销售部门在一批锁具中随意地取60个装一箱出售。团体顾客往往购买几箱到几十箱，他们抱怨购得的锁具会出现互开的情形。现聘你为顾问，回答并解决以下的问题：1）每一批锁具有多少个，装多少箱。2）为销售部门提出一种方案，包括如何装箱（仍是60个锁具一箱），如何给箱子以标志，出售时如何利用这些标志，使团体顾客不再或减少抱怨。3）采取你提出的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形。4）按照原来的装箱办法，如何定量的衡量团体顾客抱怨互开的程度（试对购买一、二箱者给出具体结果）。论文一（电子科大）一、问题的重述与分析每个

3、锁具的钥匙有5个槽，令为第个槽的高度（.用记一个锁具，则一批锁具应满足如下条件：条件1条件2中至少有三个数不相同条件37满足以下条件的两个锁具与可以互开，并把这两个锁具称为一个互开对：（*）原销售方案为：从一批锁具中随机地取60个装一箱。我们所关心的问题是：每一批锁具共有多少个，如何衡量随机装箱造成的团体顾客的抱怨程度以及采取何种方案装箱来尽量避免团体顾客的抱怨。一、模型假设1、钥匙的每个槽的高度在生产过程中能够严格控制。2、满足条件（*）的两个锁具一定能够互开。关键假设二、模型建立与求解1、确定一批锁具的总数(1)所有可能排列为种

4、(2)受条件2和条件3的约束，要排除一部分排列方式，称为除去集D.(3)令显然，，且可以计算得出：所以，一批锁具的总数为7776-（6+450+456+792+192）=5880个考点之一装箱总数为5880/60=98箱例如71、装箱方案设槽高之和为H，则与是互开对设是一个锁具，则可以验证，也满足条件1、2、3。也是一个锁具，并且与奇偶性恰好相反，称为对偶锁具，故所有锁具分为两部分：奇类与偶类，且数量相等，各占一半。分奇、偶类分别装箱，一批锁具中奇偶各装49箱，作上标记，则只要团体顾客购买不超过49箱，就可以保证不会出现互开现象。绝

5、大部分参赛队的装箱方案，普通！2、方案最优性的证明三种境界用计算机对互开对数进行穷举计算得到在一批锁具中互开对总数为22778对。用顶点表示锁具，用边表示两个锁具为互开对，得到图，其中，记=奇类锁具，=偶类锁具，则是一个二分图，记作.要证明49箱是最优结果，等价于证明图的最大点无关集含2990点，或等价于证明图存在完美匹配已构成亮点。引理1二分图含有覆盖的每个顶点的匹配的充要条件是对任意有（1）定理二分图的是它的两个最大点无关集。[证]由奇类锁具与偶类锁具的对称性可知满足（1），有误，见下图即中含有覆盖中每个顶点的匹配，显然也覆盖了

6、中的每个顶点，于是是完美匹配，亦即的最大点无关集包含点数不可能超过2980，所以我们的销售方案是最优的。[评注]证明有误，例如右图：结论是正确的，已有计算机搜索结果证明，但尚未见到理论证明。71、定量分析顾客抱怨互开的程度（1）对于随机装箱的方案互开对总数为对，平均每个锁具与其它锁具能组成的互开对数为对。随机装箱时，某一个指定的锁具与箱中的其余59个组成互开对的平均数为（个）一箱中平均互开对数为（对）同理可知：箱锁具中，能与某一个指定锁具互开的锁具个数平均为（个）平均含有的互开对数为也是大部分队的做法，普通！显然，或越大，顾客抱怨程

7、度越大。12492.339.415693.50.0780.1573.87（2）对于奇偶分类装箱的方案当购买量不超过49箱时，不会抱怨。当购买量超过49箱时，先从奇类中取出49箱，再从偶类中任取出箱出售，平均互开对数为（对）故奇偶分类装箱后团体顾客的抱怨程度减少了。[注]模型评价：1、分析出色，结构完整、严谨，较圆满地解决问题。2、最优性证明有误，但问题转化为图论问题已构成亮点。3、销售方案普通，不大符合实际。4、抱怨程度的分析不够深入。7论文二（兰州铁道学院）较实际的一种销售方案：序贯销售。亮点，实现不困难，关键是想法。装箱分奇偶两

8、类，按槽高的大小排序，则有下图结果表达精致为提高团体顾客最大可购买箱数，再考虑按槽高的大小及字典序从小到大装箱。：（11123）（11132）（11213）（11231）（11321）（12113）……：（11124）（11142）（