网络优化

出版时间：2012-12  出版社：清华大学出版社  作者：博赛卡斯  页数：500  
Tag标签：无  

前言

　　优化问题可分为两种主要类型：连续型和离散型。网络优化就居于这两类问题的分界线上。线性规划和组合优化问题之间存在联系是因为可以将多面体约束集表示为其极点的凸包。当涉及到网络时，由于多面体的极点是整数向量，并且它们所表示的是看上去和线性规划不相干的组合问题的解，上述联系变得紧密得多。正由于这种结构，也由于它们的直观特性，网络模型为解释连续优化和离散优化中的很多基本思想提供了理想的工具。　　网络模型除了具有引人入胜的方法论方面的特点之外，在实践中也被广泛应用，其应用范围还在持续扩大。总体上看确实如此，诸如最短路、指派、最大流、运输、转运、生成树、匹配、旅行商、广义指派、车辆路径选择以及多商品流这些网络问题已构成大多数常见类型的实际优化问题。在网络问题的求解方法方面已经发生了稳定的进步，事实上，由于算法和技术的进步，上述求解方法方面的进步在过去十五年里呈现加速发展的趋势。　　本书目的是对线性、非线性和离散网络优化问题提供相当全面的最新的介绍。书中突出连续结构和离散结构之间的联系，从广泛的视野讨论相关的分析和算法问题，并对重要的网络模型和应用提供指导。　　……

内容概要

　　《信息技术和电气工程学科国际知名教材中译本系列·网络优化：连续和离散模型》不仅详细介绍了经典的线性网络优化模型、理论和方法，还分别对非线性网络优化问题和具有一般性整数约束的网络优化问题进行了广泛而深入的讨论，所涉及的网络优化知识非常全面。书中不少材料源自作者本人在网络优化相关领域多年的研究成果和研究心得，内容新颖，富有启发性，与同类书籍相比具有鲜明的特色。通过阅读《信息技术和电气工程学科国际知名教材中译本系列·网络优化：连续和离散模型》，能够对网络优化模型、理论和方法建立完整的认识。　　《信息技术和电气工程学科国际知名教材中译本系列·网络优化：连续和离散模型》每章都配备了大量习题，适合用作网络优化相关课程的教材。书中各章节内容既相互关联，又相对独立，便于教师根据课时安排进行适当的选择。

作者简介

作者：（美国）博赛卡斯 译者：王书宁 牟晓牧 李星野

书籍目录

第1章引言 1.1图和流 1.1.1路和环 1.1.2流和散度 1.1.3路流和共轭分解 1.2网络流模型一例子 1.2.1最小费用流问题 1.2.2凸费用网络流问题 1.2.3多商品流问题 1.2.4离散网络优化问题 1.3网络流算法——综述 1.3.1原费用改进 1.3.2对偶费用改进 1.3.3拍卖 1.3.4好算法，坏算法及多项式算法 1.4注释，文献和习题 第2章最短路问题 2.1问题表述与应用 2.2通用最短路算法 2.3标记设置（Dijkstra）法 2.3.1标记设置法的性能 2.3.2二叉堆法 2.3.3 Dial算法 2.4标记修正法 2.4.1 Bellman—Ford算法 2.4.2 D’Esopo—Pape算法 2.4.3 SLF算法和LLL算法 2.4.4阈值算法 2.4.5标记设置法和标记修正法的比较 2.5单起点单终点算法 2.5.1标记设置 2.5.2标记修正 2.6拍卖算法 2.7多起点多终点算法 2.8注释，文献和习题 第3章最大流问题 3.1最大流最小割问题 3.1.1图的割集 3.1.2最大流最小割定理 3.1.3最大和最小饱和割集 3.1.4不可行网络问题的分解 3.2 Ford—Fulkerson算法 3.3基于价格的增广路算法 3.3.1基于价格的路构造算法 3.3.2基于价格的最大流算法 3.4注释，文献和习题 第4章最小费用流问题 4.1变换和等价 4.1.1置流量下限为零 4.1.2消除流量上限 4.1.3简化为循环形式 4.1.4简化为指派问题 4.2对偶 4.2.1互补松弛条件和对偶问题的解释 4.2.2非负约束的对偶和互补松弛条件 4.3注释，文献和习题 第5章单纯形法 5.1单纯形法的主要思想 5.1.1利用价格确定入边 5.1.2确定出边 5.1.3处理退化情况 5.2基本单纯形法 5.2.1单纯形法的终止性质 5.2.2单纯形法的初始化 5.3推广到具有上下界约束的问题 5.4实现问题 5.5注释，文献和习题 第6章对偶上升方法 6.1对偶上升 6.2原对偶（序贯最短路）方法 6.3松弛方法 6.4求解已解决问题的变形 6.5实现问题 6.6注释，文献和习题 第7章拍卖算法 7.1指派问题的拍卖算法 7.1.1主拍卖算法 7.1.2近似坐标下降解释 7.1.3拍卖算法的变形 7.1.4复杂性一E一伸缩 7.1.5处理不可行性 7.2拍卖算法的推广 7.2.1逆向拍卖 7.2.2非对称指派问题的拍卖算法 7.2.3同类人员拍卖算法 7.3最大流的预流推进法 7.3.1分析与复杂性 7.3.2实现问题 7.3.3与拍卖算法的关系 7.4 ε—松弛方法 7.4.1计算复杂性——ε—伸缩 7.4.2实现问题 7.5拍卖／序贯最短路算法 7.6注释，文献和习题 第8章非线性网络优化 8.1凸可分问题 8.2有附加约束的问题 8.3多商品流问题 8.4整数约束 8.5有增益的网络 8.6最优性条件 8.7对偶性 8.8算法和近似 8.8.1可行方向法 8.8.2分片线性近似 8.8.3内点法 8.8.4罚函数和增广Lagrange方法 8.8.5近邻最小化 8.8.6光滑化 8.8.7变换 8.9注释，文献和习题 第9章凸可分网络问题 9.1单变量凸函数 9.2最优性条件 9.3对偶性 9.4对偶函数可微性 9.5可微对偶问题算法 9.6拍卖算法 9.6.1 ε—松弛法 …… 第10章整数约束网络问题 附录A有关数学知识回顾 参考文献 索引

