高等运筹第九讲(刘巍)大连海事大学

高等运筹学,大连海事大学刘巍,目录,第一篇运筹学发展历史第二篇运筹学中的数学规划第三篇运筹学中的组合优化第四篇运筹学中的随机优化第五篇运筹学中的博弈论第六篇运筹学中管理科学第七篇运筹学中智能计算第八篇运筹学发展势态,第九讲内容,第十一章组合数学及相关问题,第十一章组合数学及相关问题,组合数学概述排列组合容斥原理鸽巢原理递推关系与母函数,组合数学概述,组合数学是近几十年来发展最为迅速的一个数学分支，它与分析、代数、数论、概率论等基础数学的多个学科有密切联系，组合结构已经成为许多数学理论不可或缺的组成部分。离散结构在信息科学、物理学、生物学和化学等众多领域中大量出现，为组合数学的发展提供了强大的动力。,近年来，组合数学的思想和方法在数据结构和算法分析中都有重要的应用;利用符号计算中的算法，数学软件正在为越来越多的数学领域服务。组合设计为现代移动通信以及光纤通信中的编码技术提供了基础;它还应用于身份认证、密钥分享、数字签名等密码系统的设计中。此外，利用组合数学为处理基因序列比对和物种关系分析中的大量数据提供了一个有效的途径。组合数学在信息时代将有着非常广阔的应用研究前景。,两个传说,在我国古老的易经中有这样一句话：“河出图，洛出书，圣人则之。”后来，人们根据这句话传出许多神话。,传说在伏羲氏时代，黄河里跃出一匹龙马，龙马背上驮了一幅图，上面有黑白点55个，用直线连成10数（如图），后人称之为“河图”。,又传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个大乌龟，甲上背有9种花点的图案，9种花点数正巧是19这9个数，各数位置的排列也相当奇妙，横行、纵列以及两对角线上各自的数字之和都为15（如图），后人称之为“洛书”。,河图、洛书两图中黑点组成的数都是偶数（古代称阴数），白点表示的数是奇数（古代称阳数）。其中把“洛书”用数字表达就是下面的数表，其任意横、竖、斜各条直线上的三个数之和均相等（等于15），这就是我们今天所说的“幻方”。,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。,概念理解,广义的组合数学就是离散数学；狭义的组合数学是图论、代数结构、数理逻辑等的总称。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等,组合数学是一门研究离散对象的科学,组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft的BillGates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈,美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T联合创办的，设在Rutgers大学），该中心已是组合数学及理论计算机科学的重要研究阵地。美国国家数学科学研究所（MathematicalSciencesResearchInstitute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动,美国重要的国家实际室（LosAlamos国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。,欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构,亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速,组合花絮（1）-四色问题,如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论却是一个著名的世界难题，1976年数学家通过计算机运算得到证明而成为四色定理。,组合花絮（2）-中国邮递员问题,著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。,组合花絮（3）-任务分配问题,有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？,组合花絮（4）-河洛图,我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号,组合花絮（5）-装箱问题,当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。,组合花絮（6）-过河问题,在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很典型、很简单的组合数学问题。,组合花絮（7）-稳定婚姻问题,假如能找到两对夫妇（如张（男）-李（女）和赵（男）-王（女），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法,组合花絮（8）-管理调度,我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学典型例子。又比如，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用说了,组合花絮（9）-库房和运输的管理,怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存取的地方）。,组合花絮（10）-铺地砖问题,我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题,组合花絮（11）-金融分析,组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了金沙股市风险分析系统现已投放市场，为短线投资者提供了有效的风险防范工具,核心内容,依据一定的规则来安排某些事物的有关数学问题，这些问题包括4个方面：这种安排是否存在，即存在性问题；如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题（包括枚举的验证与效率）；怎样构造这种安排，即算法构造问题；如果给出了最优化标准，又怎样得到最优安排，即最优化问题。,相关问题,排列组合容斥原理鸽巢原理递推关系与母函数二分图的最大匹配,1.1加法法则与乘法法则.加法法则设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。,一、排列组合,例某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。,例北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。,乘法法则设事件A有m种产生式，事件B有n种产生方式，则事件A与B有mn种产生方式。,集合论语言：若|A|=m,|B|=n,AB=(a,b)|aA,bB,则|AB|=mn。,例某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有53=15个。,例从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。,例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互相容性。,1.2排列与组合,定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。,若取出r个元素而不考虑次序，则称从n个不同元中取r个元的组合。其组合的个数记为C(n,r),规定：,从n个不同元中取n个的排列称为n的全排列,我们有下列排列与组合的计数公式：,特别地，对于全排列有P(n,n)=n!。,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,r)=n(n-1)(n-r+1)有时也用nr记P(n,r),若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。,故有C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!,6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。解.由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是（种）,由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是6！720于是我们得到满足要求安排方案共计有,A（0,0）,B（5,4）,求n*m的方格图形中，从点（0，0）到点（n，m）的最短路径数目,我们用组合数学的思路来解题。最短路径必定是一条只向右上走的路。设向右走一步为x，向上走一步为y。则每一条路线一定对应由n个x，m个y共m+n个元素组成的排列。以n=5,m=4为例任意一条路线如下图所示，对应的xy序列为：xyxxxyxyy,可见，只要能确定9个位置中4个y的位置就唯一确定了一条路径。所以，本题答案就是C(5+4,4)=126一般地，n*m个方格情况就是C(n+m,m),1.3模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系.在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难,于是可设法构造一易于计数的B，使得A与B一一对应。,二、容斥原理,例求1，20中2或3的倍数的个数。,解2的倍数是：2,4,6,8,10,12,14,16,18,20.(10个)3的倍数是：3，6，9，12，15，18。(6个)但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13,容斥原理研究有限集合的交或并的计数。,DeMorgan定理:,DeMogan定理的推广：,设：,容斥原理：,最简单的计数问题是求有限集合A和B的并的元素数目。显然有,例：一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？,解：令，M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；所以有,即学校学生数为336人。,一般地，我们可得定理：,定理：设A1,A2,Am均为有限集，m2,则,，其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：,容斥原理指的就是这两个式子。,例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。,解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，则AB为同时出现ace、df的排列数。,根据容斥原理，不出现ace和df的排列数为：,=6!-(5!+4!)+3!=582,例2求从1到500的整数中能被3或5除尽的数的个数。,解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合,则,例3求由a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目。,解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是：3n。,a，b，c至少出现一次的n位符号串集合即为,三、鸽巢原理,鸽巢原理,我们可能经常会遇到这样的情况：在一桌酒席上，十来个本来不相识的人坐在一起，经过不太久的交流，马上会有人找到自己的“知音”，他们可能是校友、同行、同乡、同姓、同年龄、同属相或者是朋友的朋友、朋友的同乡、同乡的朋友等。这种情况几乎在每次酒席中都会发生，以致让人感觉到这世界真是太小。难道这都是巧合吗？,聚会认友,我们经常会参加各种聚会。如果我说：在任何一种聚会中，一定有两个人，他们在场的朋友数是一样多的。你一定会很吃惊。但是，我们可以用鸽巢原理来说明，这是千真万确的。,聚会的朋友,在任何6个人中，一定可以找到3个人，他们或者互相都认识，或者互相都不认识。,六个人的聚会,3.1鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”,例367人中至少有人的生日相同。例10双手套中任取11只，其中至少有两只是完整配对的。例参加一会议的人中至少有人认识的别的参加者的人数相等。,3.2鸽巢原理之二,鸽巢原理二m1,m2,mn都是正整数，并有m1+m2+mnn+1个鸽子住进n个鸽巢，则至少对某个i有第i个巢中至少有mi个鸽子，i=1,2,n,上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=mn=2，m1+m2+mnn+1=n+1如若不然，则对任一i，都有第i个巢中的鸽子数mi1则鸽子总数m1+m2+mnn，与假设相矛盾,推论n(m1)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子,推论若n个整数的平均数大于r-1，则至少有一个整数大于等于r。,例49名数学家相遇，其中任意3人中至少有2人有共同语言，每位数学家最多会讲3种语言。证明，至少有3位数学家可以用同一种语言对话。,证明把每一位数学家看成一个顶点vi，i=1，2，3,9.如果某两位数学家能用某种语言对话，则认为其相应的顶点之间有一条边（相邻），并涂相应颜色。问题是：证明至少存在3个顶点vi,vj,vk,使边同色。,考虑v1，分两种情况：（1）v1与v2,v3,v9均相邻由于每位数学家最多会讲3种语言，故8条边至多有三种不同的颜色，因此由鸽巢原理，至少有三条边是同色的，与此三边相关的四位数学家是有共同语言的。,（2）存在j1,使v1与vj不相邻此时，不妨设j=2，由于任意3人中至少有2人有共同语言（相邻），故另外七位数学家v3,v4,v9中的每一位必与v1,v2之一相邻，从而其中至少有四位与v1或v2相邻，不妨设v3,v4,v5,v6与v1相邻。,于是四个边至多有三种不同的颜色，因此由抽屉原则，至少有两条边是同色的，与此二边相关的三位数学家是有共同语言的。注：若将9位数学家改为8位数学家，结论不真。,例520名网球运动员进行14场单打比赛，每人至少上场一次。求证：必有6场比赛，其参赛的12名运动员各不相同。,证明把每一位运动员看成一个顶点vi，i=1，2，3,20.如果某两位运动员进行一场比赛，则认为其相应的顶点之间有一条边，如此构成一个图G。根据条件知，边数为14，且问题是：证明至少有六条边的12个顶点是互不相同的。,事实上，如果某个球员参加比赛超过一场，我们只保留其一场记录，而将其它场次去掉。用图的语言就是：在每个顶点vi处抹去d(vi)-1条边（一条边可以同时在其两端点抹去），则抹去的边数不超过条，故剩下的图G1至少有14-8=6条边。G1中每个顶点的次数不超过1，因此6场比赛参赛者各不相同。,四、母函数与递推关系,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,4.1母函数,定义：给定序列(a0,a1,an,)，记为an.函数f(x)=a0+a1x+anxn+称为该序列的普通母函数，简称母函数。,例常数列(1,1,)的母函数为f(x)=1+x+xn+=1/(1-x)数列C(n,i),i=0,1,2,n的母函数为,这里的母函数只是“形式幂级数”，运算均按收敛幂级数进行。,母函数的组合意义：考察,其中：x前的系数为a,b,c的所有可重1-组合，x2前的系数为a,b,c的所有可重2-组合，一般地：xn前的系数为a,b,c的所有可重n-组合，,在前式中取a=b=c=1,则xn前的系数为a,b,c的所有可重n-组合数F(3,n).,所以，构造某组合问题的组合数an的母函数f(x)的基本方法为：用一个乘积因子(1+x+x2+)来代表一个所选元素，若该元素可重复n次，则因子中应出现xn。,例设有2个红球，3个白球，1个黑球和1个黄球.求从这些球中取出5个的不同方案数。,解：设从所给球中取出i个的不同方案数为ai,则由题设可得ai的母函数为,例求用1元和2元的钞票支付n元的不同方式数。,解：设所求不同方式数为an,则由题设可得an的母函数为,于是,定义：给定序列(a0,a1,an,)，记为an.函数称为该序列的指数型母函数,简称指数母函数。,例常数列(1,1,)的母函数为,例从n个不同元素中取r个的排列数P(n，r)指数母函数为：,例n个不同元素的可重r-排列数nr(r=0,1,2,)的指数母函数为,例求用1,2,3,4,5五个数字组成的n位数的个数，要求1出现的次数为偶数，2出现的次数为奇数，并且3至少出现一次。,解：设所求n位数的个数为an，则由题设可得an的指数母函数为：,从而有,所以,4.2递推关系,定义：设(a0,a1,an,)是一个序列，把该序列中an与它前面几个ai(0in)关联起来的方程称为递推关系。序列中的一些已知条件称为初始条件。,例如,传说在古老的印度有一座神庙，神庙中有三根针和套在一根针上的64个圆环.古印度的天神指示他的僧侣们按下列规则,把圆环从一根针上全部移到另一根针上，第三根针起“过渡”的作用.1.每次只能移动1个圆环；2.较大的圆环不能放在较小的圆环上面.如果有一天，僧侣们将这64个圆环全部移到另一根针上，那么世界末日就来临了.请你试着推测：把个圆环从1号针移到3号针,最少需要移动多少次?,1,2,3,游戏：河内塔（TowerofHanoi）,n=1时,n=2时,n=1时,n=3时,n=2时,n=1时,n=2时,n=1时,n=3时,n=4时,n=3时,n=2时,n=1时,n=4时,n=3时,n=2时,n=1时,归纳:,4.3递推关系的求解方法,（1）迭代法,例如前面的HanoiTower（河内塔）问题：,我们有,（2）母函数法,例如前面的HanoiTower（河内塔）问题：,由递推关系，我们有,我们设an的母函数为,由递推关系可得,故有,解得,所以,（3）常系数线性递关系