组合最优化

课程编码：071100M01004H 英文名称：Combinatorial Optimization 课时：40 学分：2.00 课程属性：一级学科核心课 主讲教师：郭田德

组合优化是应用数学和组合领域的新兴学科，它由线性规划、算法理论、组合数学发展而来，目的是解决离散结构的最优化问题。在本门课程中，我们主要讲授组合优化中的一些重要思想、理论结果和算法。本课程为运筹学与控制论学科博士和硕士生而设立的专业基础课，同时也可作为管理科学、计算机科学与技术和数学学科的博士和硕士研究生的选修课。通过本课程的学习, 希望学生除了掌握一些基本方法和技巧之外, 对组合优化的近代发展和研究趋向有所了解, 为进一步从事专业研究打下基础。

线性代数、 线性规划、概率论基础

第一章 引言 2学时
第1节 概述
第2节 什么是组合最优化
第3节 组合最优化与计算机数学
第4节 组合最优化与计算机通讯网络
第5节 组合最优化与管理科学
第6节 组合最优化问题的研究方法
第二章 预备知识 2学时
第1节 图论与网络优化
第2节 几种规划之间的关系
第3节 最优化问题
第4节 邻域
第三章 算法与计算复杂性 4学时
第1节 两个典型问题
第2节 计算复杂性的概念
第3节 算法及复杂性
第4节 多项式时间算法与指数时间算法
第四章 多面体、多胞形、Fakars引理、线性规划 6学时
第1节 多面体
第2节 多胞形的基本概念
第3节 Fakars引理的各种形式
第4节 线性规划问题的历史
第5节 线性规划问题的几何解释
第6节 线性规划的基本定理
第7节 线性规划问题的单纯形算法
第8节 线性规划的对偶理论
第9节 线性规划的原始－对偶算法
第五章 组合优化问题的原始－对偶算法 6学时
第1节 最短路问题的原始－对偶算法
第2节 最大流问题的原始－对偶算法
第3节 最小费用流问题的原始－对偶算法
第4节 Hitchcock问题的原始－对偶算法
第六章 组合优化问题的有效算法 6学时
第1节 几个重要算法的计算复杂度讨论
第2节 最大流问题的有效算法
第3节 最优匹配问题的有效算法
第4节 赋权匹配问题的有效算法
第七章 多面体组合学 4学时
第1节 多面体
第2节 多胞形及其性质
第3节 有理多面体
第4节 有理多面体是整的充分必要条件
第5节 单位模矩阵
第6节 全单位模性质
第7节 全对偶整性
第8节 割平面
第八章 旅行售货商问题 4学时
第1节 旅行售货商问题（TSP）及其求解算法
第九章 拟阵 4学时
第1节 最小支撑树与Greedy算法
第2节 拟阵基本概念
第3节 拟阵与组合最优化问题
第十章 NP和NP－完备性 2学时
第1节 NP－完备性理论概述
第2节 判定问题与语言
第3节 算法的严格定义与P类问题
第4节 NP类问题
第5节 典型的P类问题和NP类问题
第6节 多项式归结和NP完备性
第7节 Cook定理
第8节 六个基本的NP－完备问题
第9节 co－NP类问题

略