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

高等运筹学 大连海事大学刘巍 目录 第一篇运筹学发展历史第二篇运筹学中的数学规划第三篇运筹学中的组合优化第四篇运筹学中的随机优化第五篇运筹学中的博弈论第六篇运筹学中管理科学第七篇运筹学中智能计算第八篇运筹学发展势态 第九讲内容 第十四章组合数学及相关问题 第十四章组合数学及相关问题 1组合数学 2近似算法 3组合多面体 4生物分子网络 1组合数学 组合数学是近几十年来发展最为迅速的一个数学分支 它与分析 代数 数论 概率论等基础数学的多个学科有密切联系 组合结构已经成为许多数学理论不可或缺的组成部分 离散结构在信息科学 物理学 生物学和化学等众多领域中大量出现 为组合数学的发展提供了强大的动力 近年来 组合数学的思想和方法在数据结构和算法分析中都有重要的应用 利用符号计算中的算法 数学软件正在为越来越多的数学领域服务 组合设计为现代移动通信以及光纤通信中的编码技术提供了基础 它还应用于身份认证 密钥分享 数字签名等密码系统的设计中 此外 利用组合数学为处理基因序列比对和物种关系分析中的大量数据提供了一个有效的途径 组合数学在信息时代将有着非常广阔的应用研究前景 两个传说 在我国古老的 易经 中有这样一句话 河出图 洛出书 圣人则之 后来 人们根据这句话传出许多神话 传说在伏羲氏时代 黄河里跃出一匹龙马 龙马背上驮了一幅图 上面有黑白点55个 用直线连成10数 如图 后人称之为 河图 又传说在公元前23世纪大禹治水的时候 在黄河支流洛水中 浮现出一个大乌龟 甲上背有9种花点的图案 9种花点数正巧是1 9这9个数 各数位置的排列也相当奇妙 横行 纵列以及两对角线上各自的数字之和都为15 如图 后人称之为 洛书 河图 洛书两图中黑点组成的数都是偶数 古代称阴数 白点表示的数是奇数 古代称阳数 其中把 洛书 用数字表达就是下面的数表 其任意横 竖 斜各条直线上的三个数之和均相等 等于15 这就是我们今天所说的 幻方 幻方可以看作是一个3阶方阵 其元素是1到9的正整数 每行 每列以及两条对角线的和都是15 5 1 9 3 7 2 4 8 6 1666年莱布尼兹所著 组合学论文 一书问世 这是组合数学的第一部专著 书中首次使用了组合论 Combinatorics 一词 组合数学的蓬勃发展则是在计算机问世和普遍应用之后 由于组合数学涉及面广 内容庞杂 并且仍在很快地发展着 因而还没有一个统一而有效的理论体系 这与数学分析形成了对照 组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题 包括安排的存在问题 计数问题 构造问题以及给出了优化标准后如何求出最优安排问题 1 1加法法则与乘法法则 加法法则 设事件A有m种产生方式 事件B有n种产生方式 则事件A或B之一有m n种产生方式 集合论语言 若 A m B n A B 则 A B m n 一 排列组合 例 某班选修企业管理的有18人 不选的有10人 则该班共有18 10 28人 例 北京每天直达上海的客车有5次 客机有3次 则每天由北京直达上海的旅行方式有5 3 8种 乘法法则 设事件A有m种产生式 事件B有n种产生方式 则事件A与B有m n种产生方式 集合论语言 若 A m B n A B a b a A b B 则 A B m n 例 某种字符串由两个字符组成 第一个字符可选自 a b c d e 第二个字符可选自 1 2 3 则这种字符串共有5 3 15个 例 从A到B有三条道路 从B到C有两条道路 则从A经B到C有3 2 6条道路 例某种样式的运动服的着色由底色和装饰条纹的颜色配成 底色可选红 蓝 橙 黄 条纹色可选黑 白 则共有4 2 8种着色方案 若此例改成底色和条纹都用红 蓝 橙 黄四种颜色的话 则方案数就不是4 4 16 而只有4 3 12种 在乘法法则中要注意事件A和事件B的相互相容性 例1 求小于10000的含1的正整数的个数2 求小于10000的含0的正整数的个数 1 小于10000的不含1的正整数可看做4位数 但0000除外 故有9 9 9 9 1 6560个 含1的有 9999 6560 3439个 另 全部4位数有104个 不含1的四位数有94个 含1的4位数为两个的差 104 94 3439个 2 含0 和 含1 不可直接套用 0019含1但不含0 在组合的习题中有许多类似的隐含的规定 要特别留神 不含0的1位数有9个 2位数有92个 3位数有93个 4位数有94个 不含0小于10000的正整数有9 92 93 94 95 1 9 1 7380个 含0小于10000的正整数有9999 7380 2619个 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 有时也用 n r记P n r 若球不同 盒子相同 则是从n个中取r个的组合的模型 若放入盒子后再将盒子标号区别 则又回到排列模型 每一个组合可有r 个标号方案 故有C n r r P n r C n r P n r r n r r 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均为有限集 m 2 则 其中N是集合U的元素个数 即不属于A的元素个数等于集合的全体减去属于A的元素的个数 一般有 容斥原理指的就是这两个式子 例1求a b c d e f六个字母的全排列中不允许出现ace和df图象的排列数 解 设A为ace作为一个元素出现的排列集 B为df作为一个元素出现的排列集 则A B为同时出现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只 其中至少有两只是完整配对的 例 参加一会议的人中至少有 人认识的别的参加者的人数相等 例 从1到2n的正整数中任取n 1个 则这n 1个数中 至少有一对数 其中一个是另一个的倍数 证设n 1个数是a1 a2 an 1 每个数去掉一切2的因子 直至剩下一个奇数为止 组成序列r1 r2 rn 1 这n 1个数仍在 1 2n 中 且都是奇数 而 1 2n 中只有n个奇数 故必有ri rj r 则ai 2 ir aj 2 jr 若 i j 则ai是aj的倍数 例 设a1 a2 am是正整数序列 则至少存在k和l 1 k l m 使得和ak ak 1 al是m的倍数 证设Sh ai Sh rhmodm0 rh m 1h 1 2 m 若存在l Sl 0modm则命题成立 否则 1 rh m 1 但h 1 2 m 由鸽巢原理 故存在rk rh 即Sk Sh 不妨设h k 则Sh Sk ak 1 ak 2 ah 0modm i 1 h 例 设a1 a2 a3为任意 个整数 b1b2b3为a1 a2 a3的任一排列 则a1 b1 a2 b2 a3 b3中至少有一个是偶数 证由鸽巢原理 a1 a2 a3必有两个同奇偶 设这 个数被 除的余数为xxy 于是b1 b2 b3中被 除的余数有 个x 一个y 这样a1 b1 a2 b2 a3 b3被 除的余数必有一个为 3 2鸽巢原理之二 鸽巢原理二m1 m2 mn都是正整数 并有m1 m2 mn n 1个鸽子住进n个鸽巢 则至少对某个i有第i个巢中至少有mi个鸽子 i 1 2 n 上一小节的鸽巢原理一是这一原理的特殊情况 即m1 m2 mn 2 m1 m2 mn n 1 n 1如若不然 则对任一i 都有第i个巢中的鸽子数 mi 1则鸽子总数 m1 m2 mn n 与假设相矛盾 推论 n m 1 1只鸽子进n个巢 至少有一个巢内至少有m只鸽子 例证明每个长为n2 1的实数序列中 一定存在长为n 1的递增或递减子序列 不一定是严格递 减 推论 若n个整数的平均数大于r 1 则至少有一个整数大于等于r 证明 设 为任取的实数序列 若此序列中不存在长为n 1的递增子序列 则一定存在长为n 1的递减序列 令mi为以ai为首项的最长递增子序列的长度 i 1 2 n2 1 因为n2 1 n n 1 1 1 由鸽笼原理的推论可知 若有某个mi n 1 则结论成立 若不然 必有mi n 1 从而有mi n 例设A a1a2 a20是10个0和10个1组成的 进制数 B b1b2 b20是任意的 进制数 C b1b2 b20b1b2 b20 C1C2 C40 则存在某个i 1 i 20 使得CiCi 1 Ci 19与a1a2 a20至少有10位对应相等 A B C 第i格 第i 19格 12 192012 1920 12 19201 1920 证在C C1C2 C40中 当i遍历1 2 20时 每一个bj历遍a1 a2 a20 因A中有10个0和10个1 每一个bj都有10位次对应相等 从而当i历遍1 20时 共有10 20 200位次对应相等 故对每个i平均有200 20 10位相等 因而对某个i至少有10位对应相等 四 母函数与递推关系 递推关系是计数的一个强有力的工具 特别是在做算法分析时是必需的 递推关系的求解主要是利用母函数 当然母函数尚有其他用处 但这主要是介绍解递推关系上的应用 例如 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 0 i n 关联起来的方程称为递推关系 序列中的一些已知条件称为初始条件 例如 利用递推关系进行计数这个方法在算法分析中经常用到 举例说明如下 例一 HanoiTower 河内塔 问题 N个圆盘依其半径大小 从下而上套在A柱上 如下图示 每次只允许取一个移到柱B或C上 而且不允许大盘放在小盘上方 若要求把柱A上的n个盘移到C柱上请设计一种方法来 并估计要移动几个盘次 现在只有A B C三根柱子可用 Hanoi问题是个典型的问题 第一步要设计算法 进而估计它的复杂性 集估计工作量 算法 N 2时 第一步先把最上面的一个圆盘套在B上 第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕 对于一般n个圆盘的问题 假定n 1个盘子的转移算法已经确定 先把上面的n 1个圆盘经过C转移到B 第二步把A下面一个圆盘移到C上 最后再把B上的n 1个圆盘经过A转移到C上 上述算法是递归的运用 n 2时已给出算法 n 3时 第一步便利用算法把上面两个盘移到B上 第二步再把第三个圆盘转移到柱C上 最后把柱B上两个圆盘转移到柱C上 N 4 5 以此类推 算法分析 令h n 表示n个圆盘所需要的转移盘次 根据算法先把前面n 1个盘子转移到B上 然后把第n个盘子转到C上 最后再一次将B上的n 1个盘子转移到C上 n 2时 算法是对的 因此 n 3是算法是对的 以此类推 于是有 算法复杂度为 H x 是序列的母函数 给定了序列 对应的母函数也确定了 反过来也一样 求得了母函数 对应的序列也就可得而知了 当然 利用递推关系 式也可以依次求得 这样的连锁反应关系 叫做递推关系 4 3递推关系的求解方法 1 迭代法 例如前面的HanoiTower 河内塔 问题 我们有 2 母函数法 例如前面的HanoiTower 河内塔 问题 由递推关系 我们有 我们设 an 的母函数为 由递推关系可得 故有 解得 所以 3 常系数线性递关系的解法 若f n 0则称序列 an 为k阶常系数线性齐次递推关系 称 xk b1xk 1 bk 1x bk 0为k阶常系数线性递推关系的特征方程 齐次常系数线性递关系的解法 若递推关系的特征多项式有k个相异实根x1 x2 xk 则递推关系的通解为 其中c1 c2 ck为任意常数 若对递推关系再给出一组k个初始值 还可以由通解求出满足初始条件的唯一解 例求解 解 此递推关系的特征方程为 其特征根为 故其通解为 由初始条件可得F0 0 将F0 0 F1 1代入得 解得 所以 若特征根出现一对共轭复根x1 a bi x2 a bi时 则递推关系的通解可表示为 若对递推关系再给出一组k个初始值 还可以由通解求出满足初始条件的唯一解 其中 例 求下列n阶行列式dn的值 解 根据行列式性质 有 此递推关系的特征方程为 其特征根为 故其通解为 由初始条件d1 1 d2 0得 解得 所以 若特征根出现k重根 不妨设a1是k的重根 则递推关系的解对应于a1的项为其中A0 A1 Ak是k个待定常数 例 求下列n阶行列式dn的值 解 根据行列式性质 有 此递推关系的特征方程为 其特征根为 故其通解为 由初始条件d1 2 d2 3得 解得 所以 非齐次常系数线性递关系的解法 定理 递增推关系 的通解为 f n 是n的t次多项式的形式 若1不是 的特征方程的根 则 有特解形式为 若1是 的特征方程的m重根 则 有特解形式为 例求和式 解 设 从则可得 其对应的齐次递推关系为 其特征方程为 其对应的齐次递推关系的通解为 因为1是特征方程式的1重根 f n 是n的三次多项式 所以有下列形式的特解 代入题上的递推关系得 于是可得方程组 从而解得 所以原递推关系的通解为 代入初始条件a1 1得 解得C 0 故有 f n 是bn的形式 b为常数 若b不是 的特征方程的根 则 有特解形式为 若b是 的特征方程的m重根 则 有特解形式为 例求解下列递推关系 其对应的齐次递推关系的通解为 解 其对应的齐次递推关系为 其特征方程为 因为2是特征方程式的1重根 所以有下列形式的特解 代入题上的递推关系 求解得 所以原递推关系的通解为 代入初始条件a0 0 a1 1得 从而解得 所以原递推关系的解为 2近似算法 近似算法是求解组合优化问题的一类多项式时间算法 它们尽管不能确保对问题的每一个实例都可以求得最优解 但是可以保证求得的解的目标值与最优解的目标值相差不多 自20世纪60年代末格雷厄姆在研究排序问题时提出第一个近似算法以后 特别是70年代初库克首次证明了存在NP一完全问题以来 为各种各样的组合优化问题设计近似算法就一直是组合优化领域的一个重要研究方向 主要包括三个方面 设计近似比越来越小的近似算法 设计运行时间越来越短的近似算法 证明近似比的下界或者不可近似性 已有的大量研究主要都集中在第一个方面 人们先后提出了对偶 半定规划 随机算法 平面划分和次模函数等技巧 第二方面的工作主要是针对存在多项式时间近似方案的NP一难问题 而第三方面的工作主要是利用20世纪90年代阿罗拉等人提出的概率可验证系统 这一方向中有很多问题有待解决 所有已知的解决NP 难问题算法都有指数型运行时间 但是 如果我们要找一个 好 解而非最优解 有时候多项式算法是存在的 给定一个最小化问题和一个近似算法 我们按照如下方法评价算法 首先给出最优解的一个下界 然后把算法的运行结果与这个下界进行比较 对于最大化问题 先给出一个上界然后把算法的运行结果与这个上界比较 迄今为止 所有的NP完全问题都还没有多项式时间算法 对于这类问题 通常可采取以下几种解题策略 1 只对问题的特殊实例求解 2 用动态规划法或分支限界法求解 3 用概率算法求解 4 只求近似解 5 用启发式方法求解 旅行售货员问题近似算法 问题描述 给定一个完全无向图G V E 其每一边 u v E有一非负整数费用c u v 要找出G的最小费用哈密顿回路 旅行售货员问题的一些特殊性质 比如 费用函数c往往具有三角不等式性质 即对任意的3个顶点u v w V 有 c u w c u v c v w 当图G中的顶点就是平面上的点 任意2顶点间的费用就是这2点间的欧氏距离时 费用函数c就具有三角不等式性质 对于给定的无向图G 可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法 voidapproxTSP Graphg 1 选择g的任一顶点r 2 用Prim算法找出带权图g的一棵以r为根的最小生成树T 3 前序遍历树T得到的顶点表L 4 将r加到表L的末尾 按表L中顶点次序组成回路H 作为计算结果返回 当费用函数满足三角不等式时 算法找出的旅行售货员回路的费用不会超过最优旅