离散最优化算法 PDF 591304版

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

目录

• 第一章 线性规划
• 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 近似算法的概率分析
• 习题
• 参考文献