组合最优化

课程编码：180080070105M2002H 英文名称：Combinatorial Optimization 课时：40 学分：2.00 课程属性：专业核心课 主讲教师：郭田德

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

线性代数、 线性规划、图论与网络优化、概率论基础

第一章 引言 2.0学时 郭田德
第1节 概述
第2节 什么是组合最优化
第3节 组合最优化与计算机数学
第4节 组合最优化与计算机通讯网络
第5节 组合最优化与管理科学
第6节 组合最优化问题的研究方法
第二章 预备知识 2.0学时 郭田德
第1节 图论与网络优化
第2节 几种规划之间的关系
第3节 最优化问题
第4节 邻域
第三章 算法与计算复杂性 4.0学时 郭田德
第1节 两个典型问题
第2节 计算复杂性的概念
第3节 算法及复杂性
第4节 多项式时间算法与指数时间算法
第四章 线性规划 4.0学时 郭田德
第1节 线性规划问题及其基本性质
第2节 线性规划问题的基本定理
第3节 线性规划问题的单纯形算法
第4节 线性规划的对偶理论
第5节 多面体组合学
第五章 线性规划问题的原始-对偶算法 4.0学时 郭田德
第1节 算法的基本思路
第2节 原始－对偶算法
第3节 算法初始可行解的求法
第4节 算法的几点说明
第六章 组合优化问题的原始－对偶算法 6.0学时 郭田德
第1节 最短路问题的原始－对偶算法
第2节 最大流问题的原始－对偶算法
第3节 最小费用流问题的原始－对偶算法
第4节 Hitchcock问题的原始－对偶算法
第七章 组合优化问题的有效算法 6.0学时 郭田德
第1节 几个重要算法的计算复杂度讨论
第2节 最大流问题的有效算法
第3节 最优匹配问题的有效算法
第4节 赋权匹配问题的有效算法
第八章 整数规划 4.0学时 郭田德
第1节 有理多面体
第2节 多胞形的整数闭包
第3节 单位模矩阵
第4节 全单位模性质
第5节 全对偶整性
第6节 割平面
第7节 拉格朗日松弛
第九章 NP-难组合优化问题的研究方法 4.0学时 郭田德
第1节 最优化方法
第2节 近似算法
第3节 近似方案
第4节 启发式算法
第十章 拟阵 4.0学时 郭田德
第1节 独立系统与拟阵
第2节 拟阵公理
第3节 贪婪算法
第4节 拟阵划分
第5节 拟阵交

略