Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(3)
时间:2016-12-28 17:33 来源:毕业论文 作者:毕业论文 点击:次
表1.1 最大流算法时间复杂度进展[9] （不包括随机算法和近似算法） 注： 介于 和 之间， 在 的多项式量级上 1.3 网络流基本概念及其数学模型 1.3.1 基本概念 定义 1：一个网络（Network）是一个有两个不同顶点的有向图 ，一点称为网络的源点（source），记为 或 ，而另一点称为收点（sink），记为 或 ，其余的点叫中间点（intermediate vertices）。对于每一个弧（arc） ，对应有一个 (或简写为 ) , 称为弧的容量（capacity）。为了方便起见，我们通常把网络记作 。 网络上的流（flow），是指定义在弧集合 上的一个函数 ，并称 为弧 上的流量(也简记作 )。 定义 2：满足下述条件的流 称为可行流： (1 ) 容量限制条件：对每一弧 ， ； (2 ) 平衡条件： 对于中间点：流出量等于流入量，即对每个 有 对于发点 ，记 对于收点 ，记 式中 称为这个可行流的流量，即源点的净输出量(或收点的净输入量) 。并称其为可行 流。 可行流总是存在的。比如令所有弧的流量 ，就得到一个可行流(称为零-流)，其流量 。 定义 3：网络中的一个流是最大流，如果网络中没有其它的流量比其大的流。 若给一个可行流 ，我们把网络中使 的弧称为饱和弧（saturated arc）, 使 的弧称为非饱和弧（unsaturated arc）。使 的弧称为零流弧（flow-zero arc）, 使 的弧称为非零流弧（flow-positive arc）。 若 是网络中连接源点 和收点 的一条路径，我们定义路径的方向是从 到 ，则路径上的弧被分为两类: 一类是弧的方向与路径的方向一致，叫做前向弧（forward arc）。前向弧的全体记为 。另一类弧与路径的方向相反，称为后向弧（backward arc）。后向弧的全体记为 。 定义 4：设 是一个 可行流， 是从 到 的一条路径，若 满足下列条件，称之为关于可行流 的增广路（augmenting path），或 增广路。 在弧 上， ，即其中每一条弧都是非饱和弧； 在弧 上， ，即其中每一条弧都是非零流弧。 设 ， ，我们把始点在 中, 终点在 中的所有弧构成的集合, 记为 。 定义 5：给网络 ，若点集 被剖分为两个非空集合 和 使 ， ，则把弧集 称为是(分离 和 的) 割集（cut set）。 给定一 割集 ，把割集 中所有弧的容量之和称为这个割集的容量(简称为割量) , 记为 ，即 1.3.2 数学模型 网络最大流问题的数学模型可以描述为： 并且满足： 最大流问题是一个特殊的线性规划问题。 二 Ford–Fulkerson算法 Ford–Fulkerson算法是1956年提出的，是被广泛使用的一种经典算法。Ford和Fulkerson的算法首次使用组合优化的方法来解决最大流问题。该算法引进了剩余网络、增广路等概念[1]，把最大流问题的求解归结为从一个初值（即一个可行流）开始，不断递增（即增广）直到求得最优解的迭代过程，这个过程奠定了用组合方法求解最大流问题的基础。 2.1 Ford–Fulkerson算法的思想及原理 定理1（最大流最小割定理[1]）：设 是一个源为 收点为 的网络。关于 中的每个可行 流，有下列相互等价的命题： （a）流 是一个最大 流； （b） 中不存在一条 增广路； （c）存在一个 割 ，使得 。 由于本文的目的并不是研究最大流的理论，在这里只证明 [13]。 证明： ：若 是最大流，设 中存在关于 的增广路，令 由增广路的定义，可知 ，令 不难验证 是一个可行流，且 。这与是最大流的假设矛盾。 (责任编辑：qin) |