离散最优化算法

图书标准信息

• 作者 刘振宏、马绍汉 著
• 出版社 科学出版社
• 出版时间 2012-11
• 版次 1
• ISBN 9787030359490
• 定价 45.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 233页
• 字数 340千字
• 正文语种 简体中文

【内容简介】

　　最优化算法是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.60-1规划的隐数法（implicitentimeration）
习题
参考文献

第三章网络规划
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.4NP-完全问题的证明举例
7.5关于NP-完全性的另一些概念
7.5.1Co-NP类
7.5.2NP-hard类
7.5.3伪多项式算法与强NP-完全性
习题
参考文献

第八章近似算法及其分类
8.1近似算法的基本概念
8.2非空闲策略
8.3Greedy算法
8.4局部搜索
8.5基于线性规划的近似算法
8.6基于动态规划的近似算法
8.7绝对近似类
8.8相对近似类
8.9PTAS类与FPTAS类
8.10随机近似算法
8.11近似算法的概率分析
习题
参考文献