离散最优化算法

第一章 线性规划 1.1 线性规划的基本概念 1.2 单纯形算法 1.3 线性规划的对偶理论 1.4 对偶单纯形算法 1.5 原始一对偶算法 1.6 单纯形算法是非多项式算法 1.7 线性规划问题的多项式时间算法 习题 参考文献第二章 整数线性规划 2.1 引言 2.2 分数对偶割平面算法 2.3 整数对偶割平面算法 2.4 混合整数规划的割平面算法 2.5 分支估界算法 2.6 0—1规划的隐数法（implicit entimeration） 习题 参考文献第三章 网络规划 3.1 图的搜索算法 3.1.1 无向图的深探法（DFS） 3.1.2 无向图的广探法（BFS） 3.2 网络流模型及解的整数性 3.3 网络中的最短路 3.3.1 非负权网络的最短路算法 3.3.2 无负回路网络中的最短路算法 3.3.3 所有点对之间的最短路算法 3.4 网络中的最大流 3.4.1 最大流的Ford—Fulkerson算法 3.4.2 最大流的Dinits算法 3.4.3 容量具有上下界的最大流算法 3.4.4 可行性定理及其组合应用 3.5 最小费用流 3.5.1 模型Ⅱ的相继最短路算法 3.5.2 最小费用循环流的平均圈算法 习题 参考文献第四章 树与拟阵 4.1 树的基本性质 4.2 树的中心与重心 4.3 无向网络中的最优生成树 4.4 有向树 4.5 拟阵的基本概念与性质 4.5.1 拟阵的定义与例子 4.5.2 拟阵的～些基本性质 4.6 拟阵与Greedy算法 4.7 拟阵的最大交 4.8 最大权交的算法 习题 参考文献第五章 动态规划 5.1 网络中两点间的最优路问题 5.2 用动态规划方法解某些非线性规划 5.3 用动态规划方法解某些整数规划 5.4 生产计划与资源分配问题 5.4.1 生产计划问题 5.4.2 资源分配问题 5.5 排序问题 5.5.1 排序问题 5.5.2 货郎问题 5.6 矩阵链与公共子序列 5.6.1 矩阵链中矩阵相乘的顺序问题 5.6.2 最长公共子序列问题 习题 参考文献第六章 逆最优化问题 6.1 逆线性规划的一般模型 6.2 在范数l1下式（6.1.5）和式（6.1.6）的解 6.2.1 给定的可行解x0为0—1的解 6.2.2 在范数l1下模型LP2的解 6.3 在范数l∞下式（6.1.5）和式（6.1.6）的解 6.4 组合优化的逆问题一般模型 6.5 各种逆最优化问题的归结 6.6 瓶颈扩张问题的一例 习题 参考文献第七章 算法、复杂性与NP—完全理论 7.1 问题、算法与复杂性 7.2 多项式算法P类和NP类 7.3 多项式变换与NPC类 7.4 NP—完全问题的证明举例 7.5 关于NP—完全性的另一些概念 7.5.1 Co—NP类 7.5.2 NP—hard类 7.5.3 伪多项式算法与强NP—完全性 习题 参考文献第八章 近似算法及其分类 8.1 近似算法的基本概念 8.2 非空闲策略 8.3 Greedy算法 8.4 局部搜索 8.5 基于线性规划的近似算法 8.6 基于动态规划的近似算法 8.7 绝对近似类 8.8 相对近似类 8.9 PTAS类与FPTAS类 8.10 随机近似算法 8.11 近似算法的概率分析 习题 参考文献

最优化算法是20世纪中叶发展起来的一门学科，既有久远的历史渊源，又有广阔的应用前景。在计算机时代，最优化算法更呈现出异彩纷呈的发展态势。刘振宏、马绍汉编著的《离散最优化算法》共八章，前四章介绍最优化算法的经典内容，后四章包含了最优化算法近年来的发展，如逆最优化问题和近似算法。书中还讲述了作者在组合优化领域所做的创造性的工作。为便于消化和理解书中的内容，每章末附有习题和参考文献。《离散最优化算法》可作为高等院校运筹学与控制论、计算机应用、系统工程等学科的高年级本科生、研究生的教材，也可供从事这方面工作的科技工作者参考。