论文部分内容阅读
摘 要：最大流和它的对偶问题最小截问题是经典的组合优化问题，已有40多年的研究历史，存在许多优秀的算法和大量优秀的代码。许多问题转化为最大流问题或最小截问题后可以得到十分有效的解决。该文列举了网络最大流问题在匹配问题，图的边连通度问题及资源分配问题领域的应用。
关键词：组合优化 线性规划 网络优化 最大流 最小截
中图分类号：F224 文献标识码：A 文章编号：1674-098X（2014）05（c）-0043-02
最大流和它的对偶问题最小截问题是经典的组合优化问题，也是特殊的线性规划问题，已有40多年的研究历史，存在许多优秀的算法和大量优秀的代码。因此许多问题转化为最大流问题或最小截问题后可以得到十分有效的解决。发现具体应用问题和最大流或最小截问题的联系是最大流问题或最小截问题应用研究的关键[1]。
1 网络最大流问题的数学描述
定义1[2]：对于以V为节点集，A为弧集，C为最大容量集的网络N=（V，A，C），其上的一个流，f是指从N的弧集A到R的一个函数，即对每条弧（i，j）赋予一个实数fig（称为弧（i，j）的流量），如果流f满足
（1）
则称f为可行流。
考虑在以V为节点集，A为弧集，C为最大容量集的网络N=（V，A，C）：节点vs为网络中唯一的源点，vt为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量为ds，通常记为v或v（f），即v=v（f）=ds=-dt，最大流问题就是在N=（vs，vt，V，A，C）中找到流值最大的可行流（即最大流）。
因此，用線性规划的方法，最大流问题可以形式地描述如下：
（2）
2 网络最大流问题的应用
2.1 求最大匹配问题
2.2 求图的边连通度问题
定义5[4]设G=（V，E）是连通图，如果e是G中的一条边，且G-{e}不连通，则称e是G的一条割边。若E1是E的非空子集，G-E1不连通，但对E1的任何真子集E2都有G-E2连通，则称E1是G中一个边割集。割点构成只含一个点的点割集。割边构成只含一条边的边割集。
定义6[4]设G是一个非平凡的连通图，则我们称λ（G）=min{|E1||E1是G的边割集}为G的线连通度。即λ（G）是使得G不连通所必须删除的边的最小条数。求图的边连通度问题可转化为求图的权全为1的全局最小截问题，所谓全局最小截是指所有点对间最小截中的值最小的截，又最小截问题的对偶问题是最大流问题，故求图的边连通度问题可转化为求弧的最大容量为1的最大流问题。现以举例说明，求图3的连通度。
解：在5个点中任选两点分别作为网络中的源点和汇点，则可以组成10个网络图，若以v1为源点，v5为汇点，且各弧上的最大容量为1的最大流问题.如图4所示。通过Ford-Fulkerson标号法求得最大流量为2。若以v1为源点，v3为汇点，且各弧上的最大容量为1的最大流问题如图5所示。通过Ford-Fulkerson标号法求得最大流量为3，总之我们需要求10个网络的最大流，限于篇幅不一一列举，在这些最大流中最小的流量为2，所以图的连通度为2。
2.3 资源分配问题
例 某市政工程公司在未来5～8月份内需完成4项工程：修建一条地下通道；修建一座人行天桥；修建一条道路及道路维修。工期和所需劳动力如表1所示，公司共有120人，任一项工程在一个月内的劳动力不能超过80人，则公司如何分配劳动力完成所有工程。
解：将工程计划用如下网络图6表示，其中标号5、6、7、8分别表示5～8月份，Ai， Bi，Ci，Di表示工程在第i个月内的完成部分，用弧表示某月完成某项工程的状态，弧的流量为劳动力限制。合理安排每个月个工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求上图从发点到收点的最大流问题。用Ford-Fulkerson标号法求得的一个最大流量方案如图7所示，可知5月份有剩余劳动力20人，4项工程恰好按期完成。
3 结语
该文列举、分析了网络最大流问题在匹配问题、图的边连通度问题及资源分配问题领域的应用并给出了对应的解决方案。
参考文献
[1] 张宪超，陈国良，万颖.网络最大流问题研究进展[J].计算机研究与进展，2003，40（9）：1281-1292.
[2] 《运筹学》教材编写组，运筹学[M].3版.北京：清华大学出版社，2005.
[3] 耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2004.
[4] GARY Chartrand，Ping Zhang.Introduction to Graph Theory[M].范益政等译.北京：人民邮电出版社，2006.
关键词：组合优化 线性规划 网络优化 最大流 最小截
中图分类号：F224 文献标识码：A 文章编号：1674-098X（2014）05（c）-0043-02
最大流和它的对偶问题最小截问题是经典的组合优化问题，也是特殊的线性规划问题，已有40多年的研究历史，存在许多优秀的算法和大量优秀的代码。因此许多问题转化为最大流问题或最小截问题后可以得到十分有效的解决。发现具体应用问题和最大流或最小截问题的联系是最大流问题或最小截问题应用研究的关键[1]。
1 网络最大流问题的数学描述
定义1[2]：对于以V为节点集，A为弧集，C为最大容量集的网络N=（V，A，C），其上的一个流，f是指从N的弧集A到R的一个函数，即对每条弧（i，j）赋予一个实数fig（称为弧（i，j）的流量），如果流f满足
（1）
则称f为可行流。
考虑在以V为节点集，A为弧集，C为最大容量集的网络N=（V，A，C）：节点vs为网络中唯一的源点，vt为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量为ds，通常记为v或v（f），即v=v（f）=ds=-dt，最大流问题就是在N=（vs，vt，V，A，C）中找到流值最大的可行流（即最大流）。
因此，用線性规划的方法，最大流问题可以形式地描述如下：
（2）
2 网络最大流问题的应用
2.1 求最大匹配问题
2.2 求图的边连通度问题
定义5[4]设G=（V，E）是连通图，如果e是G中的一条边，且G-{e}不连通，则称e是G的一条割边。若E1是E的非空子集，G-E1不连通，但对E1的任何真子集E2都有G-E2连通，则称E1是G中一个边割集。割点构成只含一个点的点割集。割边构成只含一条边的边割集。
定义6[4]设G是一个非平凡的连通图，则我们称λ（G）=min{|E1||E1是G的边割集}为G的线连通度。即λ（G）是使得G不连通所必须删除的边的最小条数。求图的边连通度问题可转化为求图的权全为1的全局最小截问题，所谓全局最小截是指所有点对间最小截中的值最小的截，又最小截问题的对偶问题是最大流问题，故求图的边连通度问题可转化为求弧的最大容量为1的最大流问题。现以举例说明，求图3的连通度。
解：在5个点中任选两点分别作为网络中的源点和汇点，则可以组成10个网络图，若以v1为源点，v5为汇点，且各弧上的最大容量为1的最大流问题.如图4所示。通过Ford-Fulkerson标号法求得最大流量为2。若以v1为源点，v3为汇点，且各弧上的最大容量为1的最大流问题如图5所示。通过Ford-Fulkerson标号法求得最大流量为3，总之我们需要求10个网络的最大流，限于篇幅不一一列举，在这些最大流中最小的流量为2，所以图的连通度为2。
2.3 资源分配问题
例 某市政工程公司在未来5～8月份内需完成4项工程：修建一条地下通道；修建一座人行天桥；修建一条道路及道路维修。工期和所需劳动力如表1所示，公司共有120人，任一项工程在一个月内的劳动力不能超过80人，则公司如何分配劳动力完成所有工程。
解：将工程计划用如下网络图6表示，其中标号5、6、7、8分别表示5～8月份，Ai， Bi，Ci，Di表示工程在第i个月内的完成部分，用弧表示某月完成某项工程的状态，弧的流量为劳动力限制。合理安排每个月个工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求上图从发点到收点的最大流问题。用Ford-Fulkerson标号法求得的一个最大流量方案如图7所示，可知5月份有剩余劳动力20人，4项工程恰好按期完成。
3 结语
该文列举、分析了网络最大流问题在匹配问题、图的边连通度问题及资源分配问题领域的应用并给出了对应的解决方案。
参考文献
[1] 张宪超，陈国良，万颖.网络最大流问题研究进展[J].计算机研究与进展，2003，40（9）：1281-1292.
[2] 《运筹学》教材编写组，运筹学[M].3版.北京：清华大学出版社，2005.
[3] 耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2004.
[4] GARY Chartrand，Ping Zhang.Introduction to Graph Theory[M].范益政等译.北京：人民邮电出版社，2006.