运筹学

课程编码：180080070100M1002H 英文名称：Operations Research 课时：40 学分：2.00 课程属性：学科核心课 主讲教师：胡旭东

本课程为数学学科各专业博士、硕士研究生的学科基础课，同时也可作为管理科学专业研究生的选修课。本课程主要内容涉及运筹学若干主要分支的数学理论基础。通过本课程的学习，希望学生能掌握运筹学主要分支的基本模型、理论和算法。同时也希望通过一些案例教学，让学生对运筹学的框架和实质有所了解，为进一步学习和应用运筹学、从事运筹学的各分支的研究打下基础。

数学分析，线性代数

第一章 线性规划 7学时 胡旭东
第1节 凸分析初步(凸集，最短距离引理，分离引理，支撑定理，Farks定理)
第2节 单纯形算法和对偶理论
第3节 线性规划应用（运输问题，指派问题，最大流问题，最小费用问题）
第二章 博弈论 7学时 胡旭东
第1节 零和博弈（鞍点，纯策略，混合策略，占优策略，极小极大定理）
第2节 非零和博弈（纳什均衡，纳什定理，囚徒两难，夫妻之战）
第3节 稳定匹配（稳定匹配，沙普利算法）
第4节 公平分配（所罗门判案，塔木德方案）
第三章 非线性规划 11学时 胡旭东
第1节 凸分析初步(凸函数，方向导数，次梯度，最优性条件)
第2节 无约束优化的最优性条件（一阶条件，二阶条件）
第3节 有约束优化的最优性条件（不等式约束，KKT-条件，对偶定理）
第4节 无约束优化的算法（线搜索，点集映射，最速下降法，牛顿法，共轭方向法）
第5节 有约束优化的算法（罚函数法，可行方向法，梯度投影法）
第四章 计算复杂性 4学时 胡旭东
第1节 图灵机（确定型，非确定型，停机定理）
第2节 计算复杂性分类（P问题，NP问题，NP-C问题，NP-难问题，库克定理）
第五章 组合优化算法设计与分析 11学时 胡旭东
第1节 分而治之法（搜索，排序，旅行商问题）
第2节 动态规划法（最短路，三角剖分、背包）
第3节 分支定界法（整数线性规划、旅行商、工件排序）
第4节 贪婪算法（最小生成树、最大可满足、背包、顶点覆盖、独立集、旅行商）
第5节 整数规划方法（顶点覆盖、最大可满足、最大割）
第6节 在线算法（页面调度、k-服务器、工件排序、装箱）

略