作者：谢政著
页数：312
出版社：科学出版社
出版日期：2017
ISBN：9787030409522
电子书格式：pdf/epub/txt
内容简介
本书全面系统地介绍了网络最优化中的基本问题和基本算法以及计算复杂性的基本内容和近似算法。取材恰当，叙述清晰，论证严谨，深入浅出。 全书共十二章，分为两部分：第一部分包括前十章，主要介绍最小树，最小树形图，最短路，最大流，最小费用流，最大匹配，最大权匹配和中国邮递员问题等基本问题的各种多项式算法，以及线性规划、整数线性规划的基本理论；第二部分包括后两章，讨论计算复杂性中的基本概念，NP完全理论及重要的NP完全问题，还介绍了装箱问题，平行机排序问题，旅行商问题，背包问题等NP难问题的近似算法。 本书可作为运筹学专业研究生教材，也可供应用数学、系统科学、管理科学、计算机科学和军事运筹学等有关专业的教师、研究生和大学高年级学生参考。
本书特色
本书全面系统地介绍了网络第一化中的基本问题和基本算法以及计算复杂性的基本内容和近似算法。取材恰当，叙述清晰，论证严谨，深入浅出。《BR》 全书共十二章，分为两部分：最部分包括前十章，主要介绍最小树，最小树形图，最短路，第一流，最小费用流，第一匹配，第一权匹配和中国邮递员问题等基本问题的各种多项式算法，以及线性规划、整数线性规划的基本理论；第二部分包括后两章，讨论计算复杂性中的基本概念，NP完全理论及重要的NP完全问题，还介绍了装箱问题，平行机排序问题，旅行商问题，背包问题等NP难问题的近似算法。
目录
《运筹与管理科学丛书》序前言第1章 图与算法 1.1 图的基本概念 1.2 有向图的基本概念 1.3 几类重要的图 1.4 图与网络的表示形式 1.5 网络最优化问题 1.6 算法及其复杂性 1.7 排序算法 习题1第2章 最小树 2.1 树的基本性质 2.2 最小树的基本性质 2.3 求最小树的算法 2.4 最小度限制树 2.5 支撑树的排序.
2.6 过指定顶点的最小单圈子图 习题2第3章 最小树形图 3.1 有根图 3.2 树形图 3.3 求最小树形图的朱刘算法 3.4 分枝 习题3第4章 线性规划 4.1 线性规划问题及其对偶规划问题 4.2 整数线性规划与全单位模矩阵 4.3 关联矩阵的一些性质 4.4 网络最优化问题的线性规划模型 习题4第5章 最短路 5.1 引言 5.2 最短路方程 5.3 无回路网络中最短路的拓扑排序法 5.4 非负权网络中最短路的Dijkstra算法 5.5 解最短路问题的Ford算法 5.6 求所有顶点之间最短路的Floyd算法 5.7 回路的检测 5.8 第2最短路 5.9 最短路算法的应用 习题5第6章 最大流 6.1 流与截 6.2 Ford Fulkerson算法 6.3 最短增广链算法 6.4 预流推进算法 6.5 双容量网络流 习题6第7章 最小费用流 7.1 负费用回路算法 7.2 最小费用路算法 7.3 原始对偶算法 7.4 最小平均费用回路算法 7.5 求最小费用循环流的状态算法 7.6 最小凸费用流和最小凹费用流 习题7第8章 二部图的匹配 8.1 图的匹配 8.2 求二部图中最大匹配的算法 8.3 求赋权二部图中最大权匹配的算法 8.4 最大最小匹配 习题8第9章 一般图的匹配 9.1 交错树 9.2 求最大匹配的花算法 9.3 求最大权匹配的原始对偶算法 习题9第10章 中国邮递员问题 10.1 Euler闭迹 10.2 有向Euler闭迹 10.3 赋权图上的邮递员问题 10.4 赋权有向图上的邮递员问题 10.5 赋权混合图上的邮递员问题 习题10第11章 NP完全理论 11.1 最优化问题的判定形式 11.2 P类与NP类 11.3 NP完全类与c00k定理 11.4 c0一NP类 11.5 六个基本的NP完全问题 11.6 NP完全性证明技术 11.7 更多的NP完全问题 11.8 NP难问题 习题11第12章 近似算法 12.1 近似算法的性能 12.2 装箱问题 12.3 平行机排序问题 12.4 旅行商问题 12.5 背包问题 12.6 一些否定结果 习题12参考文献索引《运筹与管理科学丛书》已出版书目
2.6 过指定顶点的最小单圈子图 习题2第3章 最小树形图 3.1 有根图 3.2 树形图 3.3 求最小树形图的朱刘算法 3.4 分枝 习题3第4章 线性规划 4.1 线性规划问题及其对偶规划问题 4.2 整数线性规划与全单位模矩阵 4.3 关联矩阵的一些性质 4.4 网络最优化问题的线性规划模型 习题4第5章 最短路 5.1 引言 5.2 最短路方程 5.3 无回路网络中最短路的拓扑排序法 5.4 非负权网络中最短路的Dijkstra算法 5.5 解最短路问题的Ford算法 5.6 求所有顶点之间最短路的Floyd算法 5.7 回路的检测 5.8 第2最短路 5.9 最短路算法的应用 习题5第6章 最大流 6.1 流与截 6.2 Ford Fulkerson算法 6.3 最短增广链算法 6.4 预流推进算法 6.5 双容量网络流 习题6第7章 最小费用流 7.1 负费用回路算法 7.2 最小费用路算法 7.3 原始对偶算法 7.4 最小平均费用回路算法 7.5 求最小费用循环流的状态算法 7.6 最小凸费用流和最小凹费用流 习题7第8章 二部图的匹配 8.1 图的匹配 8.2 求二部图中最大匹配的算法 8.3 求赋权二部图中最大权匹配的算法 8.4 最大最小匹配 习题8第9章 一般图的匹配 9.1 交错树 9.2 求最大匹配的花算法 9.3 求最大权匹配的原始对偶算法 习题9第10章 中国邮递员问题 10.1 Euler闭迹 10.2 有向Euler闭迹 10.3 赋权图上的邮递员问题 10.4 赋权有向图上的邮递员问题 10.5 赋权混合图上的邮递员问题 习题10第11章 NP完全理论 11.1 最优化问题的判定形式 11.2 P类与NP类 11.3 NP完全类与c00k定理 11.4 c0一NP类 11.5 六个基本的NP完全问题 11.6 NP完全性证明技术 11.7 更多的NP完全问题 11.8 NP难问题 习题11第12章 近似算法 12.1 近似算法的性能 12.2 装箱问题 12.3 平行机排序问题 12.4 旅行商问题 12.5 背包问题 12.6 一些否定结果 习题12参考文献索引《运筹与管理科学丛书》已出版书目
