第二节 网络优化理论

我们生活的网络社会，是一个由计算机信息网络、电话通信网络、运输服务网络、物质分派网络等和能源所组成的复杂的网络系统。谢凡荣（2009）提出，对一个网络系统进行有效的计划、管理以及控制，并让该网络系统达到最大的社会和经济效益，这个过程被称为网络优化。

网络优化是运筹学（Operations Research）中的一个经典和重要分支，所研究的问题涉及物资管理、经济管理、工业工程、交通运输、计算机科学与信息技术、通信与网络技术、控制论及军事运筹学等诸多领域。

在网络优化的过程中，最短路问题、最小饱和流问题、最大流问题、最小费用最大流问题、最小费用流问题、最大利润流问题、最大容量路问题等都是一些最基本的问题。国内外有不少学者对这些问题进行了深入的研究，并且取得了很好的成果。例如，在最大流的问题上，国内学者徐周波（2005）和江锦成（2014）分别应用ADD算法和SAPR算法对其进行求解；而Dijkstra算法和Floyd算法在求解最短路问题上应用比较广泛。

Thomas（2006）指出最短路问题的基本内容是：若网络中的每条边都有一个基于长度、成本或时间的数值，则找出源点和末点之间总权和最小的路径就是最短路问题，可用来解决最短运输路线计算、车辆路径安排以及厂区的选址和布局等一些现实问题。

1956年福特和福克逊提出了最大流标号算法，并建立了“网络流理论”。最大流问题（maximum flow problem）是一种组合最优化问题，它的作用是在对设备合理利用的情况下，通过使运输流量最大来提高效率，以达到最好的效果。

钱颂迪（1990）对网络中最小费用最大流问题进行了详细论述。任意一个网络中都存在着路径，而且每段路径都有“容量”和“费用”两个条件的限制。此类问题的研究试图解决一个问题：从起点到终点如何选择路径以及分配经过路径的流量，可以在流量最大的前提下，达到所需的费用最小的要求。

卢虎生等（2003）阐述了在网络优化中，最大利润流是以运输利润最大为目标。一个利润可行流可分解为若干个路流和圈流，相应地该可行流的利润也等于这些路流和圈流的利润之和。

研究网络优化问题的多目标规划模型与算法中，考虑到人的有限理性以及问题的复杂性这两方面因素，往往在追求最优解的时候更趋向于寻找满意解或者有效解。周树发等（2004）以工程网络优化为研究对象，综合考虑工程的质量、工期、成本、资源等多个因素，建立多目标规划模型，以求网络优化的全面性。