（注意：本文件的显示、打印需要公式编辑器的支持。）
工 程 数 学
山东大学软件学院 2011年7月
I
前 言
先修课程要求：高等数学、离散数学、数据结构
课程内容与学时分配： 1．运筹学 共14学时 线性规划 6学时 整数规划 2学时 动态规划 4学时 网络分析 2学时 2．组合数学 共12学时
排列组合 2学时 鸽巢原理及应用 2学时 容斥原理及其应用 2学时 母函数方法 2学时 递推关系 2学时 Polya 计数定理 2学时
参考文献:
1. 刁在筠等，运筹学，高等教育出版社，2001 2. 叶惠民，工程数学，东南大学出版社，2003
3. 邹述超，概率论与数理统计，高等教育出版社，2003
4. Richard A. Brualdi, Introductory Combinatorics, Printice Hall, Inc., 1999
5. 卢开澄，组合数学，清华大学出版社，1999 6. 曹汝成，组合数学，华南理工大学出版社，2000 7. 朱大铭，算法设计与分析，高教出版社。
II
目 录
第一篇 运筹学 .............................................................................................. 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 第七章 母函数与递推关系 ................................................................ 75
§1 用母函数解递推关系 ................................................................ 75 §2 用母函数解整数拆分问题 ........................................................ 80 §3 用指数型母函数解错排问题 .................................................... 83
III
第八章 Polya 计数定理 ..................................................................... 86
§1 Burnside引理 ............................................................................ 86 §2 Polya定理 .................................................................................. 93
IV
前 言
本文只是部分运筹学与组合数学的摘要汇编，在缺少讲解的情况下，可能需要读者查阅其他教材或文献以了解详细内容。
第一篇 运筹学
第一章 线性规划 §1 线性规划问题及数学模型
生产及生活中有一大批问题的数学模型可以用相对简单的线性方程组表示出来。由下面的两个例子，理解这类问题的相似结构，进而总结线性规划问题的一般模型，给出常用解法。
例1 设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨。已知不同地点间每吨运费如下表所示，运费与运量成正比，求解运费最省的供给方案。
运 产 地 费 销 地 A 21 51 B 25 51 C 7 37 D 15 15 甲 乙 解：设甲、乙运往A、B、C、D的物资量分别为x11, x12, x13, x14, x21, x22, x23, x24吨，则由题意，我们需要去求
1