《山东大学《运筹学》课件06图与网络分析-7最小费用流问题》由会员分享，可在线阅读，更多相关《山东大学《运筹学》课件06图与网络分析-7最小费用流问题（11页珍藏版）》请在金锄头文库上搜索。
1、第七节第七节 最小费用流问题最小费用流问题最小费用流算法最小费用流算法 规划形式规划形式 算法步骤算法步骤 算法复杂性算法复杂性运输问题运输问题 对偶规划对偶规划 算法步骤算法步骤规划形式规划形式规划形式规划形式续一续一原始规划原始规划P规划形式规划形式续二续二对偶规划对偶规划D最小费用流算法的步骤最小费用流算法的步骤第第1步步(开始开始) 让所有的流让所有的流xij=0，所有点对应的数，所有点对应的数p(i)=0。第第2步步(决定哪些弧可以改变流量决定哪些弧可以改变流量) 用用I表示这样的弧集合使表示这样的弧集合使p(j)-p(i)=wij，同时，同时xij0 用用Q表示不在表示不在IR中的
2、弧集合。中的弧集合。最小费用流算法的步骤最小费用流算法的步骤第第3步步(改改变变流流量量)用用最最大大流流算算法法，在在IR上上找找增增广广路路，增增加加流量。流量。如如果果从从s到到t的的流流量量已已经经是是v，那那么么计计算算停停止止，已已经经得得到到一一个个流量是流量是v的最小费用流。的最小费用流。如如果果从从s到到t不不能能再再增增加加流流量量，检检查查在在QIR中中是是否否能能找找到到增增广广路路。如如果果不不能能找找到到增增广广路路，那那么么该该网网络络的的最最大大流流达达不不到到v；如果在；如果在QIR中能找到增广路，就转入第中能找到增广路，就转入第4步。步。第第4 4步步(改变
3、顶点的改变顶点的p(i )值值)把把所所有有点点分分成成两两类类：S是是标标上上号号的的点点的的集集合合，T是是标标不不上上号号的的点点的的集集合合，让让S中中的的点点p(i )值值不不变变，T的的点点p(i )值值全全部部加加1，再转回第，再转回第2步。步。续续例例最小费用流算法最小费用流算法的复杂性的复杂性设网络的点数为设网络的点数为n，弧数为，弧数为m，弧的最大容量为，弧的最大容量为w算算法法的的循循环环次次数数取取决决于于点点的的p(i)值值修修正正的的次次数数，最最多多进行进行mw次次因此因此第第2 2步的计算量步的计算量为为O(m2w)如果最大流值为如果最大流值为v，则留增广最多进
4、行，则留增广最多进行v次次所以所以第第3 3步的计算量步的计算量为为O(nw)第第4步的计算量步的计算量为为O(nmw)所以，所以，总的计算量总的计算量为为O(m2w+nmw)运输问题运输问题ai表示发点表示发点i可供应的产品数量可供应的产品数量 bj表示收点表示收点j所需的产品数量所需的产品数量wij表示从发点表示从发点i到收点到收点j的单位产品的单位产品运输费用运输费用xij表示从发点表示从发点i分配给收点分配给收点j的的产品数量产品数量对偶规划对偶规划算法步骤算法步骤第第1步步(开始开始) 任给原始规划的可行解任给原始规划的可行解xij第第2步步(计算对偶解计算对偶解) 对于原始规划的可
5、行解对于原始规划的可行解xij，计，计算出对偶规划的一个解算出对偶规划的一个解ui,vj第第3步步(计算检验数计算检验数) 对于对偶规划的解对于对偶规划的解ui,vj，计算，计算若所有的若所有的 均非负，则计算结束，这时得到的均非负，则计算结束，这时得到的xij和和ui,vj分别为原始规划和对偶规划的最优解；否则，分别为原始规划和对偶规划的最优解；否则，转第转第4步步算法步骤算法步骤续续第第4步步(调整原始可行解调整原始可行解) 令令即选择即选择xst进入基。对应于网络中，即在支撑树上加进入基。对应于网络中，即在支撑树上加入弧入弧(s,t)，从而得到一个回路。并选择其流量，从而得到一个回路。并选择其流量xst=，使这个回路上的流量通过加，使这个回路上的流量通过加 或减或减 以达到去掉以达到去掉一条弧的目的，从而得到一个新的被改进的原始可一条弧的目的，从而得到一个新的被改进的原始可行解行解xst，转第，转第2步步例例
