第2讲 最大流与最小费用流(13)

建模

寻求最大流问题的方法： 寻求最大流问题的方法： 先任一假设网络的一个流， 然后由此出发， 设法逐渐增大流值。 这里假定弧的容量为正整数 (若弧的容量为有理数， 则可化为整数 后再进行) 。 令 uij f ij , 当(i, j )为前向弧 ， δ ij = 当(i, j )为后向弧 f ij , δ = min{δ ij } 则在这条可增广轨上每条前向弧的流都可以增加一个量 δ , 而 相应的后向弧的流可减少 δ ,这样就可使得网络的流量获得增加， 同时可以使每条弧的流量不超过它的容量， 而且保持为正， 也不影 响其它弧的流量。总之，网络中 f 可增广链的存在是有意义的， 因为这意味着 f 不是最大流。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第2讲 最大流与最小费用流(13)在线全文阅读。