章节摘录

版权页：   插图：   网络流问题是最重要且最经常遇到的优化问题之一。它们自然地出现于通信、交通和制造网络这样一些大系统的分析和设计问题中。它们也可用于描述指派、最短路和旅行商路线这样一些组合问题。 笼统地说，网络流问题由供给点和需求点以及连接它们的若干路径所组成，其作用是将供给转运到需求。这些路径可能包含中问转运点。通常可以用图的节点表示供给点、需求点以及转运点，用图的路表示路径。另外，可能有多种“类型”的供给／需求（或“商品”）共享某些路径。对路径的特性也可能有某些约束，比如它们的载货能力，使用特定路径时还会有相应的费用。这些问题可以自然地建模为网络流优化问题，粗略地说，我们试图通过网络流优化选出能够以最小的费用将供给转运到需求的路径。 本书所处理的网络流优化问题非常广泛，包括线性和非线性费用函数。我们应特别注意四类主要问题： （1）转运或最小费用流问题，包括一种商品和一个线性费用函数。该问题有若干重要特例，比如最短路、最大流、指派以及运输问题。 （2）单商品凸费用网络流问题。该问题和前面的转运问题相同，只是费用函数是凸函数而不仅是线性函数。 （3）多商品线性或凸费用网络流问题。该问题将前面的两类问题推广到多商品情况。 （4）离散网络优化问题。在这些问题中，沿着网络路径传输的量只能取有限个数值。很多组合优化问题可以这样建模，其中有些问题的网络结构并不很明显。某些离散优化问题的计算非常困难，实践中只能近似求解。它们的求解算法经常涉及求解前面三类“连续”的子问题。 上面提到的所有网络流问题都可以用和图相关的概念建立数学模型。我们在1.1节引入有关符号和术语；在1.2节给出网络流优化模型的数学公式和实际例子；最后在1.3节对后面章节将提出的一些算法给出一个概述。 1.1图和流 本节我们引入一些基本定义，涉及图、路、流以及其他概念。图的概念非常直观，可以按照提示性图形来理解，但也经常隐含一些微妙之处。因此读者可能需要以后再回顾本节内容，并对有关定义的一些细微点进行更仔细的阅读。

编辑推荐

《信息技术和电气工程学科国际知名教材中译本系列:网络优化:连续和离散模型》每章都配备了大量习题，适合用作网络优化相关课程的教材。书中各章节内容既相互关联，又相对独立，便于教师根据课时安排进行适当的选择。

用户评论 (总计2条)

•   还没看，书皮有点脏。可能是太久没人买。
•   不错的书，应该是控制工程专业的？不过也适合计算机专业的作算法参考纸张比较柔软不过手感还行