关于锁具装箱的数学模型 黄宗虎李波李春福 (电子科技大学 指导教师徐全智 编者按本文首先利用组合计数的方法求得一批锁具的总数并按槽高和的奇偶性分类装 箱说明团体顾吝一次购买量不超过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