教案圖與網(wǎng)絡(luò)最小費用流.ppt

1、運籌學(xué),講課教師：湯建影,南京航空航天大學(xué)經(jīng)濟與管理學(xué)院,第五節(jié) 最小費用流問題,什么是最小費用流問題？ 求解最小費用流的賦權(quán)圖法 求解最小費用流的復(fù)合標(biāo)號法,一、什么是最小費用流,給定網(wǎng)絡(luò)N=(V,A,c,b)和經(jīng)過網(wǎng)絡(luò)的流量v，求流在網(wǎng)絡(luò)上的最佳分布，使總費用最小。 c為弧的容量，b為弧上通過單位流量的費用,二、求解最小費用流的賦權(quán)圖法,基本思想： 從零流量開始，在始點到終點的所有可能增加流量的增廣鏈中尋求總費用最小的鏈，并首先在這條鏈上增加流量，得到流量為 的最小費用流。 再對 尋求所有可能增加流量的增廣鏈，并在其中總費用最小的增廣鏈上繼續(xù)增加流量，得到流量為 的最小費用流。 依此類推，

2、直到網(wǎng)絡(luò)中不再存在增廣鏈，不能再增加流量為止。,二、求解最小費用流的賦權(quán)圖法,增廣鏈費用，最小費用增廣鏈。 對于最小費用可行流，沿最小費用增廣鏈調(diào)整流，可使流增加，并保持流費用最小。 給定初始最小費用可行流，求最小費用增廣鏈，若存在，則沿該增廣鏈調(diào)整網(wǎng)絡(luò)流，直到達(dá)到給定的網(wǎng)絡(luò)流或不存在增廣鏈為止，后一種情況為最小費用最大流。 若給定網(wǎng)絡(luò)流超過最大流，則不可能實現(xiàn)。,如何求最小費用增廣鏈？,生成最小費用可行流的剩余網(wǎng)絡(luò)： 將飽和弧反向 將非飽和非零流弧加一反向弧 零流弧不變 所有正向弧的權(quán)為該弧的費用，反向弧的權(quán)為該弧費用的相反數(shù) 剩余網(wǎng)絡(luò)又叫長度網(wǎng)絡(luò)，本教材叫做賦權(quán)圖。 最小費用增廣鏈對應(yīng)剩余

3、網(wǎng)絡(luò)的最短路,最小費用流的實例,第一次剩余網(wǎng)絡(luò)最短路,第一次調(diào)整網(wǎng)絡(luò)流,第二次剩余網(wǎng)絡(luò)最短路,第二次調(diào)整網(wǎng)絡(luò)流,第三次剩余網(wǎng)絡(luò)的最短路,第三次調(diào)整網(wǎng)絡(luò)流,剩余網(wǎng)絡(luò)已不存在最短路,最小費用最大流,制定一個總運量為7且總運費最小的運輸方案：最小費用流問題 制定使運量最大且總運費最小的運輸方案：最小費用流問題 若規(guī)定網(wǎng)絡(luò)流為7，則第二次調(diào)整量應(yīng)為2，而不是3。 最小費用與網(wǎng)絡(luò)流的關(guān)系是凸的，即隨著流的增加，單位流的費用在增加。請見下頁的圖。,三、求解最小費用流的復(fù)合標(biāo)號法,將求最短路的標(biāo)號法和求最大流的標(biāo)號法相結(jié)合，即在求增廣鏈的標(biāo)號后加上一個距離標(biāo)號，成為一組三標(biāo)號，距離標(biāo)號應(yīng)采用修正標(biāo)號法。并采用T標(biāo)號和P標(biāo)號的記法。 下面以前例為例來說明符合標(biāo)號的應(yīng)用。,第一次迭代,第二次迭代,第三次迭代,最后結(jié)果,提示思考,最短路問題、最大流問題可以看作最小費用流的特殊情況，請分析如何將最小費用流問題特化成最短路問題和最大流問題？ 運輸