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
© 1995-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
© 1995-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
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
数学的实践与认识 在图H中没有公共的端点,则称M为H的对集(或匹配)。若H没有另外的对集M, 使M'|>|M|,则称M为H的最大对集。 三、建立模型 定义锁具图:G=(V,E),其中,V为顶点集,V中一顶点表示一个锁具,即V是 批锁具的全体。E为边集,对V中任意两点,当且仅当它们所代表的锁具能够互开 时,则用一条边将此二点连接。 为了方便,用五元数组来记一个锁具 其中h;(=1,2,3,4,5)为锁具的第i个槽的高度,并记 Total 称之为此锁具 的总槽高。根据每个锁具的总槽高 Total值,可将锁具图G(V,E)的顶点集V分为20 个子集,分别记为 每个子集的元素个数如下表 集合中元素个数2050120162251322405508539563 集合中元素个数563 则A(i=8,9,10,…,27)具有下面两条性质: A,是图G(V,E)的独立集G=8,9,10,…,27)。 2.A中的元素只可能与A-1或A+1中的元素有连边。所以锁具图G为20部图 为了解决问题,我们将V分成两个集合 A,, Q 显然,P,Q都为图G的独立集,即G(V,E)为二部图 我们应注意到下面两点: 1.一批锁具的个数即是锁具图G(V,F)的顶点数|Vv=5880 2.从一批锁具中取出一些锁具构成集合K,要求K中任意二锁具不能互开,则K 是锁具图G(V,E)的独立集。所以求解问题2和问题3就要深入研究独立集。因而锁具 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第26卷(1996)第1期 图的独立数就变得相当重要了。 下面就讨论锁具图G(V,E)的独立数。 四、主要结果 定理1(1中p.108)对任意图H(V,E), a(H)+B(H)=VI 定理2(〔1〕中p.27)在二部图中,最大对集的边数等于最小覆盖的顶点数 定理3锁具图 G(V,E)存在边数为2940的对集 定理4锁具图G(V,E)的独立数a(G)=2940。 所以由定理4知,锁具图的最大独立集的元素个数为2940。进而推得,对于任何 种装箱方案,团体顾客的购买量超过2940套锁具时,就一定会出现互开的情形。 五、定理的证明 定理1,2的证明可参阅参考文献〔1。 定理3的证明此定理的证明实际上是用计算机找出了一个边数为2940的对集。 程序的设计思想是:将P中元素(h,h2,h3,h,h)作为整数 10000h1+1000h2+100h3+10h,+ 放入数组ou[2940中,Q中元素类似地作为整数放入数组j(2940〕中。再构造一个矩 阵 A=(a1)29 其中 1,o与j门有连边 0,o[门与jj没有连边。 找出A中不同行不同列值为1的元素的最大个数,即是锁具图G的最大对集的边 数。为找出最大对集及其边数,我们采用下面的方法找出一对集其边数为2940。在矩阵 A中找出行和最小的行(设为第i行),再在此行元素为1的列中找列和最小的列(设为 第j列),此时得到要求的对集的一条边,即ou(i与jj之间的一条边。 在A中将第i行与第j列划去,又得一新的矩阵,对新的矩阵同样处理,直到矩阵中 找不出不同行不同列的值为1的元素或找到了2940个不同行不同列的值为1的元素 最后可得出一对集。实际上,我们的程序计算出了边数为2940的对集。 在很多的图论书中都给出了计算最大对集(匹配)的算法,但对锁具图G(V,E)来 说,由于规模太大而无法在普通微机上实现。既便是对上述程序设计思想实现时也遇到 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved