工程数学-2010.doc

注意：本文件的显示、打印需要公式编辑器的支持工　程　数　学山东大学软件学院二O一O年九月前　　言先修课程要求：高等数学、离散数学、数据结构课程内容与学时分配： 1．运筹学 共14学时线性规划 6学时整数规划 2学时动态规划 4学时网络分析 2学时2．组合数学 共12学时排列组合 　 2学时鸽巢原理及应用 2学时容斥原理及其应用 2学时母函数方法　　　 2学时递推关系 2学时Polya 计数定理 2学时参考文献:1. 刁在筠等，运筹学，高等教育出版社，20012. 叶惠民，工程数学，东南大学出版社，20033. 邹述超，概率论与数理统计，高等教育出版社，20034. Richard A. Brualdi, Introductory Combinatorics, Printice Hall, Inc., 19995. 卢开澄，组合数学，清华大学出版社，19996. 曹汝成，组合数学，华南理工大学出版社，20007. 朱大铭，算法设计与分析，高教出版社目　　录第一篇 运筹学 1第一章 线性规划 1§1　线性规划问题及数学模型 1§2　图解法 7§3　单纯形法解LP问题 9§4　对偶线性规划 14第二章 整数规划 18§1　整数线性规划问题 18§2　整数线性规划问题解法 20第三章 动态规划 22§1　最优化原理 22§2　用最优化原理解非线性规划问题 23§3　动态规划算法设计 26第四章 网络分析 33§1　图及网络 33§2　网络上的优化问题 34第二篇　组合数学 46第五章 排列组合 46§1　和、积的原则 46§2　排列 47§3　重复排列 49§4　组合 54§5　组合等式及意义 57§6　排列与组合的生成 57第六章 容斥原理与鸽巢原理 60§1　容斥原理 60§2　鸽巢原理 65§3　有重复元素的圆排列问题 69第七章 母函数与递推关系 74§1　用母函数解递推关系 74§2　用母函数解整数拆分问题 79§3　用指数型母函数解错排问题 82第八章 Polya 计数定理 85§1　Burnside引理 85§2　Polya定理 9198前 言本文只是部分运筹学与组合数学的摘要汇编，在缺少讲解的情况下，可能需要读者查阅其他教材或文献以了解详细内容。

第一篇 运筹学第一章 线性规划§1　线性规划问题及数学模型生产及生活中有一大批问题的数学模型可以用相对简单的线性方程组表示出来由下面的两个例子，理解这类问题的相似结构，进而总结线性规划问题的一般模型，给出常用解法例1　设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨已知不同地点间每吨运费如下表所示，运费与运量成正比，求解运费最省的供给方案地产费运地销ABCD甲21 25 7 15乙51 5137 15解：设甲、乙运往A、B、C、D的物资量分别为x11, x12, x13, x14, x21, x22, x23, x24吨，则由题意，我们需要去求21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24的最小值显然x11, x12, x13, x14, x21, x22, x23, x24不能任意取值，我们还有“甲地调出物资2000吨”、“供给A地1700吨”等条件限制总结需求及条件限制，得到下面的完整数学模型：该模型的现实含意为：在x11+x12+x13+x14 = 2000等条件下，求f = 21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24的最小值。

这里先做出数学模型，以后再考虑求解方法)例2　某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3已知单位产品需要的原料数、单位产品的利润、原料总量等条件如下表所示，制定出总利润最大的生产计划需原料kg单位产品所原料品产Q1 Q2 Q3原料可用量（kg /日）P12301500P2024800P33252000单位产品利润(千元)354解：设三种产品的生产量分别为x1, x2, x3时可以得到最大利润3x1+5x2+4x3，则由题意，我们可以得到完整的模型为总结这两个例子，可以看到其共同点：都是在对未知量做出线性约束的前提下，求未知量线性组合的最值我们将最大、最小值统一为最小值，假设线性约束有等式、有不等式，未知量有些必须非负、有些不受限制，可以得到下面的一般线性规划模型：线性规划（LP）问题的一般形式（等式不都在前面怎么办？非负变量不都在前面怎么办？调一调LP模型中的术语：目标函数(指标函数、指标)：　价值系数：　，　价值向量：　决策变量：　，　决策向量：　上述记法可以使指标写成：约束：约束矩阵：右端向量：　非负约束：　自由变量：　可行解、可行点：　即满足约束的点，也就是满足约束的一组未知量的取值，该组值不一定能使得指标达到最小值。

