运筹与组合-201009.docVIP

（注意：本文件的显示、打印需要公式编辑器的支持。） 运 筹 与 组 合 山东大学学院 二OO年月 : 刁在筠等，运筹学，高等教育出版社，2001 Richard A. Brualdi, Introductory Combinatorics, Printice Hall, Inc., 1999 卢开澄，组合数学，清华大学出版社 朱大铭，算法设计与分析，高教出版社。 目　　录 第一篇 运筹学 1 第一章 线性规划 1 §1　线性规划问题及数学模型 1 §2　图解法 6 §3　单纯形法解LP问题 8 §4　对偶线性规划 13 第二章 整数规划 17 §1　整数线性规划问题 17 §2　整数线性规划问题解法 18 第三章 动态规划 20 §1　最优化原理 20 §2　用最优化原理解非线性规划问题 22 §3　动态规划算法设计 23 第四章 网络分析 30 §1　图及网络 30 §2　网络上的优化问题 31 第二篇　组合数学 43 第五章 排列组合 43 §1　和、积的原则 43 §2　排列 44 §3　重复排列 46 §4　组合 51 §5　组合等式及意义 54 §6　排列与组合的生成 54 第六章 容斥原理与鸽巢原理 57 §1　容斥原理 57 §2　鸽巢原理 62 §3　有重复元素的圆排列问题 66 第七章 母函数与递推关系 71 §1　用母函数解递推关系 71 §2　用母函数解整数拆分问题 76 §3　用指数型母函数解错排问题 79 第八章 Polya 计数定理 82 §1　Burnside引理 82 §2　Polya定理 88 运筹学 线性规划 §1　线性规划问题及数学模型 例2　某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3。已知的条件如下表所示，制定出总利润最大的生产计划。 Q1 Q2 Q3 原料可用量 （kg /日） P1 2 3 0 1500 P2 0 2 4 800 P3 3 2 5 2000 单位产品利润 (千元) 3 5 4 线性规划（LP）问题的一般形式 （等式不都在前面怎么办？非负变量不都在前面怎么办？） 目标函数　 价值系数　，　价值向量　 决策变量　，　决策向量　 约束，约束矩阵 右端向量　 Ax = ? b 非负约束　 自由变量　 可行解、可行点　满足约束的点 可行域D 最优解 LP问题的规范形式 一般形式中p=0, q=n 时，称为规范形式。 一般形式与规范形式的转化 将化为 令 例：将下面的线性规划转化为规范形式 解： ， ，， ， LP问题的标准形式 一般形式中p=m, q=n 时，称为标准形式。 一般形式与标准形式的转化 对 ，， 令 这里的称为剩余变量。 例：将下面的线性规划转化为标准形式 解： ， §2　图解法 z在(1,4)点达到最大值3。 例2　用图解法解线性规划 例3　用图解法解线性规划 无最优解 关于可行域D与最优解的讨论：D＝?，无解、不可行；D≠?，无界；D≠?，有最优解。 §3　单纯形法 设r(A)=m，A的前m列为线性无关。(注意各向量、矩阵的维数) 将A分为左右两块，左边m列为可逆方阵B，右边记为N。(左面m列是不是一定可逆？) 对应将价值向量c和决策向量x的前m行与后n-m行分开， ，， 　　　 ， 令，则 ， 且 。 原LP问题变形为 若取，则得一个满足等式约束的解 ， 其对应的指标值为　　。 B称为基， B的列称为基向量， 称为基本解， 时称为基本可行解，此时B称为可行基 时称为非退化的基本可行解。 下面假设我们要讨论的LP问题对所有的可行基B，都有。 定理　若标准LP问题有可行解，则必有基本可行解；若有最优解，则一定存在一个基本可行解是最优解。(证明略) 定理　若，则是最优解。 证　。 定理　若的第k个分量，且，则该LP问题无界。这里Ak表示矩阵A的第k列。 证　取，（这是一个n维的列向量，第k个分量为1，其余分量为0。）令取(下面说明此x是可行解，且其指标值要多小有多小。) 定理　若的第k个分量，且中存在正分量，则，使得且。 证　令（见前面定理中的定义，这里但不能任意取。） 1）可以适当取使得为可行解： 由 知道； 要使得即，只需 ， 设　由等知道 取即可。 2） 这里，但因为不能任意取大数，所以指标不能任意小。 §4　对偶线性规划 是约束矩阵A的第i行，Aj是约束矩阵A的第j列。 规范形式的对偶问题为 标准形式的对偶问题为 2．对偶理论 定理　如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解值相等。 定理　对偶的对偶为原始的LP问题。 3．对偶LP的来历 将一般形式 化为标准形式，其中 ， ， ， ，令，则改写为 ，即，展开为 ，　　　 整数规划 §1　整数线性规划问题 房产投资　地产面积