网络优化:连续和离散模型.pdf

所需积分/C币:40 2019-07-23 13:05:46 35MB PDF

网络优化:连续和离散模型 . pdf
信息技术和电气工程学科国际知名教材中译本系列 Network Optimization Continuous and Discrete Models 网络优化:连续和离散模型 Dimitri P Bertsekas著 王书宁牟晓牧李星野译 清华大学出版社 北京 北京市版权局著作权合同登记号图字:01-2009-4079 Authorized translation froin the English language edition, entitled Network Optimization: Continuous and Discrete Models ISBN 1-886529-02-7 by Dimitri P. Bertsekas, published by Athena Scientific copyright @1998 All Rights Reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information ste OTEC retrieval system; without permission from Athena Scientifie Simplified chi lincs language edition published by TSINGHUA UNIVERSITY PRESS Copyright 2012 本书中文简体版由 Athena Scientific授权给清华大学出版社出版发行。未经许可,不得以任何方式复制 或抄袭本书的任何部分。 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:010-6278298913701121933 图书在版编目CIP)数据 网络优化;连续和离散模型/(美)博赛卡斯( Bertsekas,D.P)著:王书宁等译北京:清华大学 出版社,2013.1 书名原文; Network Optimization: Continuous and Discrete Model 〔信息技术和电气工程学科国际知名教材中译本系列 ISBN9787-302-300526 I①网…Ⅱ、①博…②王…Ⅲ①网络理论-研究Ⅳ①O157.5 中国版本图书馆CIP数据核字(2012)第215648号 责任编辑:王一玲 封面设计:常雪影 责任校对:梁毅 责任印制:李红英 出版发行:清华大学出版社 pa#iT:http://www.tup.comcn,http://www.wabook.com 地址:北京清华大学学研大厦A座 邮编:100084 社总机:010-627701 邮购:010-62786544 投稿与读者服务:010-62776969, service(a tup. tsinghua,edu.cn 质量反馈:010-62772015,zhiliang@tup.tsinghua,edu.cn 课、件下载:htp:/www.tup.com.cm,01062795954 印装者:清华大学印刷厂 经销:全国新华书店 开本:185mm×260 mn 印张:32,25 字数:762千字 版次:2013年1月第1版 印次:2013年1月第1次印刷 印数:1~2000 定价;59.00元 产晶绵号:031851-01 译者序 本书介绍网络优化的模型、理论和方法,作者为美国麻省理工学院 Dimitri e.Bert sekas教授。 网络优化是一类非常有趣的数学规划问题。首先,网络优化模型可用网络图表示,这 种可视性为直观解释数学规划理论和方法提供了很好的途径;其次,对于线性网络优化问 题,变量的整数性约束一般都能自动满足,从而可将离散问题当作连续问题求解,这是一 个非常特别而有用的性质:另外,实践中遇到的经常是包含众多边和节点的大规模网络优 化问题,用网络优化算法求解此类问题在速度和可靠性方面均具有明显优势。由于上述原 因,无论从理论研究还是实际应用的角度来看,学习网络优化知识均大有裨益。 本书不仅详细介绍了经典的线性网络优化模型、理论和方法,还分别对非线性网络 优化问题和具有一般性整数约束的网终优化问题进行了广泛而深入的讨论,所涉及的网 络优化知识非常全面。书中不少材料源自作者本人在网络优化相关领域多年的研究成果 和研究心得,内容新颖,富有启发性,与同类书籍相比具有鲜明的特色。通过阅读本书, 能够对网络优化模型、理论和方法建立完整的认识。 本书每章都配备了大量习题,适合用作网络优化相关课程的教材。书中各章节内容 既相互关联,又相对独立,便于教师根据课时安排进行遹当的选择。 本书第1、5、6、8章及附录部分由王书宁翻译,第2、3、4、10章由牟晓牧翻译,第7、9章 由李星野翻译,最后由王书宁定稿。 感谢 Dimitri p. Bertsekas教授提供本书英文版本的电子文件,为翻译本书提供了极大 的便利。 译者 2012年10月 前言 优化问题可分为两种主要类型:连续型和离散型。网络优化就居于这两类问题的分界 线上。线性规划和组合优化问题之间存在联系是因为可以将多面体约束集表示为其极点的 凸包。当涉及到网络时,由于多面体的极点是整数向量,并且它们所表示的是看上去和线 性规划不相干的组合问题的解,上述联系变得紧密得多。正由于这种结构,也由于它们的 直观特性,网络模型为解释连续优化和离散优化中的很多基本思想提供了理想的工具。 网络模型除了具有引人入胜的方法论方面的特点之外,在实践中也被广泛应用,其应 用范围还在持续扩大。总体上看确实如此,诸如最短路、指派、最大流、运输、转运、生成 树、匹配、旅行商、广义指派、车辆路径选择以及多商品流这些网络问题已构成大多数常 见类型的实际优化问题。在网络问题的求解方法方面己经发生了稳定的进步,事实上,由 于算法和技术的进步,上述求解方法方面的进步在过去十五年里呈现加速发展的趋势 本书目的是对线性、非线性和离散网络优化问题提供相当全面的最新的介绍。书中 突出连续结构和离散结构之间的联系,从广泛的视野讨论相关的分析和算法问题,并对重 要的网络模型和应用提供指导。 关于连续网络优化,我们主要集中于两个想法,它们也是一般性数学规划的基本想 法:对偶性和迭代费用改进。我们对用迭代算法解决最常见的线性费用问题、最小费用流 问题或转运问题以及后者的凸费用版本,进行广泛的讨论。关于对偶性的讨论也相当全面 从线性网络规划的对偶性开始,直至 Rockafellar关于单变规划对偶性的发展。 关于离散网络优化,我们通过诸如旅行商、广义指派、生成树、匹配和路径选择这些主 要范例进行问题描述。这样做是必要的,因为和连续优化问题的结构相比,对离散优化问题 的结构很难进行简单高效的描述,熟悉一些重要类型的问题对于建模、分析和利用算法求 解非常重要。我们也要介绍主要的求解算法,包括分支定界、 Lagrange松弛、 Dantzig-Wolfe 分解、启发式方法以及局部搜索方法。 这是一本涵盖广泛主题的导论性书籍。因此,不可避免地对某些主题的讨论不会像 对别的主题那样详细。有关内容的选择,部分由于个人兴趣和专业知识,部分由于作者对 简单模型的偏好,这种模型有可能以最有效的方式帮助读者认识相应问题的本质。同时, 前言 我们在分析和阐述时试图通过以下两种方式增强读者的数学建模能力:界定各种算法能 够有效求解的问题的范围,为一般性公式描述的问题提供很多实例。 本书各章内容如下: 第1章:本章为全书引言,给出图的基本概念和术话,讨论网络模型的若干例子,并对 线性网络优化算法有关情况进行初步介绍。 第2章:本章对最短路问题进行广泛讨论。内容涉及主要方法以及它们的理论和实际 性能。 第3章:本章集中讨论最大流问题以及求解该问题的增广路算法。除了经典的Ford- Fulkerson方法的变形,还介绍近期基于拍卖的想法发展的一种算法。 第4章:本章介绍最小费用流问题(线性费用,单种商品,无附加约束)及其等价变形。 随后对该问题给出基本的对偶理论以及相应的解释。 第5章:本章集中讨论求解最小费用流问题的单纯形法。以构遣方式导出有关这种方 法的整数解的基本结果。此外,还显著地强化了第4章的对偶理论。 第6章:本章导出对偶上升方法,包括原对偶、序贯最短路和松弛方法。 第7章:本章从介绍指派问题的拍卖算法开始,进而说明如何将这种算法推广到更加 复杂的问题。由此得到最大流问题的预流推进法和最小成本流问题的←松弛法。另外还给 出了拍卖算法的若干种变形。 第8章:本章内容很重要,它从线性网络优化转向非线性网络优化。主要注意力集中 于连续(凸)问题以及和这些问题相关的结构和处理方法的广泛多样性。具体地说,本章将 对非线性规划的多类算法进行综述,这些算法可以用于解决不同的凸网络优化问题。另外 也会对离散(整数)问题进行一些讨论,并着重强调它们和连续问题的联系。 第9章:本章内容复杂,它的主要对象是高层次和/或研究导向的读者。它处理可分凸 问题,讨论这些问题和经典的网络平衡问题之间的联系,并导出它们的丰富的理论结构。 这种结构的突出特色是一个特别精致的对偶理论以及下降方向和流量守恒约束定义的子 空间的基本向量有限集之间的组合关联。除了讨论凸可分网终问题之外,本章还对单变规 划进行初步介绍,这是具有线性规划的强对偶性和组合性质的最大类的非线性规划问题。 本章也要导出凸可分问题的拍卖算法,并对它们的运行时间进行分析。 第10章:本章讨论整数约束问题的基本处理方法。其中要讨论精确处理方法,比如分 支定界方法、基于 Lagrange松弛的有关方法、次梯度优化方法和割平面方法。另外也要描 述基于局部搜索的近似方法,比如遗传算法、禁忌搜索和模拟退火方法。最后还要讨论部 署算法,这是相对较新且可广泛应用的一类近似方法,它可以代替局部搜索或和后者一起 协同工作。 本书可以用作网络优化课程教材或者用作一年级研究生优化导论课程的部分教材。 除了第9章的一些内容,阅读本书仅需要相当基本的预备知识。主要要求是有一定程度的数 前言 学素养,例如,学习过徽积分之外的严格的数学课程。本书大部分内容可以用于线性和非 线性优化课程。其中第1至第5章和第8章可以构成一个短期课程的内容。作为一种选择,也 可以选用第1至第5章,第8章的一小部分,以及第10章构成一门集中关注线性和离散网络优 化的课程。实际上,如果满足于较弱的对偶结果(在第4章给出),并且采用类似习题1.34给 出的分析路径去建立最优解的整数性质,那么上面的各章列表可以不包含第5章的内容。 下面的图说明了各章之间的依赖关系 第1至第5章 (引言/线性〕 第6章 第7章 第8章 第10章 (对偶方法)(拍卖)(非线性/离散川(整数) 第9章 (凸间题) 本书包含大量例题和习题,适合课堂教学使用。有些理论性习题可用作主要内容的 重要补充材料。对部分习题的解答(以及误表和附加材料)将放在本书网页 http://world.std.com/"athenasc/netsbook.htm 并会定期更新。另外,作者的网页 http://web.mitedu/dimitrib/www/home.html 也包含一些 FORTRAN编码,它们实现了本书讨论的很多算法。 关于连续和离散网络优化有非常广泛的文献,不可能将它们全部列出,也不可能对导 致目前状况的所有研究历史进行全面的回顾。因此我不打算对该领域所有的原创性贡献 列出完整的清单。作者所引用的或者是已被作者广泛使用的文献,或者是对本书内容提供 了重要扩展的文献,或者是综述一些重要主题的文献,或者是特别适合进一步阅读的文献。 我们也选择性地引用了少数具有历史重要性的文献,但这方面的相应列表远远不够完整。 一般而言,为了有助于该领域的研究者,对于所涉及的主题,作者更偏好于引用相对比较 成熟且对较近期的发展给出了大量参考文献的综述或教材。 本书相当一部分内容是基于作者在过去20年中对网络优化的研究。在这些研究中作 者很幸运地遇到一些优秀的合作者,这里要提到已经和作者进行了广泛合作的一些人。Ei Gani于1979年帮助作者进行了采用拍卖算法和松弛方法解决指派问题的计算试验。作者 和F在那段时期的交流中产生了ε伸缩的想法。另外,Eli和作者在数据网络的各种路径 选择方法中进行了广泛的合作,包括凸的多商品流问题的投影方法。 Paul tseng从1982年 起就和作者一起进行网络优化的工作。我们一起开发了 RELAX编码,对基本的松弛方法 vI 前言 进行了若干扩展,并在其他多种课题中进行了密切的合作,包括最近的解决凸网络问题和 有增益的网络问题的拍卖算法。自1987年以来, David castanon和作者一起研究了指派问 题、运输问题、最小费用流问题的多种算法,包括串行和并行算法。 John tsitsiklis多年以 来一直是作者在优化和大规模计算问题方面的共同作者和紧密合作者,其中包括网络问 题。除了Ei,Paul, David和John,作者和一些同事也有相当多的合作研究经历,相应结果 在本书也有反映。在这方面,作者要提到 Jon Eckstein, Bob Gallager, Francesca Guerriero, Roberto musmanno, Stefano pallottino和 Maria- Grazia scutella若干同事校对了本书部分 内容,并贡献了极有价值的建议。尤其是 David Castanon, Stefano pallottino, Steve Patek Serap savari, Paul Tseng和 John tsitsiklis在这方面给出了很多帮助。非常感谢来自DDM 和CCI部门的NSF研究经费支持。作者的家庭一直是稳定和爱的支持的源泉,没有这些本 书不可能完成。 Dimitri P. bertsekas Cambridge, Mass Spring 1998 目录 第1章引言 1.1图和流 1.1,1路和环 ;。 112流和散度 2346 1.1.3路流和共轭分解 1.2网络流模型一例子. 12.1最小费用流问题 12.2凸费用网络流问题 14 123多商品流问题 annIE, .nH89n8n8.881?t, IRRI道i重dan重目a 15 124离散网络优化问题…16 1.3网络流算法一综述…18 1.3.1原费用改进… :-1:4418 1.3.2对偶费用改进 1.3.3拍卖 1.34好算法,坏算法及多项式算法 tf世tt当f“世+t世tt当 ITttBINI'taa'重 14注释,文献和习题 32 第2章最短路问题 45 21问题表述与应用 ;a;4a;;;;*;*44;;=-;+=-;"++如++;++;+++,++,,如,+ 46 22通用最短路算法…50 23标记设置( Dijkstra)法,, Ia.naBE 23.1标记设置法的性能 ,,,,,,,,,,,,.59 23.2二叉堆法 ++++;+++++++a+x 59 233Dial算法.160 24标记修正法……1683

...展开详情

评论 下载该资源后可以进行评论 1

xinchuzu 很优秀!值得学习。
2019-12-09
回复
img
ASR-06
  • 签到新秀

    累计签到获取,不积跬步,无以至千里,继续坚持!

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