§4.2偶遇问题 §4.3夫妇问题 §4.4由子集系生成的布尔代数 §4.5线性不等式的 Renyi方法 §4.6 Poincare公式 §4.7 Bonferroni不等式 §4.8 Ch.Jordan公式 §4.9积和式 第五章Stirling数 §5.1 第二类Stirling数S(n,k)和集合的划分 §5.2 S(n,k)的发生函数 §5.3 S(n,k)间的递推关系 §5.4划分数或n个元素集合的等价关系数?(n) 掌握第一类Stirling数及其递推关系 传统讲授 4 8 掌握第二类Stirling数及其递推关系 传统讲授 4 8 掌握布尔代数及相关结论 传统讲授 4 8 §5.5 第一类Stirling数s(n,k)及其发生函数 §5.6 s(n,k)的递推关系 §5.7 s(n,k)的值 §5.8同余问题 第六章 置换 §6.1对称群 §6.2有关循环分解的计数问题；再论一类Stirling数 §6.3多重置换 §6.4 [n]的置换的逆序 §6.5由升数确定的置换；Eulerian数 §6.6置换群；循环指标多项式；Burnside定理 §6.7 Polya定理 第七章 不等式与估计的范例 . §7.1 组合序列的凸性和单峰性 §7.2 Sperner系 §7.3 N上2阶正则图计数的渐近研究 §7.4 随掌握置换及其相关理论 传统讲授 4 8 掌握Polya定理 传统讲授 4 8 掌握各种范例 传统讲授 4 8 机变换 §7.5 Ramsey定理 §7.6 二元Ramsey数
学习参考书（注明编者，出版社，出版时间及版次）：
[1] Louis Comtet（谭明术等译）, 高等组合学，大连理工大学出版社1991 第一版 [2] 卢开澄，组合数学，清华大学出版社
[3] J.H. Van Lint, R.M.Wilson, A course in combinatorics, 机械工业出版社
《线性与整数规划》课程教学大纲
撰 写 人：方奇志
撰写时间：2007 年07月28日 开课院系：数学系 课程编号：100K0047
课程英文名称：Linear and Integer Programming 拟授课教师：方奇志
课程总学时: 192 总学分：3 课内学时：64 课外学时：128 课程教学目标与基本要求：
本课程是硕士学位基础课。线性与整数规划是运筹学和最优化理论的重要组成部分，在工业、军事、经济管理等领域有广泛的应用。本课程主要介绍线性规划和整数规划的理论、算法及若干应用专题。线性规划部分包括多面体理论、对偶理论、单纯形法、对偶单纯形法、原始对偶算法和若干算法上的新进展；整数线性规划部分包括割平面法、分枝定界法、动态规划算法以及相应的理论；应用专题包括运输与指派问题、对策论中的线性规划算法等。
通过本课程的学习，要求学生掌握线性和整数规划的基本理论和基本算法，了解与该课程内容相关的最新理论进展，为硕士阶段的后续课程的学习打好理论基础；同时，在所学的基本理论和方法基础上，提高建立模型和分析问题的水平和能力。 教学方式：讲授与讨论结合
考核方式及学生成绩计算方式和方法：平时作业和期末开卷考试结合；为100分制：平时作
业占30分，期末开卷考试占70分。
课程内容及详细教学计划：
授课内容 教学目标 章、节 授课内容 本章的教学目标是使学生掌握线性规划的单纯形方法，和相关的算法理论，特别是线性规划的基本 学时分配 授课模式 课内课外学时 学时 16 32 6 第一章 线性规划及其单纯形法 第一节 线性规划模型、线性规划的几何 §1.1 §1.2 线性规划模型的形式 线性规划的几何意义 传统讲授 3 2 1 第二节 线性规划基本定理和单纯形法 传统讲授 5 10 §2.1 §2.2 §2.2 基本可行解 线性规划的基本定理 单纯形法的基本思想和步骤 定理和单纯形法的几何意义。为学生理解后续的规划理论提供支持。 1 2 2 8 8 第三节 单纯形法的几何意义证明 第四节 反循环法则 §4.1 §4.2 字典序反循环法则 Bland反循环法则 对偶理论是线性规划的中心理论，本章内容的掌握对线性规划方法在实际中的应用有非常重要的意义。本章的教学目标是使学生深入理解线性规划对偶理论，其几何意义及初步的应用。 传统讲授 4 传统讲授 4 2 2 10 第二章 线性规划对偶理论 第一节 对偶定理及对偶应用实例 §1.1 §1.2 §1.3 §1.4 §1.5 对偶的基本概念 弱对偶定理和强对偶定理 互补松弛性 Farkas引理及其几何意义 最短路问题及其对偶 20 14 传统讲授 7 2 2 1 1 1 第二节 对偶单纯形法 §2.1 §2.2 对偶单纯形法 对偶单纯形法与单纯形法的对应 传统讲授 3 2 1 8 6 第三章 单纯形法的进一步讨论 第一节 单纯形法的进一步讨论 §1.1 §1.2 §1.3 修正单纯形法 列生成法及应用实例 最大流问题及用列生成方法求解 第二节 Dantzig-Wolfe分解算法 §2.1 §2.2 分解算法的基本思想和步骤 分解算法应用实例 修正单纯形法和分解算法是单纯形方法在各种组合优化问题算法设计中的应用以及在实际中的应用形式。本章的教学目标是介绍这些方法，使学生接触线性规划在实际中的应用。 原始-对偶算法思想是各种网络优化问题和组合优化问题算法设计中最重要的方法之一。本章的教学目标是使学生了解原始-对偶算法的基本思想，和这种方法在网络算法设计中的作用。 16 8 传统讲授 4 1 2 1 4 2 2 10 8 第四章 原始-对偶算法 第一节 原始-对偶算法 §1.1 §1.2 §1.3 原始-对偶算法的基本思想和说明 最短路问题的原始对-偶算法 最大流问题的原始-对偶算法 20 8 传统讲授 4 2 1 1 第二节 最短路和最大流问题算法 §2.1 §2.2 §2.3 最短路问题的Dijkstra算法 最大流最小截定理 最大流问题的Ford-Fulkerson算法 讨论报告 6 2 2 2 12 第五章 整数线性规划 第一节 整数线性规划一般形式 §1.1 §1.2 整数线性规划模型举例 全单模性质 第二节 整数规划的割平面法 §2.1 §2.2 §2.3 Gomory割 字典序 分数割平面法的有限性 割平面法、动态规划方法和分枝定界法是求解整数线性规划的最重要的方法。本章的教学目标是使学生掌握整数线性规划的基本应用模型和算法理论等。 12 24 4 传统讲授 2 1 1 传统讲授 4 1 1 2 8 第三节 分枝定界法 第四节 动态规划方法 第五章 应用专题 第一节 运输问题 §1.1 §1.2 运输问题模型及其算法 运输问题模型的推广 本章的教学目标是使让使学生了解线性规划方法在其他领域的应用，如物流、对策论等，加强学生对线性规划方法的理解，为以后的应用研究提供方向。 讨论报告 2 传统讲授 4 8 4 8 16 8 讨论报告 4 2 2 第二节 对策论中的线性规划算法 §2.1 §2.2 矩阵对策中的线性规划对偶算法 合作对策模型中线性规划方法应用 讨论报告 4 2 2 8 参考书目
[1] 束金龙、闻人凯. 线性规划理论与模型应用（国家理科基地教材/数学核心教程系列）.
科学出版社，2003年。
[2] C.H. Papadimitriou, K. Steiglitz（美）著，刘振宏，蔡茂诚译.组合最优化：算法
和复杂性.清华大学出版社，1988年。
[3] Laurence A. Wolsey（美）著.Integer Programming. John Wiley & Sons Inc, 1998. [4] Leonid Nison Vaserstein,Christopher Cattelier Byrne（美）著，谢金星、姜启源、张立平译.
线性规划导论（华章数学译丛）. 机械工业出版社, 2006年.
[5] Wayne L.Winston（美）著. Operations Research:Applications and Algorithms（中文书名：
运筹学：数学规划，国外大学优秀教材——工业工程系列（影印版））. 清华大学出版社，2004年。
[6] Robert J. Vanderbei（美）著. Linear Programming.--- Foundations and Extensions.
KluwerAcademic Publishers，2001.