6.-5最小费用最大流问题ppt课件

第v节最小成本最大流问题，1，1，基本概念1，最小成本最大流问题是什么？通过从容量网络D=(V，a，b)(称为成本容量网络)中获取最大流x，为每个圆弧提供单位流量成本，总传输流量成本c(x)=cij xij是最小优化问题之一。其中bij表示圆弧(VI，VJ)上的容量，xij表示圆弧(VI，VJ)上的流，cij表示圆弧(VI，VJ)的单位流通过的成本。2，2，最小成本流与成本容量网络，具有相同流f的可执行流中总成本最小的可执行流称为此成本容量网络流量f的最小成本流，简单地说是流f的最小成本流。3，如上节所示，找到最大流的方法是在任何可行流中，找到此流的增量链。沿调整f，尝试为新的可行流查找到最大流的扩展链。现在，要找到最小成本的最大流，首先将f沿可实现流f的增量链调整为=1，以获得新的可实现流f ，其中C(f)=v (f) 1比C(f)增加了多少(总传输流成本)？4，3，增量链成本沿可实现流X的增量链(流修正路径)调整为修正量=1，要获得新的可实现流，C()-C(X)为增量链成本。5，增加链成本是调整单位调整量的可行流量时支付的成本；修正量=1时，流量f()=f(x)1；C()-C(X)=，6，2，解决最小成本最大流问题的双方法，1，解决方法：(1)始终将网络中的可行流保持为最小成本流，然后持续调整流量，使其逐渐增加，最终成为最小成本的最大流。(2)始终保持可行流是最大的流，通过持续调整，成本逐渐降低，最终成为最大流的最小成本流。7，2，算法原理(1)如果定理X是流f(X)的最小成本流，是所有扩展链中的最小成本扩展链，则沿调整X的新可执行流是流f()的最小成本流。8，(2)实施思想基于根据上述定理找到最小成本增加链，调整该链中的流，增加流量，然后获得最小成本流的第一解决方案路径。重复此操作，直到达到最小成本最大流量。9，对偶方法原理和步骤，查找最大流，Ford算法查找从vs到vt的最短扩展链，调整流量，成本最低的可执行流，将零流用作初始可执行流，Yes，绘制扩展成本网络，No，流是否等于最大流？最小成本最大流，确保最大流量，确保最小成本，10，使用实施的核心配置增长成本网络图(即扩展成本网络图)，通过最短路径算法查找最小成本增长链。为什么？原因：正向饱和弧不显示，反向零流弧不显示。-如果不建立增长成本网络，则无法调整流(1)饱和弧，无法减少流量。(2)不饱和弧，流量可以增加，不能减少。增量链流量调整：正弧增加流量，反转弧减少流量。11，增量成本网络图的配置方法将网络中的每个圆弧(vi，vj)变成相反方向的圆弧对，形成通向所有方向的“道路”，权重定义如下：12，未在简化上述想法上绘制相应的圆弧，具体配置增量成本网络图如下。在零流弧中保持原始弧不变，使用单位成本作为权重：wij=cij:13，在不饱和弧中，原始弧按单位成本加权，圆弧(虚线弧)按单位成本的负值加权：14，从饱和弧中删除原始弧，圆因此，在容量网络中查找最小成本增长链等于在增广成本网络图(扩展成本网络图)中查找从始发点到接收点的最短路。将找到的最短路径恢复到原始网络图(虚线圆弧从原始图变为反向圆弧)。步骤16，3:使用第一步- Ford-Fukerson算法对相应容量网络的最大流量进行fmax取得；这个阶段的作用是什么？)，第二阶段-采取零流的初始可实现流，并执行流0的最小费用流(为什么？)，17，3阶段-通常使用k-1迭代，最小成本流X(k-1)，当前可行流的增量成本网络图W(X(k-1)，使用最短路算法查找从发射点到接收点的最短路径。如果没有段落，则X(k-1)为最小成本最大流，并停止重复。否则，请继续下一步。步骤18，4-将最短路径恢复到原始网络图的最小成本增加链，并调整中的可执行流X(k-1)，以获得在流量为fmax的情况下结束迭代的新的可执行流图。否则，请转到第一步，然后继续下一个迭代过程。19，4，是，增广费网络图(容量费用图(bij，cij)、可行流程图(流量网络(bij，cij，xij)、最大流程图fmax=11(非标准费用)所有权利大于0，可以使用d标签法找到最短路径：就是最低成本增长链。流量调整1=min8-0，5-0，7-0=5总流量f1=5最小成本增加链成本 cij=1 2 1=4 总成本C1=45=20，2 1，2次迭代用目录法寻找最短路径：车也是最低成本增加链。流量调整量2=min10-0，2-0(7-5)=2，总流量=原始流量新流量=5 2=7；最小成本增加链成本 cij=4 1=5 总成本C2=原始成本增加成本=20 52=30，22，0流弧保持原始边缘，另外，不饱和弧添加弧后，饱和弧删除原始边缘，添加反向虚线弧。最短路是最小成本增加链作为列表方法。流量调整量3=min3，10，4=3，总流量=原始流量新流量=7 3=10；最小成本增加链成本 cij=1 3 2=6 总成本C2=原始成本增加成本=30 63=48，第三次迭代，23， 0流弧保持原始边缘，还添加不饱和弧，饱和弧删除原始边缘，添加相反虚线弧；采用列表方法，最短路径相应的最小成本增加链：流量调整4=min8，5，7，1=1，总流量=原始流量增加流=10 1=11；最小成本增加链成本 cij=4-2 3 2=7 总成本C2=原始成本增加成本=48 71=55。如果因为总流11达到了最大流而停止迭代，则当前可能的流图就是最大流图。第4次迭代，24，示例-最小成本-最大流问题，在下图中查找从网络到的最小成本最大流。图中圆弧的编号为。、25、(0)查找在以前的计算中已知的最大网络流量。使用0流作为初始可执行流。扩展成本网络与原始网络相同，(1)第一次迭代：使用Ford算法查找最小扩展链，路径为vs-v3-V5-vt，26，调整流量：增加链：基于初始可能流量调整流量，(1)流还可以增加4，单位成本1。(2)流量也可以减少，当前流量减少6，每减少1流量减少1。28，使用Ford算法查找最小扩展链，路径为vs-v2-V5-