前言

我们生活在一个网络社会中. 从某种意义上说，现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统. 网络优化就是研究如何有效地计划、管理和控制这个网络系统，使之发挥最大的社会和经济效益.

网络优化是运筹学(Operations Research)中的一个经典和重要的分支，所研究的问题涉及物资管理、经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术、控制论及军事运筹学等诸多领域. 因此学习一些有关网络优化的基本知识, 对许多专业的学生和许多领域的科技人员、管理人员都是相当必要的.

本书系统介绍了网络优化的基本模型和基本算法. 在基本模型方面, 主要介绍树的问题(包括最小树、最小树形图、最大分枝)、最短路问题、最大流问题、最小费用流问题和匹配问题等. 在基本算法方面，由于处理上述这些问题的算法非常多，而且新算法还在不断涌现, 从大量算法中选择哪些典型算法进行介绍本身是见仁见智的事，我们只能有选择地介绍其中部分算法. 我们既介绍一些比较经典的算法，也介绍一些比较新颖、实用的算法.

本书由7章组成. 第1章为概论, 主要介绍图和网络的一些基本概念、图和网络在计算机上的表示方法，并初步介绍计算复杂性理论.第2章介绍关于算法的一些基本知识，包括计算复杂性理论、近似算法、整数规划、动态规划，以及一些常用的网络搜索算法等.第3章到第7章分别介绍树的问题、最短路问题、最大流问题、最小费用流问题和匹配问题，这是网络优化的基本内容. 

本次成书过程中参考了大量国内外有关文献和教材，并对内容进行了进一步的筛选和扩充. 我们希望本书能适合于各个层次的读者阅读. 对于数学和计算机等理论性要求较高的专业的教学，最好能讲授本书全部或大部分内容，并要求读者在学习本课程之前已经掌握了线性规划的基础知识. 我们希望不仅能让这部分读者了解各种网络优化算法的基本思想和基本理论，而且能了解一些实现技巧并学会算法的复杂性分析方法. 在各章的练习题中，我们还配备了一定数量难度较高的题目作为对书中讲授内容的扩充.对于其他理论性要求不太高的专业的教学或不太关心算法复杂性的读者来说，可以在阅读中略去部分理论内容. 对于只想对网络优化有所了解或只希望从本书中查询一些具体算法的读者来说，完全可以略去全部的理论部分， 而只了解相应的模型和算法就可以了. 

自2000年以来，笔者以本书为教材在清华大学讲授研究生课程“网络优化”.在此期间，得到多方面的反馈和宝贵意见.在此基础上，我们对本书的结构和内容进行了一些调整和修改.在第2版中增加了算法基础一章，介绍一些准备知识，包括复杂性理论、近似算法及一些常用的算法.第1版中的整数规划和动态规划两章不再作为单独的章节出现，一些相关的内容安排在算法基础一章.

最后，对我们家人的理解、耐心和支持表示由衷的谢意！由于我们的水平有限，恳请读者对本书的不足之处提出批评指正.