全国大学生《数学建模》竞赛：1994B

关于锁具装箱的数学模型 黄宗虎李波李春福 (电子科技大学 指导教师徐全智 编者按本文首先利用组合计数的方法求得一批锁具的总数并按槽高和的奇偶性分类装 箱说明团体顾吝一次购买量不超过49箱时一定不会出现互开现象,作者试图利用图论的 定理证明方案的最优性,但在证明过程中,从奇类镜与钢类具的对称性并不能得到图 得到随机装箱时顾客的抱怨程度的量化结果 整篇文章建模假设合理综合运用多种学科工具,较园满完成题目的要求,并有一定的创 见叙述简洁清楚,结构严谨是一篇较优秀的参赛论文 摘要本文建立了一个关于如何对一批弹子锁具进行装箱和标志的模型 本文首先用组合数学的方法求得了一批锁具的总数为5880件,接着分析了能够互开的锁 具之间的特性,从而得到以下装箱方案:根据钥匙槽高度之和的不同奇偶性将锁具分类装箱,按 照这个方案,当购买量不超过49箱时,就可以保证一定不会出现互开的情形.文中用图论知识 证明了这个方案是最优的.本文从概率论的角度,引进平均互开对数E(m),衡量了按原方案 装箱时顾客的抱怨程度,并将本文的方案与原方案进行比较,得出新方案明显减少了顾客抱怨 程度的结论 问题的重述与分析 某锁厂生产一种弹子锁具,每个锁具的钥匙有5个槽,令h;(i=1,2,3,4,5)为钥匙第 个槽的高度,则一批锁具应满足如下三个条件 条件1对任意一种槽高排列h1h2h3h4hs5有 h∈1,2,3,4,5,6(i=1,2,3,4,5) 条件2对任意一种槽高排列h1h2h3h4hs,至少有三个槽高互不相同 条件3对任意一种槽高排列h1h2h3h4h3,有 h;-h1-11≠5(i=2,3,4,5) 而同时满足下面两个条件的两个锁具可以互开,并把这两个锁具称为一个互开对 1.两个锁的钥匙有四个槽高度相同; 2,其余一个槽高度相差1 锁厂销售部门原先在一批锁具中随机地取60个装为一箱出售,这样一来,成箱购买锁 具的顾客总抱怨购得的锁具有互开现象 我们所关心的问题是每一批锁具共有多少个,如何衡量随机装箱造成的团体顾客的抱 怨程度以及采取何种方案装箱来尽量避免团体顾客的抱怨 由一批锁具中,互开对总数是确定的,但在随机装箱之后,对于每一箱面言,锁具互开现 象就不可避免地带有了随机性,因而可以用统计平均值定量地衡量随机装箱造成的团体顾

关于锁具装稻的数学模型 59 客的抱怨程度 为了能够提出一种方案来装箱和标志,以尽量避免团体顾客的抱怨,就需要找出能够互 开的锁具之间的特性,从而使能够互开的锁具分开装箱和标记 文中用到的符号及其说明 符号。说明 符号 说明 23,4,5)/锁具钥匙的第;个槽的高度 a(G)图的最小覆盖中的顶点个数 H h B1(G)图G的最大匹配中的边数 满足条件1但不满足条件2或条件3的 钥匙槽高度的排列方式的集合,称为A(G)图G的最大独立顶点集中的顶点个数 除去集 D2(i=1 D的一个完全划分 Na(V)图G中v的邻集 2,3,4,5) 批锁具中平均每把锁具与其它锁具 E M 图的最大匹配 所能组成的互开对数 K箱锁具中平均每把锁具与其它锁具 集合V的元素个数 所能组成的互开对数 总互开对数 互开对数 E(m)K箱锁具中平均含有的互开对数 某锁具 锁具集合/顶点集合 互开锁具对的关系构成的边的集合 G(vX由v和X组成的图 P(G)图G的顶点个数 二、模型假设 1.锁具厂在生产锁具过程中能够准确地知道钥匙的每个槽的高度 2.对于同一批中两个锁具,若二者相对应的5个槽的高度中有4个相同,且另一个槽的 高度差为1,则一定能互开 模型的建立及求解 1.确定一批锁具的总数 我们根据生产一批锁具的三个条件,用排列组合的知识对一批锁具的总数目进行求 解,其主要过程如下 (1)根据条件1,钥匙槽高度的可能排列有63=7775种 抱 (2)受条件2和条件3的约束,实际制锁时还要除去一部分钥匙槽高度的排列方式,我 们称这些排列方式形成的集合为除去集D 现 (3)条件3可等价为钥匙槽高度排列方式中不能出现1和6相邻的情况 顾 (4)对除去集D可进行如下划分

60 全国大学生数学建模竞赛优秀论文汇编 令D1=h1=h2=h3=h4=hs的排列}; D2=|h,(i=1,2,3,4,5)中只有两个不同数的排列}; D3=1h,(i=1,2,3,4,5)中有三个不同数且1和6相邻的排列|; D4=|h1(i=1,2,3,4,5)中有四个不同数且1和6相邻的排列 D3=|h(i=1,2,3,4,5)各不相同且1和6相邻的排列 显然,D(i=1,2,3,4,5)是D的一个完全划分,即D1UD2UD3UD4UD3=D 且D∩D=0(i,=1,2,3,4,5且≠j我们分别求出了D2(i=1,2,3,4,5)中的元 素个数(详细计算见附录1)如下:1D11=6;1D21=450:1D31=456;1D,1=702;1 D3=192(D1表示集合D中元素的个数) 综上,一批锁具的总数为 7776-(6+456+792+192)=5880件 可装的箱数为 5880 98箱 2.装箱方案 (1)对锁具进行分类 当两个锁具相对应的5个槽的高度中有4个相同,另一个槽的高度差为1时,它们可以 互开我们惊奇地发现了下面的规律 定理在一批锁具中,能够互开的两锁具的槽高排列h1h2h3h4hs和hth2h3h4h5 其各槽高度之和H=∑h和H=必然具有不同的奇偶性 因为互开的两个锁具有四个槽高度相同,仅有一个槽高度差1,那么高度之和H h和H=∑h必为两个相邻的自然数,而两个相邻的自然数中,必有一个为奇数,另 个为偶数 根据定理,我们把锁具按钥匙槽高度之和H的奇偶分为两类,H为奇数的属于奇类,H 为偶数的属于偶类,这样,能够互开的锁具一定分属于奇类和偶类 (2)求解奇类和偶类中锁具的个数 对一个锁具的钥匙槽高度的排列h1h2h3h4h5,我们用7分别减去每个高度h(i=1,2 3,4,5),形成另一个与其对偶的排列:(7-h1)(7-h2)(7-h3)(74(7-h)记原排列 的高度和H0=∑h,新排列的高度和H (7-h1)具一 则有 ,个三具 H0-H1=3 为使上式成立,H、H1中必有一个偶数和一个奇数,而每一个奇(偶)类中的排列必能 从偶(奇)类中找出与其对应的对偶排列,这种对偶关系是一一对应的.所以 奇类中锁具数=偶数中锁具数=S880 故奇类和偶类中的锁具数都为2940件

关于锁具装箱的数学模型 (3)装箱和标记 基于以下讨论,我们可得到如下方案: ①生产锁具过程中记录每个钥匙槽的高度,从而确定H的奇偶性,将生产出来的锁具 分为奇类和偶类 ②将奇类和偶类分别装为49箱并做“奇”和“偶”的标志 D 这样,销售部门可以根据所做标记只选同类的箱子售给团体顾客.只要他们一次购买的 箱数不超过49箱(即2940个锁具),我们就可以保证他们的锁具不会有互开现象,他们也不 会抱怨了 3.对方案最优性的证明 我们用计算机对互开对总数进行穷举法计算(见附录2),得到在一批锁具中互开 对总 数为22778对 我们将锁具的互开关系用图表示出来锁具集合用顶点集合V表示,如果两个锁具V V(i,=1,2,…5880且i≠j能够互开,就用边x连接起来,所有X组成边集合X,用 这种方法得到的图G0(V,X)有5880个顶点和22778条边 我们引用图论中的一些概念 最大匹配 最小覆盖 最大独立顶点集邻集N(V)二分图G(V1,V2,X) 最大匹配中的边数B1(G)最大覆盖中的顶点个数c0(G) 最大独立顶点集中顶点个数0(G) 这些概念在一般图论理论书中可见到(可参见文献[1],[2] 我们的目的是寻找图G0中的最大独立顶点集,即不包含互开锁对的最大锁具集合 引理1二分图G(V1,V2,X)含有饱和V1的每个顶点的匹配的充要条件是对所有 vasV,|Na(V0)|≥1Vo(Va表示集合V中元素的个数 (1)(见[1]) 引理2在二分图G中,最大匹配M的边数等于最小覆盖的顶点数a0(G) 引理3a0(G)+(G)=P(G) (见[1]) 其中P(G)为图G的顶点总数 对二分图G0(v,X),我们将奇(偶)类顶点集合定义为v1(V2)得到G0(V1,V2,X) 定理分图G0(V1,V2,X)的V1,V2是它的两个最大独立顶点集. 证明:我们的图G0(V,X),对表示奇类锁具的顶点集合V1,由奇类锁具与偶类锁具的对 列 称性可知,G0(V1,V2,X)满足(1),即图Gn(V1,V2,X)含有饱和V1中每个顶点的匹配M 又因为V1中各顶点互不邻接,则 中P(G0) 2≤M|≤B1(G0)=a0(G0) (由引理2得) B0(G0)=P(G0)-a0(G) (由引理3得) 能 Pc ≤P(G0) P(G0)5880 2=2940 即图G0的最大独立顶点集中的顶点数不大于2940,而我们划分的独立集(奇类集和偶

62 全国大学生数学建模竞赛优秀论文汇编 类集)的顶点个数为2940,因此奇类集V1和偶类集V2是G0(V1,V2,X)的两个最大独立 顶点集定理得证 所以,我们的方案可以使锁具不出现互开情况时购买量达到最大.这就证明了我们的方 案是最优的 4.定量分析顾客抱怨互开的程度 (1)对于随机装箱的方案 在一批锁具中,互开对总数为m=278对,则平均每个镇具与其它所有锁具能组成 的互开对数为E=0M=7.75(对) 对于任一个指定锁具S,从其它5879把钥匙中任取一把,能打开该锁的概率是均等的 这样,如果从另外5879个锁具中随意取出59个锁具与S装成一箱,则在这一箱中能与S组 成互开对的锁具个数平均有 E1= 5879 0.078(个) 平均含有的互开对数为 E(m1)=50=2.3对) 同理可以得知:箱领具中能与某一个锁具互开的锁具个数平均为E.=E×5元,平 均含有的互开对数为 E(m)=02B:=02912×E=3 22778 5879×98×kx(60k-1) 显然,E4和E(m)的大小反映了购买k箱的顾客的抱怨程度,即E或E(m)越大,顾 抱怨程度越大 表1k=1,k=2和k=4的具体结果 箱数k 含有的互开对数E(m) 2.339.415693.515 能与某一锁具S互开的锁具数E40.078015733.87 (2)对于奇偶分类装箱的方案 由前面的分析知,给箱子进行奇偶标志后再出售,只要顾客购买量k不超过49箱,就可 以保证不出现互开的情况,顾客自然不会抱怨当购买量k超过49箱时,可以先从奇(偶)类 锁具中取出49箱,再从偶(奇)类锁具中任取k-49箱出售给顾客,互开对显然只产生在49 箱奇(偶)类锁具与k-49箱偶(奇)类锁具之间.此时,k箱锁具中的平均互开对数为 k-49 E(m1)=2278×02940=2278×X p(对) 对比随意装箱的互开对数为 E(n)-53797798 k(60k-1), 可知 当k≤49时,E(m)=0,E(mk)>0中大的2

关于锁具装箱的数学模型 63 立 此时顾客的抱怨被避免了 当4949时,取奇(偶)类49箱后剩下的k 就可 箱在偶(奇)类中按序号从小到大取箱.使得在k箱中互开总数尽量减少,这样必然更 )类 减小顾客的抱怨程度 四、模型评价 1.本模型利用数的奇妙的奇偶性为制锁厂提供了一项很好的锁具装箱方案.此方案在 大范围内消除了锁具的互开现象,而且方案简单明了,施行方便 2.本模型综合运用了多种方法对问题进行求解.其中穷举法简单易懂,用计算机编程 运行时间仅几秒钟;而概率、图论、组合数学等方理论性较强,逻辑严密,而且易于为 3.当锁具的种类变化时,即锁具的槽数和每个槽的可能高度的集合发生变化时,我们 方案仍然适用,将我们的计算机程序稍作修改,就能很快得出一批锁具的总数和奇类、偶

全国大学生数学建模竞赛优秀论文汇编 类锁具的个数 4.我们的模型还能应用到其它类似性质的事物上,如对条形码的排列组合和识别分类 问题,只需将可能高度改为可能码数,槽数改为条形码的条数即可 参考文献 1]王朝瑞,《图论》(修订本),北京工业学院出版社出版,1987年 [2]李慰萱,《图论》,湖南科学技术出版社,1980年 六、附录清单 附录1除去集D的元素个数的详细求解 附录2程序框图、源程序及运行结果(略) 1.程序说明 2. PASCAL源程序 附录1 除去集D(i=1,2,3,4,5)的元素个数的详细求解 1.根据D1的性质,h1(i=1,2,3,4,5)都取同一个数,明显有D1个元素个灵敏为 2.根据D2的性质,h;(i=1,2,3,4,5)中只有两个不同数1和a2,我们进行如下考 虑,让每个h1(i=1,2,3,4,5)都可以任取a1和a2,有25种方式,但这样做又重复了D1中 五个槽高均为a1和五个槽高均为∞2的两种组合,因而须从25中减去2,最后考虑到a1, ∈1,2,3,4,5,6},可有C种取法,故而D2的元素个数为 C2(23-2)=450个 3.根据D3的性质,h1(i=1,2,3,4,5)中必有1和6,记另外一个与1和6不同的高度 数为a,我们考虑如下完全划分 (a)h(i=1,2,3,4,5)中三个1和一个 第一步,从h1h2h3h4h3中选出了三个来安排1,有C3种方法第二步,从剩余的两个槽 位中选一个来安排6,剩余最后一个位置自然要排a,因而有PC3种安排方法,但这样做纳 入了D集中的两个元素1116和6a111须从安排方法中减去,又o可以12,3,4,5中任取 数,故而共有排列方式 C(2C3-2)=72种 b)h(i=1,2,3,4,5)中三个6和一个1 与(a)同理可知共有排列方式 C2(C3-2)=72种半个分 (c)h2(i=1,2,3,4,)中有两个1和两个6 第一步从h1h2h3h4h3中任选两上来排1,有C3种选法;第二步,从剩余三个位置中任 选两个安排6,剩下最后一个位置自然要排a,因而有CC3种排法但这样做纳人D集中的 两元素11066和66a11,须从排法中减去2.又o可以{2,3,4,5中任取一数,故而共有排列

关于锁具装箱的数学模型 方式 C(CC3-2)=112种 (d)h1(i=1,2,3,4,5)中有两个1和一个6.部 第一步,从h1h2h3h4h5中选出二个安排1,有C3种方法,第二步,从剩余3个位置中选 个排6,剩余的二个位置都排a,因面有CC种排法但这样做纳入了D中的9个元素 11a6、11m6a、6a11、a6a11、1ala6、1o6a1、6a1a1、11a6和6au11a,须从排法中减 去.又a可以{2,3,4,5|中任取一个数,故而共有排列方式 C(CC-9)=84种 (e)h(i=1,2,3,4,5)中有两个6和 与(d)同理可知共有排列方式 (C3C-9)=84种 (1)h1(i=1,2,3,4,5)中只有一个1和一个6 这样考虑,三个a可形成四个间隔位,将1,6做为一个数插入四个间隔位有C4种方法, 这样得到的组合方式显然属于D3,同样可将6,1做为一个数插人四个间隔位,而a可从2, 3.4,5中任取一数,故而共有排列 C4(P4P2)=32种 综上所述,D3集中元素的个数为 72+72+112+84+84+32=456个 考中 4.根据D4的性质,h(=1,2,3,4,5)中必有1和6,记另外两个与1和6不同而且相 互之间也不同的高度数为o1、2,我们考虑如下完全划分: (a)h;(i=1,2,3,4,5)中有两个1和一个6 与3-(d)的情况相类比,现在的情况是m1≠2且m1,m2∈12,3,4,51,而前面的情况 是有两个相同的a且a∈12,3,4,5}.因而同理容易推知现在共有排列方式 度 CP(C3C-9)]=252种 (b)h,(i=1,2,3,4,5)中有一个1和两个6 同理,与3-(e)的情况类比可知共有排列方式 CalP(C5 9)=2种 纳 (c)h1(i=1,2,3,4,5)中只有一个1和一个6 取 与3-(f)的情况类比,现在的情况相当于原来的构成间隔位的方式增多了,可以是两 和一个m2或两个a2和一个m1构成间隔位,它们都有C3CH种方式,又1,2∈12, 3.4,51,因而现在的情形下共有排列方式 C[C3CI(P!P2)+ C3CI(P!P2)]=288 F 综上所述,D4集中元素个数为 12+252+288=792个 5.根据D3的性质,h1(i=1,2,3,4,5)中只有一个1和一个6,记其余三个与1和6不同的数 任 为m、m2、3∈|2,3,4,5},故有P种构成间隔位的形成由此可知Ds集中元素的个数为 的 (,0P(PP2)=1192个 列 沿十

装箱与销售模型 兰州铁道学院刘振杨文青何新宇 指导教师俞建宁 绵者按本文较详细地讨论了装箱和连续销售问题,证明了从任一箱起顺次销售能保证 至少有35箱不会发生互开现象,进面用字典装箱可改进到42箱这点是很有创见和特色的 (b) 假设 1.两把锁具对应的5个槽的高度中有4个对应相同,另一个槽的高度差为1时,两锁必 能互开 模型I(1) 在考虑使团体顾客不再或减少抱怨的前提下、兼顾销售方便,我们拟采用连续数字作为 箱的编号,销售时按箱的编号连续销售 设一批锁具中第÷把钥匙从一端开始顺次各槽的高度值组成一个向量记为B B1=(b1,b3),…,bm1), 其中m为一批锁具中各钥匙槽的个数(本模型m=5) 从而可有如下结论: 结论1:若1B1-B1≠1,则第i把锁和第把锁不能互开(证略) 由结论1得如下推论 推论1:要使团体顾客不再或减少抱怨,必须使1B1=1B1=1的两锁具装入编号相 距尽可能大的箱中 推论2:模同为偶数的锁具间不能互开 模同为奇数的锁具间不能互开 模相等的锁具间不能互开 由以上分析得到下面的装箱方案 将模为偶数的锁装入前箱,模为奇数的锁装入后箱(1+j=Y,Y为总箱数,本题Y =98),且把模为偶数和奇数的锁具分别按模从小到大的顺序排列后,依次装箱 记模为IB1|的所有锁具数为a(B1) 本文用计算机程序对不同1B1的a进行计算,结果如下 2(8)=20,2(9)=50,2(10)=120,2(11)=162,2(12)=251, 2(13)=322,2(14)=405,2(15)=508,2(16)=539, 2(17)=563, 2(18)=563,2(19)=539,2(20)508,2(21)=405,2(22)=322 2(23)=251,2(24)=162,2(25)=120,2(26)=50,2(27)=20 由统计数据及装箱方案可得表1:

