网络优化

作者简介

《网络优化》系统介绍了网络优化的基本模型和基本算法，包括构造这些算法的基本思想以及相应算法在计算机上的一些具体实现技巧和复杂性分析。全书由7章组成：第1章为概论，第2章介绍关于算法的一些基本知识，第3章到第7章分别讨论树的问题、最短路问题、最大流问题、最小费用流问题和匹配问题.每章还安排了一些练习题。

书籍目录

序言前言第1章 概论　1.1 网络优化问题的例子　1.2 图与网络　1.3 图与网络的数据结构　1.4 计算复杂性的概念　练习题第2章 算法基础　2.1 NP，NPC和NP-hard概念　2.2 算法设计与分析　2.3 小结　练习题第3章 最小树与最小树形图　3.1 树的基本概念　3.2 最小树算法　3.3 最小树形图　3.4 最大分枝　练习题第4章 最短路问题　4.1 最短路问题的数学描述　4.2 无圈网络与正费用网络：标号设定算法　4.3 一般费用网络：标号修正算法　练习题第5章 最大流问题　5.1 最大流问题的数学描述　5.2 增广路算法　5.3 最短增广路算法　5.4 一般的预流推进算法　5.5 最高标号预流推进算法　5.6 单位容量网络上的最大流算法　练习题第6章 最小费用流问题　6.1 最小费用流问题的数学描述　6.2 消圈算法与最小费用路算法　6.3 原始-对偶算法　6.4 瑕疵算法　6.5 松弛算法　6.6 网络单纯形算法　练习题第7章 匹配问题　7.1 匹配问题的数学描述　7.2 二部基数匹配问题　7.3 非二部基数匹配问题　7.4 二部赋权匹配问题　7.5 非二部赋权匹配问题　练习题索引及英文关键词参考文献

前言

　　最优化是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问题.结构设计要在满足强度要求等条件下使所用材料的总重量最轻；资源分配要使各用户利用有限资源产生的总效益最大；安排运输方案要在满足物质需求和装载条件下使运输费用最低；编制生产计划要按照产品工艺流程和顾客需求，尽量降低人力、设备、原材料等成本使总利润最高.可以预测，随着科学技术尤其是计算机技术的不断发展，以及数学理论与方法向各学科和各应用领域更广泛、更深入的渗透，在21世纪这个信息时代，最优化理论和技术必将在社会的诸多方面起着越来越大的作用.　　解决实际生活中优化问题的手段大致有以下几种：一是靠经验的积累，凭主观作出判断；二是做试验选方案，比优劣定决策；三是建立数学模型，求解最优策略.虽然由于建模时要作适当的简化，可能使结果不一定非常完善，但是它基于客观数据，求解问题简便、经济，而且规模可以很大（将来会越来越大）.人们还可以吸收从经验得到的规则，用实验不断校正建立的模型.随着数学方法和计算机技术的进步，用建模和数值模拟解决优化问题这一手段，将会越来越显示出它的效能和威力.显然，在决策定量化、科学化的呼声日益高涨的今天，数学建模方法的推广应用是符合时代潮流和形势发展需要的.　　.　　最优化理论、模型与方法所包含的内容很多，国内已出版了不少教材和专著介绍其各个分支.但是，一方面，近年来发展起来的、有着广泛应用背景的规划模型（如随机规划、模糊规划等），以及一些已经为许多人采用、受到广泛关注的优化算法（如模拟退火算法、遗传算法等）还缺乏详细和系统的介绍；另一方面，一些偏重优化理论和方法的教材，其要求难以与工科学生的数学知识衔接，也缺少对于应用来说十分重要的建模过程和软件介绍，而一些比较通俗的运筹学教材，则在加强理论基础，适应学生将来从事科研工作需要上考虑较少.这套教材试图弥补以上两方面的缺陷，力求体现下述特点：　　1.内容既包含传统的线性规划与非线性规划等部分，又纳入有广泛应用前景的随机规划和模糊规划；在传统内容中，既注重典型的数学思想和方法的系统叙述，又引入丰富的建模实例.　　2.数学基础既与工科学生所学知识衔接，又考虑到研究生阅读文献、从事科研工作的需要，适当提高理论基础的起点.　　3.对一般教材介绍的诸多算法进行精选，配合介绍一些应用软件，并引入近年来迅速发展的若干新算法.

章节摘录

　　第1章　概论　　我们生活在一个网络社会中。从某种意义上说，现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效地计划、管理和控制这个网络系统，使之发挥最大的社会和经济效益。　　网络优化是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。本书中将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是网络优化的基本问题。　　本章主要介绍网络优化问题的一些实际例子以及图与网络的基本概念，初步介绍计算复杂性理论，为后续章节的学习奠定基础。　　1.1　网络优化问题的例子　　我们首先通过一些例子来了解网络优化问题。　　例1.1　公路连接问题　　某地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

图书封面

---

 网络优化下载

---