山大《運(yùn)籌學(xué)》課件06圖與網(wǎng)絡(luò)分析-7最小費(fèi)用流問題

1、第七節(jié) 最小費(fèi)用流問題最小費(fèi)用流算法 規(guī)劃形式 算法步驟 算法復(fù)雜性運(yùn)輸問題 對(duì)偶規(guī)劃 算法步驟規(guī)劃形式規(guī)劃形式續(xù)一原始規(guī)劃P規(guī)劃形式續(xù)二對(duì)偶規(guī)劃D最小費(fèi)用流算法的步驟第1步(開始) 讓所有的流xij=0，所有點(diǎn)對(duì)應(yīng)的數(shù)p(i)=0。第2步(決定哪些弧可以改變流量) 用I表示這樣的弧集合使p(j)-p(i)=wij，同時(shí)xij0 用Q表示不在IR中的弧集合。最小費(fèi)用流算法的步驟第3步(改變流量)用最大流算法，在IR上找增廣路，增加流量。如果從s到t的流量已經(jīng)是v，那么計(jì)算停止，已經(jīng)得到一個(gè)流量是v的最小費(fèi)用流。如果從s到t不能再增加流量，檢查在QIR中是否能找到增廣路。如果不能找到增廣路，那么

2、該網(wǎng)絡(luò)的最大流達(dá)不到v；如果在QIR中能找到增廣路，就轉(zhuǎn)入第4步。第4步(改變頂點(diǎn)的p(i )值)把所有點(diǎn)分成兩類：S是標(biāo)上號(hào)的點(diǎn)的集合，T是標(biāo)不上號(hào)的點(diǎn)的集合，讓S中的點(diǎn)p(i )值不變，T的點(diǎn)p(i )值全部加1，再轉(zhuǎn)回第2步。續(xù)例最小費(fèi)用流算法的復(fù)雜性設(shè)網(wǎng)絡(luò)的點(diǎn)數(shù)為n，弧數(shù)為m，弧的最大容量為w算法的循環(huán)次數(shù)取決于點(diǎn)的p(i)值修正的次數(shù)，最多進(jìn)行mw次因此第2步的計(jì)算量為O(m2w)如果最大流值為v，則留增廣最多進(jìn)行v次所以第3步的計(jì)算量為O(nw)第4步的計(jì)算量為O(nmw)所以，總的計(jì)算量為O(m2w+nmw)運(yùn)輸問題ai表示發(fā)點(diǎn)i可供應(yīng)的產(chǎn)品數(shù)量 bj表示收點(diǎn)j所需的產(chǎn)品數(shù)量wij表示從發(fā)點(diǎn)i到收點(diǎn)j的單位產(chǎn)品運(yùn)輸費(fèi)用xij表示從發(fā)點(diǎn)i分配給收點(diǎn)j的產(chǎn)品數(shù)量對(duì)偶規(guī)劃算法步驟第1步(開始) 任給原始規(guī)劃的可行解xij第2步(計(jì)算對(duì)偶解) 對(duì)于原始規(guī)劃的可行解xij，計(jì)算出對(duì)偶規(guī)劃的一個(gè)解ui,vj第3步(計(jì)算檢驗(yàn)數(shù)) 對(duì)于對(duì)偶規(guī)劃的解ui,vj，計(jì)算若所有的 均非負(fù)，則計(jì)算結(jié)束，這時(shí)得到的xij和ui,vj分別為原始規(guī)劃和對(duì)偶規(guī)劃的最優(yōu)解；否則，轉(zhuǎn)第4步算法步驟續(xù)第4步(調(diào)整原始可行解) 令即選擇xst進(jìn)入基。對(duì)應(yīng)于網(wǎng)絡(luò)中，即在支撐樹上加入弧(s,t)，從而得到一個(gè)回路。并選擇其流量xst=，使這個(gè)回路上的流量