第7节最小费用流问题

《第7节最小费用流问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七节最小费用流问题最小费用流算法规划形式算法步骤算法复杂性运输问题对偶规划算法步骤规划形式规划形式续一原始规划P规划形式续二对偶规划D最小费用流算法的步骤第1步(开始)让所有的流xij=0，所有点对应的数p(i)=0。第2步(决定哪些弧可以改变流量)用I表示这样的弧集合使p(j)-p(i)=wij，同时xij0用Q表示不在I∪R中的弧集合。最小费用流算法的步骤第3步(改变流量)用最大流算法，在I∪R上找增广路，增加流量。如果从s到t的流量已经是v，那么计算停止，已经得到一个流量是v的最小

2、费用流。如果从s到t不能再增加流量，检查在Q∪I∪R中是否能找到增广路。如果不能找到增广路，那么该网络的最大流达不到v；如果在Q∪I∪R中能找到增广路，就转入第4步。第4步(改变顶点的p(i)值)把所有点分成两类：S是标上号的点的集合，T是标不上号的点的集合，让S中的点p(i)值不变，T的点p(i)值全部加1，再转回第2步。续例最小费用流算法的复杂性设网络的点数为n，弧数为m，弧的最大容量为w算法的循环次数取决于点的p(i)值修正的次数，最多进行mw次因此第2步的计算量为O(m2w)如果最大流值为v，则留增广最多进行v次所以第3步的计算量为O(nw)第4步的

3、计算量为O(nmw)所以，总的计算量为O(m2w+nmw)运输问题ai表示发点i可供应的产品数量bj表示收点j所需的产品数量wij表示从发点i到收点j的单位产品运输费用xij表示从发点i分配给收点j的产品数量对偶规划算法步骤第1步(开始)任给原始规划的可行解{xij}第2步(计算对偶解)对于原始规划的可行解{xij}，计算出对偶规划的一个解{ui,vj}第3步(计算检验数)对于对偶规划的解{ui,vj}，计算若所有的均非负，则计算结束，这时得到的{xij}和{ui,vj}分别为原始规划和对偶规划的最优解；否则，转第4步算法步骤续第4步(调整原始可行解)令即选

4、择xst进入基。对应于网络中，即在支撑树上加入弧(s,t)，从而得到一个回路。并选择其流量xst=θ，使这个回路上的流量通过加θ或减θ以达到去掉一条弧的目的，从而得到一个新的被改进的原始可行解{xst}，转第2步例