可行域D：可行解集合最优解：使得指标最小的可行解(不一定唯一，甚至不一定存在)利用上面的一些记法，在某些条件下，可以得到LP模型的特殊形式，至少在形式上显得简炼一些，实际上今后的许多分析是基于这些简炼形式的LP问题的规范形式一般形式中p=0, q=n 时，称为规范形式一般形式与规范形式的转化将化为令例：将下面的线性规划转化为规范形式解：，，，，LP问题的标准形式一般形式中p=m, q=n 时，称为标准形式一般形式与标准形式的转化对，，令这里的称为剩余变量例：将下面的线性规划转化为标准形式解：，§2　图解法例1　用图解法解线性规划x1+x2=5x1-2x2=22x1-x2=-2-x1+x2=0(5,0)(0,5)(2,0)(0,-1)x1x2(0,2)(-1,0)z在(1,4)点达到最大值3例2　用图解法解线性规划x1+2x2=8x1-x2=4x1-5x2=0(4,0)(0,-4)x1x2(0,4)(8,0)例3　用图解法解线性规划无最优解关于可行域D与最优解的讨论：D＝Ø，无解、不可行；D≠Ø，无界；D≠Ø，有最优解§3　单纯形法解LP问题1．单纯形方法考虑标准形式的LP问题设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　对偶线性规划1．对偶线性规划 是约束矩阵A的第i行，Aj是约束矩阵A的第j列规范形式的对偶问题为标准形式的对偶问题为2．对偶理论定理　如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解值相等。

定理　对偶的对偶为原始的LP问题3．对偶LP的来历将一般形式化为标准形式，其中，，，，令，则改写为，即，展开为，　　　第二章 整数规划§1　整数线性规划问题要求变量值取整数值的线性规划问题称为整数线性规划，其中变量只取0或1的线性规划称为0-1规划投资决策问题　总金额B万元，n个项目，第j项目所需资金bj，利润cj，应该选哪些项目使总利润最大房产投资　地产面积3000 M2，甲类房产每幢250M2，可收利润10万元，可建设不超过8幢，乙类房产每幢400M2，可收利润20万元，可建设不超过4幢，应该建设甲乙各几幢使得利润最大？货朗问题　从v0出发，恰好经过v1，v2，…，vn　各一次回到v0，从vi到vj路程为dij，（dii＝M充分大），怎么走最近？背包问题　n个物品，体积分别为v1，v2，…，vn，价值分别为p1，p2，…，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高例：1) V=100, v1=p1=49, v2=p2=51, v3=p3=522) V=100, v1=p1=49, v2=p2=51, v3=52, p3=52.1算法：穷举，共2n种物品的组合。

§2　整数线性规划问题解法1． 图解法图解法求解下面的ILP问题2． 分枝定界法(1.5, 2.5)　　　　　(1, 1.5)(2, 1.5)第三章 动态规划动态规划是多阶段决策问题，相对地，线性规划、非线性规划问题称为静态规划问题§1　最优化原理全局最优，则局部最优如何理解）最短路问题cb72436471②32①5164⑤38u0③⑥⑦2④edagf货郎问题设表示从vi出发，经过V中的所有点恰一次后回到v0的最佳路线总长度，则所求的就是例：§2　用最优化原理解非线性规划问题就下面的非线性规划问题，讨论最优化原理解题思想，并具体求解该题解得：，故§3　动态规划算法设计填表的思想及优势fn=fn-。