组合最优化  012M1007H

学期:2017—2018学年(春)第二学期 | 课程属性:一级学科核心课 | 任课教师:郭田德
授课时间: 星期四, 第1、2节
授课地点: 教1-405
授课周次: 1、2、3、4、5、6、7、8、9、10、11、12
授课时间: 星期二, 第1、2节
授课地点: 教1-405
授课周次: 1、2、3、4、5、6、7、8、9、10、11、12
课程编号: 012M1007H 课时: 40 学分: 2.0
课程属性: 一级学科核心课 主讲教师:郭田德
英文名称: Combinatorial Optimization

教学目的、要求

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

预修课程

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

教 材

C.H.Papdimitriou &K.Steiglitz, “Combinatorial Optimization -Algorithm and Complexity”

主要内容

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

参考文献

[1] Alexander Schrijver, “A Course in Combinatorial Optimization” 
[2]W. J. Cook,W.H.Cunningham,W.R.Pulleyblank &A. Schrijver, “Combinatorial Optimization ”