全国大学生《数学建模》竞赛：1994all.pdf_大学文库

1995年第1期数学通在整个平面上无闭轨讨论过的例1: 证明 0r+a,=2x+7于是 23y-b b v(=)=2BQ(a, oo)=2aB22-2aBa (y)=2ilx=-=2P(-2,y) 4b1b3-b=-46(2b2+a2) 从结论上看,若选取适当的a,B可使4b1b3 >0成立由结论2判定系统在整个平面上无闭 =2y2+6y+ 轨,但我们已证明对于任意的a,,a,b(a,B,a,b 均不为0)系统(4)在整个平面上无闭轨.即是说由于4a1a3-a2=104>0 对于系统(4)当4b1b3-6<0时,在整个平面由结论2知,系统(7)在整个平面上无闭轨上无闭轨注:结论2也是一个充分条件,有一些二维系参考文献统,当φ(y)(φ(x)中的4a1a3-a2<0(4b1b3-1张锦炎.微分方程几何理论与分支问题,北大出 b<0)时,该系统也可能无闭轨.例如,我们已版社,1981 1994年全国大学生数学建模竞赛圆满结束 1994年全国大学生数学建模竞赛颁奖仪式于分析和检验等方面的答卷,参赛者可以利用任何 12月21日在北京师范大学举行.由国家教委高图书资料、计算机和软件,但不得与别人讨论教司和中国工业与应用数学学会共同主办的这次此次竞赛得到各省、市、自治区教委和各参竞赛是10月28~30日进行的,全国21个省赛高校领导的热情关注和大力支持,赛前对同学市、自治区196所高校的2600多名学生,组成和指导教师组织了各种类型的培训,推动了教学 870个队参加了竞赛改革和教材建设.不少学校认为“这种活动的真数学建模竞赛通过学生运用数学知识和计算正成果在竞赛之外,是把应试教育模式改变为能机技术解决一个有意义的实际问题,培养、检验力和素质培养的一种方式学生的创造精神和综合能力,薮励他们踊跃参加课外科技活动,提高学习数学和计算机科学的积 1992年和1993年中国工业与应用数学学会极性今年有两道竞赛题,在名为逢山开路”的组织的前两届竞赛,分别有74所和101所高校参题中,给出了一山区山峰高程和河流宽度的测量加,参赛的同学普遍反映,通过训练和竞赛不仅数据,以及修建公路、桥梁、隧道的成本,要求设提高了用数学建模方法和计算机技术解决实际问计一条由山脚经居民点到矿区的公路路线.另一题的意识和能力而且在团结合作,集体攻关道是“锁具装箱”,由于锁貝制造工艺等原因,不查阅文献,撰写科技论文等方面都得到了有益的同的锁可能会相互打开,要求为销售部门提出一锻炼.国家教委十分重视和支持这项活动·决定个锁具装箱,标志和出售的方案,以减少购买大今后每年在全国高校范围内组织该项竞赛量锁具的顾客对锁具互开的抱怨今年竞赛结束后先由各省、市、自治区评奖, 竞赛采取通讯比赛形式,由3名学生组成然后聘请专家从各地推荐的优秀答卷中评出中国在3天内完成篇包括问题的阐述和分析, 科技大学、北京师范大学等20所院校的25个队模型的假设、建立和求解,计算机实现,结果的全国一等奖,另有57个队获全国二等奖 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved

74 数学的实践与认识情况下稍作提前锁具装箱问题的补充讨论 1994年全国大学生数学建模竞赛题的补充讨论代西武李英周万勇张继生 (北京联合大学机械工程学院,北京100020) 编者按大学生数学建模竞賽及相应的活动深受我国大学生的欢迎,成千上万李加培训攴竟賽的冏学不仅从培训、参賽三天的紧张拼搏中学到了许许多多课堂上学不到的东西,得到了初步的科硏实战的锻炼,培养了合作攻关的精神,而且许多教师和同学意识到三天竟賽活动的结束不是数学建模活动的结柬,他们中不少人在竟賽结来后继续进行师生结合的创造性的数学建模活动,特别是继续对自己所选的参賽題进行深入研究并取得更好的鲒果。我们认为是值得提倡的。这里发表的文章正是北京联合大学杋械工程学院师生在竟賽活动后师生结合继续对竞賽題进行研究所取得的成果的反映。摘要本文将锁具装箱问题抽象为二部图G(V,E),根据图论知识,利用计算机得出主要结论:锁具图G的独立数a(G)=2940。从而推得,对于任何一种装箱方案,团体顾客的购买量超过2940套锁具时,就一定会出现互开的情形关键词二部图,独立数,对集(匹配),覆盖数某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,槽高从{1,2,3,4,5,6中任取一数。但由于工艺条件及其它原因,制造锁具时对5个槽高还有限制:至少有三个不同的数,相邻两槽的高度差不能是5。这样所生产出的互不相同的锁具称为一批。同一批中的两个锁具,在当前工艺条件下,若二者相对应的5个槽的高度中有4个相同,另槽的高度差为1,就会出现互开情形。从顾客的利益出发,都希望“一把钥匙开一把锁”。但该厂的销售部门在产品的装箱过程中,只是简单地将一批产品中的任意60个锁具装入一箱出售。而团体顾客往往购买几箱到几十箱,因而就不可避免地出现锁具互开的情形。团体顾客对此抱怨尤深,也因此影响了该厂的销售量。针对这个问题,需要提出一个合理的、可行的锁具装箱方案,以避免锁具互开的情况 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved

第26卷(1996)第1期 ·75· 问题1确定每一批锁具的个数及装箱箱数。问题2提出一种装箱和销售方案,使团体顾客不再或减少抱怨。问题3采用所提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开的情形问题4按原装箱办法,如何定量衡量团体顾客抱怨互开的程度(对购买一、二箱者给出具体结果)。上述问题有些已经得到较好的解决,而本文只是对问题3作些进一步的讨论图论预备知识个图G是指一个有序三元组(V(G),E(G),化),其中V(G)是非空的顶点集,E (G)是不与v(G)相交的边集,而9是关联函数,它使G的每条边对应于G的无序顶点对(不必相异)。若e是一条边,而u和v是使得9(e)=uu的顶点,则称e连接u和v 顶点u和v称为e的端点例如设V(G)={u,v,v,x},E(G)={e1,e2,e3,e}而9定义为 9(e1)=a,9(e2)=t,9(e3)=tu,G(e)=v。这时G(V(G),E(G),9)就是一个图,且可用图形表示,如图有时我们将图G=(v(G),E(G),9)简记为:G=(V(G),E(G)),或G=(V,E)。一个图,如果它既没有环也没有两条边连接同一对顶点,称之为简单图。本文讨论的是简单图,下面所说的图都指简单图。因为边总是和顶点联系在起的,所以确定了顶点集和边集,也就确定了个图二部图(或称为偶图)是指一个图,它的顶点集可以分解为两个(非空)子集X和Y,使得每条边都有一个端点在ⅹ中,另一个端点在Y中。k部图是指这样的图,它的顶点集可分解为k个(非空)子集,使得任何一边的两个端点均不在同一个子集中。对任意集合A,记其元素个数为|A 设S是图H(V,E)的顶点集V的子集,若S中任意两个顶点在H中均不相邻(即二点没有连边),则称S为H的独立集。H的一个独立集S称为H的最大独立集,如果H不包含适合|S’|>{S|的独立集S'。H的最大独立集的顶点数称为H的独立数,记为a(H)。图H(V,E)的一个覆盖是指v的一个子集K,使得H的每条边都至少有一个端点在K中。一个覆盖K称为H最小覆盖,如果H没有覆盖K使得|K”|<|K|。图 H的最小覆盖的顶点数称为H的覆盖数,记为R(H) 设图H(V,E),M是E的一个子集,M中的元素为H的边,并且M中任意两边 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved

78 数学的实践与认识了一些困难。首先,矩阵A在计算机内存中放不下,所以我们在程序中不构造矩阵A, 而是每次都去判断二锁具是否互开,为了提高程序的效率,求出每个锁具所连边的边数 (在图论中此数称为顶点的度数)分别放在数组 ouedn(2940]和jedn2940]中。其次数组ou2940〕,j[2940中一个元素表示成一个整数:10001+1000h2+100h3+ih +h5,此数可能超出微机整数所允许的范围,所以我们在程序中将一个锁具分开故在两个整数型变量中,即将ou[2940分开装到ou2940和ou2(2940两个数组中,同样将 2940]分成j1[2940和j2(2940两数组程序框图见附录程序运行速度较快,在386微机上只需要8分钟,且得出满意的结果,找出了一个边数为2940的对集。定理4的证明因锁具图G(V,E)中V|=5880,由定理3,显然锁具图G(v, E)的最大对集的边数为2940。再由定理1、2易得:a(G)=2940 六、推广 6.1槽数增加为6的情形将引言中的问题稍作改变:即将锁具槽的个数由5改变为6,其他条件不变,再来研究独立数的问题我们用上述的方法,将程序稍作变动得出下面的结果批锁具的总数为:35080 总槽高为奇数的锁具数为:17720 总槽高为偶数的锁具数为:17360 找出了边数为17360的对集,在386微机上运行时间为140分钟类似地可以推得:此时的锁具图的独立数为:17720 6.2槽高的范围改为{1,2,3,4,5,6,7}时的情形将引言中的问题改变为:锁具的每个槽高在{1,2,3,4,5,6,7}中取一数值,其它条件不变时,同样可考虑此时锁具图的独立数。我们得出下述结果: 批锁具的总数为:993 总槽高为奇数的锁具数为:4942 总槽高为偶数的锁具数为:4994 将程序再作修改,也找出了边数为4942的对集。在386微机上运行时间为11分钟。类似地可以推得此时的锁具图的独立数为:49 6.3定理4的另一种证明定理4的又一种证明:对锁具图G(V,E),因P即是一独立集,所以a(G)≥2940。又因定理3,锁具图G(V,E)的边数为2940的对集M包含了锁具图G的所有顶点(顶 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved

武汉食品工业学院学报 74 Journal of Wuhan Food Industry College 1995年关于锁具装箱的方案设计 1994年全国大学生数学建模竞赛B題的数学模型王艮远范正森 (基础部) 摘要本文对1994年全国大学生数学建模竞賽B题——锁具裴箱问題进行了探讨。首先报据題中给出的条件,利用排列蛆合方法计算出了一枇锁具的个数。然后利用数学分类法建立了一个锁具葙的数学模型。最后论证了该模型所蛤出的分类是最佳的。关键词锁具葙方案设计数学模型中图分类号O141.4 1问题的提出某锁厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6 ↑数(单位略〕中任取一数。由于工艺及其它原因,制遣锁具时对5个槽高有两个限制。其至少要有3个槽的高度不同,其二,相邻两槽的高度之差不能为5,称满足上述两条制造出来的所有互不相同的锁具为一批。虽然一批锁具互不相同,但经抽样检测,发现若两锁具对应的5个槽的高度中有4个相同而另一个的高度差为1则可以互开而其它情形则不能互开。按传统的随意装箱法,厂家总是从一批领具中任取60把装成一箱出售,这样,团体顾客往往因一次购买几箱甚至几十箱而出现锁具互开情形产生抱怨。为此,厂家想对传统装箱法进行改进要求设计出一种新的装箱法从而避免或尽量减少团体顾客的抱怨程度具体要求为:求出一批锁具的总数按60把装箱,可以装多少箱;新的装箱法应包括如何装箱(仍60把装一箱),如何给箱子加标志,出售时如何利用这些标志,并具体计算出利用新的装箱法,团体顾客一次购买量不超过多少时就定可以保证不会出现互开情形;定量地绐出衡量传统装箱法团体顾客抱怨互开的程度(对购买箱、二箱者给出具体结果) 2问题分析 21问题的第一部分是本题建模的基础,只有正确计算出一批锁具的总数之后才有可能解决后面几个问题这一部分的两个限制条件为计算带来了一定的困难在应用排列组合计数时必收稿日期:1995-01-10 o1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved

王艮远范正森:关于锁具装箱的方案设计须分各种情况考虑既不能重复也不能遗漏。 2.2问题的第二部分是本题建模的主体,新的装箱方法实质是一个将全部锁具的分类问题只要我们能提供一种方法将锁具进行分类,使每个类中的任意两把锁都不能互开然后分类装箱,并在各箱上加上标志统计数量便可解得问题2 23问题的第三部分有一定难度,因为钥匙互开与否是一个随机现象,究竟选择什么样的数量指标来衡量团体顾客抱怨互开的程度,答案是不唯一的。笔者认为可从两个不同角度来考虑 2.3.1抱怨互开程度可用概率论方法算出一箱(二箱……)锁具中平均有多少对可能互开来衡量 2.32抱怨互开程度也可用概率论方法算出在一箱(二箱…)中任取一把锁能被其它钥匙打开的钥匙数多少来衡量另外问题3的结果也可用来与新装箱法进行比较从而说明新装箱法的优效性。 3基本假设假设一批锁具中相同槽高的锁具不重复生产;一个锁具是指锁与之相配的钥匙整体锁具槽高一律指钥匙槽高;一批锁具组成一锁具集U。 4模型的建立与问题求解 4.1计算一批锁具的总数N计算一批锁具的总数有两种方法:排列组合计数法;计算机枚举法本文主要介绍前者,而后者仅作为对前者的检验前一种算法可按四步进行第一步,对槽的高度无限制时锁具的↑数为:N6=65=7776 第二步,5个高中任取一个数和二个数的锁具个数为:N=C+(CC}C+C"C3C)=456; 第三步,5个槽高中有1与6相邻槽高差为5的情况有6种,即: 5个数中含有一个1,一个6,即16×××,×16××××61×……,其中×X×中无1与6,个数为CC!·43=512。个数中含有二个1,一个6,即:161××116××1×X16……,其中X×中无1与 6,个数为[CC+C)+C+2C×42=336 5个数中含有二个6,一个1,即:616X×661××6××61,……其中Ⅹ×中无1与 6,↑数为[C(C+C十C+2C影×42=336。 5个数中含有二个1,二个6,即:1166×161×1×166,………其中×不为6与1个数为[C1(C+CC)]×4=11 5个数中含有三个1,一个6,即:1116×61×111×161,……其中X不为6与1,个数为[CC+C)]×4=72 5个数中含有三个6,一个1,即:661×16×666×616,……其中X不为1与6,个数为[CC+C)]×4=72。所以所取5个数中有1与6相邻的种数为 N2=512+336+336+112+72+72=1440 第四步,满足限制条件的一批锁具的总数为 o1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved

武汉食品工业学院学报 1995年 =N。-N1-N2=7776-456-1440=5880 共装5880/60=98箱。通过计算机编程枚举结果与上相同。 4.2新装箱方案的设计用整数I表示一把锁具的槽高和,h,表示一把钥匙从后往前第个槽的高度。先证明定理1二把锁具互开的必要条件,任意两把锁具,若彼此能互开,则槽高和之差的绝对值为证明任取ab∈U,分别记ab的槽高为h1,h2,h3,h4h5,h1,h,h,hh3,若a,b能够互开则必存在h与使得[。一h=1,而其余h一h=0所以 1.-1=(h+h2+h2+h+h5)-(h1+h2+h3+h+h3) =(h1-h1)+(h2-h2)+(h3-h3)十(h4-h)+(h5-h5) h。-h l=|。一h。作为分类的依据给定如下关系: R:锁具槽高和奇偶性相同.下面证明所给关系R是一等价关系。证明反身性:任取a∈U,显然l与l奇偶性相同对称性:任取ab∈U,若L与L同奇偶,则l与L。也同奇偶传递性:任取ab,c∈U,若L与l同奇偶,l与l同奇偶则l与l,也同奇偶故R 是一个等价关系用等价关系R可将U分为两类,分别记为: U1={a|L为偶数,a∈U} U2={b为奇数,b∈U 显然这种分类满足U1UU2=U,U1∩U2=φ 定理2同一类锁具中任意两把都必不能互开证明任取ab∈U1,若l与l均为偶数,所以l一l也为偶数由定理1知a与b不能互开,这就证得U1中任意两把锁都不能互开,同理可证U2中任意两把锁也不能互开定理3U1中元素与U2中元素相等。证明显然U中元素的l的所有可能取值为8,9,10,…,25,26,27共20↑数,记各值对应的锁具个数为J(1),则由槽高分布的对称性知 J(8)=J(27)J(9)=J(26)J(10)=J(25) J(14)=J(21)J(15)=J(20)J(16)=J(19) J(17)=J(18) 所以J(8)+J(10)+…+J(26)=J(9)十J(11)+…+J(27) 因此U中元素的l值奇偶性各占一半,即U1中元素与U2中元素相等均为2940, 将U1与U2中锁具分别装箱可各装49箱将U中装得的49箱上标上“双(n)”标志将U2 中装得的49箱上标上“单(n)标志,双,单后面的n表示第n批生产的锁具,对一位团体顽客按照上述装箱销售方案只要一次购买量不超过49箱就一定可保证不会互开 4.3对传统装箱法团体原客抱怨互开程度的衠量传统装箱法为从5880个锁具中随机抽 o1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved