关于锁具装箱的数学模型 63 立 此时顾客的抱怨被避免了 当49<k<98时,E(m1)<E(m1)平到诗 的方 此时顾客的抱怨程度减少了 我们在右面画出了E(m)和E(m)的比较图 20000 0000 S组 4如 (3)在奇偶分类基础上再分类 对于某个锁具S,一批中能与它互开的锁具个数x是一定的,那么x的范围是多大呢 平 我们用穷举法利用计算机得到4≤ad≤10.并且得到了对应于每个sd的属于奇类的锁具个 数(见下面程序结果),由于奇偶的对称性,偶类也有同样的结果 程序运行结果如下 Total:= 5880 odd:=2940Even:2940 互开总对数:22778 0;互开对为 4,45;互开对为5,105 互开对为6,296;互开对为(7,609;互开对为8,91 互开对为9,74;互开对为10,150;互开对为11,0; 我们设想在奇偶分类后,再对奇(偶)类按每个锁具的sd从小到大对锁具进行装箱,并 标记以序号1,2,…,49.,这样当团体顾客购买箱数k>49时,取奇(偶)类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: