工程数学-201009.docVIP

（注意：本文件的显示、打印需要公式编辑器的支持。） 工　程　数　学 山东大学软件学院 二OO年月 : 刁在筠等，运筹学，高等教育出版社，2001 叶惠民，工程数学，东南大学出版社，2003 邹述超概率论目　　录 第一篇 运筹学 1 第一章 线性规划 1 §1　线性规划问题及数学模型 1 §2　图解法 7 §3　单纯形法解LP问题 9 §4　对偶线性规划 14 第二章 整数规划 18 §1　整数线性规划问题 18 §2　整数线性规划问题解法 19 第三章 动态规划 21 §1　最优化原理 21 §2　用最优化原理解非线性规划问题 23 §3　动态规划算法设计 25 第四章 网络分析 32 §1　图及网络 32 §2　网络上的优化问题 33 第二篇　组合数学 45 第五章 排列组合 45 §1　和、积的原则 45 §2　排列 46 §3　重复排列 48 §4　组合 53 §5　组合等式及意义 56 §6　排列与组合的生成 56 第六章 容斥原理与鸽巢原理 59 §1　容斥原理 59 §2　鸽巢原理 64 §3　有重复元素的圆排列问题 68 第七章 母函数与递推关系 73 §1　用母函数解递推关系 73 §2　用母函数解整数拆分问题 78 §3　用指数型母函数解错排问题 81 第八章 Polya 计数定理 84 §1　Burnside引理 84 §2　Polya定理 90 前 言 本文只是部分运筹学与组合数学的摘要汇编，在缺少讲解的情况下，可能需要读者查阅其他教材或文献以了解详细内容。 运筹学 线性规划 §1　线性规划问题及数学模型 该模型的现实含意为：在x11+x12+x13+x14 = 2000等条件下，求 f = 21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24 的最小值。(这里先做出数学模型，以后再考虑求解方法) 例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 解：设三种产品的生产量分别为x1, x2, x3时可以得到最大利润3x1+5x2+4x3，则由题意，我们可以得到完整的模型为 总结这两个例子，可以看到其共同点：都是在对未知量做出线性约束的前提下，求未知量线性组合的最值。我们将最大、最小值统一为最小值，假设线性约束有等式、有不等式，未知量有些必须非负、有些不受限制，可以得到下面的一般线性规划模型： 线性规划（LP）问题的一般形式 （等式不都在前面怎么办？非负变量不都在前面怎么办？调一调。） LP模型中的术语： 目标函数(指标函数、指标)：　 价值系数：　，　价值向量：　 决策变量：　，　决策向量：　 上述记法可以使指标写成： 约束： 约束矩阵： 右端向量：　 非负约束：　 自由变量：　 可行解、可行点：　即满足约束的点，也就是满足约束的一组未知量的取值，该组值不一定能使得指标达到最小值。 可行域D：可行解集合 最优解：使得指标最小的可行解(不一定唯一，甚至不一定存在)。 利用上面的一些记法，在某些条件下，可以得到LP模型的特殊形式，至少在形式上显得简炼一些，实际上今后的许多分析是基于这些简炼形式的。 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问题有可行解，则必有基本可行解；若有最优解，则