图与网络_最小费用流.ppt

《图与网络_最小费用流.ppt》由会员分享，可在线阅读，更多相关《图与网络_最小费用流.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学讲课教师：汤建影南京航空航天大学经济与管理学院第五节 最小费用流问题n什么是最小费用流问题？n求解最小费用流的赋权图法n求解最小费用流的复合标号法一、什么是最小费用流n给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。nc为弧的容量，b为弧上通过单位流量的费用二、求解最小费用流的赋权图法n基本思想：n从零流量开始，在始点到终点的所有可能增加流量的增广链中寻求总费用最小的链，并首先在这条链上增加流量，得到流量为 的最小费用流。n再对 寻求所有可能增加流量的增广链，并在其中总费用最小的增广链上继续增加流量，得到流量为 的最小费用流。n依此类推，直到网络中

2、不再存在增广链，不能再增加流量为止。二、求解最小费用流的赋权图法n增广链费用，最小费用增广链。n对于最小费用可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。n给定初始最小费用可行流，求最小费用增广链，若存在，则沿该增广链调整网络流，直到达到给定的网络流或不存在增广链为止，后一种情况为最小费用最大流。n若给定网络流超过最大流，则不可能实现。如何求最小费用增广链？n生成最小费用可行流的剩余网络：n将饱和弧反向n将非饱和非零流弧加一反向弧n零流弧不变n所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数n剩余网络又叫长度网络，本教材叫做赋权图。n最小费用增广链对应剩余网络的最短路剩

3、余网络的最短路最小费用流的实例第一次剩余网络最短路第一次调整网络流第二次剩余网络最短路第二次调整网络流第三次剩余网络的最短路第三次调整网络流剩余网络已不存在最短路最小费用最大流n制定一个总运量为7且总运费最小的运输方案：最小费用流问题n制定使运量最大且总运费最小的运输方案：最小费用流问题n若规定网络流为7，则第二次调整量应为2，而不是3。n最小费用与网络流的关系是凸的，即随着流的增加，单位流的费用在增加。请见下页的图。三、求解最小费用流的复合标号法n将求最短路的标号法和求最大流的标号法相结合，即在求增广链的标号后加上一个距离标号，成为一组三标号，距离标号应采用修正标号法。并采用T标号和P标号的记法。n下面以前例为例来说明符合标号的应用。第一次迭代第二次迭代第三次迭代最后结果提示思考n最短路问题、最大流问题可以看作最小费用流的特殊情况，请分析如何将最小费用流问题特化成最短路问题和最大流问题？n运输问题和指派问题可以用最小费用流问题建模，请将它们化为最小费用流问题。习题nP.287，习题10、11。