1、 最大网速问题的数学模型 摘要 本题给出了各节点之间的网络流图，需求解它们之间的最大流，即最大网速，为了能有 效地解决此问题，我们首先利用求解最大流的标号法对网络图中的可增广链进行逐一分析， 并对该链上的流量进行调整，直到该图中没有可增广链后，求得节点 1 到节点 6 的最大网速 为 6 兆，然后再通过 MATLAB 编程实现对标号法求解的结果进行验证。 最后，又通过提高各节点之间的网速来达到提高从节点 1 到节点 6 网速的目的，得出了 各链之间增加的具体流量。 即 s v到 1 v的容量应增加到 2 6 3 x ， 3 v到 t v的容量应增加到2 2 x ， 2 v 到 4 v与 4 v
2、到 t v的容量都应增加到7 2 x 。 当然若 2 02 3 x ，即03x，则 s v到 1 v的容量不变。同理，若03 2 x ，即06x， 则 2 v到 4 v与 4 v到 t v的容量也不变。 关键词：网络最大流；可增广链；网络流图；MATLAB； 目 录 一 问题的提出1 二 模型假设1 三 符号说明2 四 问题的分析2 五 模型的建立与求解2 5.1 模型的建立2 5.1.1 可行流3 5.1.2 割集3 5.1.3 最大流-最小割定理.4 5.1.4 可增广链推论4 5.1.5 寻求最大流的方法4 5.1.6 可行流调整算法4 5.1.7 最大流的标号算法4 5.2 模型的求解
3、5 六 模型的优化.13 6.1 网络最大流的算法拓展.13 6.2 问题的优化求解.14 模型评价16 参考文献17 附录18 第 1 页 共 20 页 一、问题的提出一、问题的提出 下图为一网络，节点 1 到节点 2 的宽带带宽为 6 兆，节点 1 到节点 3 的宽带带宽为 2 兆， 节点 2 到节点 4 的宽带带宽为 3 兆，节点 4 到节点 6 的宽带带宽为 2 兆，求节点 1 到节点 6 的最大网速。 进一步，若想提高节点 1 到节点 6 的最大网速 x 兆，如何实现？ 二、二、模型假设 2.1 假设流量在网络传输中没有损失； 2.2 假设环境对网速没有影响； 第 2 页 共 20
4、页 三、符号说明 3.1 符号说明 符号 含义 i v、 j v 某一顶点处的标号 s v、 t v 始点和终点的标号 S 标号点集合 S 为标号点集合 (,)SS 割集 f 可行流 ij f/ ji f 从 i v到 j v的流量/从 j v到 i v的流量 ij c i v到 j v所在链上的容量 E 边集 i v 流量调整量 四、问题分析 问题的分析问题的分析： 通过对题目的剖析，我们可以知道，要想求解最大流，我们必须要保证在从节点 1 到节 点 6 之间没有可增广链，因此本题求解的方向是从如何求解可增广链，然后逐步求得最大流。 五、模型建立及求解 5.15.1 模型的建立模型的建立 由题中所给图形，我们可以对其标号做一点修改，得到图 1： 第 3 页 共 20 页 图 1 网络传输过程中的流量图 为了方便对问题的求解，我们引入以下概念和定理： 5.1.1 可行流 由书中所给定义知非负数 ij c 为边的容量，本文中即指带宽，而图中（8,1）对应（ ij c ， ij f ） 其中 ij f 表示任一边（ i v， j v ）的流量，
