[科普中国]-网络最优化问题

网络最优化问题是一类特殊的组合最优化问题。应用图论理论，通过网络的拓扑结构及其性质，对网络进行研究，并且以计算机算法寻求网络中的最短路、最大流等。

基本内容网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。1

分类网络最优化问题类型主要包括： 最小费用流问题、最大流问题、最短路问题、最小支撑树问题、货郎担问题和中国邮路问题等。

最小费用流问题：模型在网络最优化中扮演着重要的角色，因为它的适用性很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使得配送网络的运营最优；

最大流问题：有供应点、需求点、转运点、弧的容量限制，但没有供应量和需求量的限制，目标是通过网络到目的地的总流量最大；

最短路问题：有供应点(供应量为1) 、需求点(需求量为1) 、转运点、没有弧的容量限制，目标是通过网络到目的地的总距离最短；

最小支撑树问题：为了使得每两个节点之间形成路，需要提供足够的边。目标就是以某种方法完成网络设计，使得边的总成本最小。这种问题称为最小支撑树问题；

货郎担问题：一个推销员从n个城市中的某个城市出发，到其他n－1个城市推销货物，每个城市都必须访问并且只访问一次，最后回到出发地，如何安排他的行走路线使总距离最短，这就是货郎担问题或旅行售货员问题；

中国邮路问题：一个邮递员从邮局出发，将邮件投递到他管辖的所有街道，最后回到邮局，如何安排他的行驶路线，使总路长最短。这个问题由我国数学家管梅谷教授于1962年首先提出来的，因此称为“中国邮路问题”。1

应用网络规划可以用于解决优化物流配置问题。首先将实际问题按照网络最优化问题的一般假设和原理建立数学模型，用计算机程序进行求解。然后测试模型，在必要时进行修正，并应用模型分析问题、提出建议、进行辅助管理决策。物流系统是由物流各要素所组成的，要素之间存在有机联系的总体。这个总体十分复杂，其内部存在着相互作用和相互依赖的各个组成部分。这个总体的特定功能，是使物流活动优化及合理化。网络分析是运筹学中的一个重要分支，是借助于图的知识来研究管理、组织与计划中的优化问题的另一种方法。2

比如在研究工程问题中，如何找出在现有资源的情况下，使工程所用时间最短或费用最小的方案。又如在企业管理中，如何制定管理计划或设备购置计划使得收益最大或费用最小等。在研究物流配置的问题中也可以利用网络的方法来对物流网络进行优化达到合理配置的目的。线性规划的一类重要应用是网络最优化问题。网络最优化问题有许多类，主要有最短路问题、最大流问题、最小费用流问题。3

本词条内容贡献者为:

刘燕兵 - 副研究员 - 中国科学院信息工程研究所