关于锁具装箱的数学模型 67 表1模型I(1)的装箱方案 810121416182022242691113151719211232527 (编号 aB120120251405539563508322162|5050162|322585153940525112020 混合箱 768592 2|4|815|2413142|475|s4|591687810319 34434852 610 22m 3544 顺次装箱自然排序 5762718089 7483 667584 对表1说明如下 (1)表中第一行为上述装箱方案对应的模1B1的排列 (2)表中第二行为模为B1的锁具的个数 (3)第三行以下为模为B1I的锁装入箱的对应编号 若锁具1B21与锁具1B|能互开,记1B1所在箱与1B|所在箱在自然下的距离为 记M(S)为从任意箱处顺次连续拿取一定不会出现互开锁的最大箱数,则 相 AM(S)=min|S1-1.四 据表1有:即 S=150,49,48,47,46,45,43,42,41,40,39,38,37,361, M(S)=36-1=35 据以上结果作购买量和出售方案对照表(表2),表2中曲线上各标值表示由该点对应 号开始顺次连续购买,一定不会出现互开锁的最大箱数.显然,保证一定不会出现互开 的最大购买量为49箱 表2使用说明: (1)若购买箱数N≤35箱,可以从任一标号开始,顺次连续取 (2)若购买箱数N=49箱,只能从第1箱或第50箱或第98箱连续取 (3)若购买35<a≤N≤b<49箱,(其中a,b为表2上可取的标值范围的外限) (1)当b位于a点左边时,b点取对应箱号的上限,a点取对应箱号的下限 ()当b位于a的右边时,b取对应箱的下限,a取对应箱的上限