【正文】 ( 2nmO36 最小費(fèi)用流問(wèn)題 ? 網(wǎng)絡(luò)流的費(fèi)用 ? 在實(shí)際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問(wèn)題，不僅涉及流量，而且還有費(fèi)用的因素。 ? 網(wǎng)絡(luò)的每一條邊 (v,w)除了給定容量 cap(v,w)外，還定義了一個(gè)單位流量費(fèi)用 cost(v,w)。對(duì)于網(wǎng)絡(luò)中一個(gè)給定的流 flow， 其費(fèi)用定義為： ? 2 最小費(fèi)用流問(wèn)題 ? 給定網(wǎng)絡(luò) G， 要求 G的一個(gè)最大用流 flow， 使流的總費(fèi)用最小。 ? 3 最小費(fèi)用可行流問(wèn)題 ? 給定多源多匯網(wǎng)絡(luò) G， 要求 G的一個(gè)可行流 flow， 使可行流的總費(fèi)用最小。 ? 可行流問(wèn)題等價(jià)于最大流問(wèn)題。最小費(fèi)用可行流問(wèn)題也等價(jià)于最小費(fèi)用流問(wèn)題。 ? ? ?? Ewv wvf l o wwvtf l o wt ),( ),(),(c o s)(c o s37 消圈算法 ? 1 算法基本思想 ? 最小費(fèi)用流問(wèn)題有關(guān)的算法中，仍然沿用殘流網(wǎng)絡(luò)的概念。 ? 此時(shí)，殘流網(wǎng)絡(luò)中邊的費(fèi)用定義為： ? int costRto(int v) { return from(v) ? pcost : pcost。 } ? 當(dāng)殘流網(wǎng)絡(luò)中的邊是向前邊時(shí)，其費(fèi)用不變。 ? 當(dāng)殘流網(wǎng)絡(luò)中的邊是向后邊時(shí)，其費(fèi)用為原費(fèi)用的負(fù)值。 ? 由于殘流網(wǎng)絡(luò)中存在負(fù)費(fèi)用邊，因此殘流網(wǎng)絡(luò)中就不可避免地會(huì)產(chǎn)生負(fù)費(fèi)用圈。 ? 在與最小費(fèi)用流問(wèn)題有關(guān)的算法中，負(fù)費(fèi)用圈是一個(gè)重要概念。 ? 最小費(fèi)用流問(wèn)題的最優(yōu)性條件 ? 網(wǎng)絡(luò) G的最大流 flow是 G的一個(gè)最小費(fèi)用流的充分且必要條件是 flow所相應(yīng)的殘流網(wǎng)絡(luò)中沒(méi)有負(fù)費(fèi)用圈。 38 ? 最小費(fèi)用流的消圈算法 步驟 0： 用最大流算法構(gòu)造最大流 flow。 步驟 1： 如果殘量網(wǎng)絡(luò)中不存在負(fù)費(fèi)用圈，則計(jì)算結(jié)束，已經(jīng)找到最小費(fèi)用流； 否則轉(zhuǎn)步驟 2。 步驟 2： 沿找到的負(fù)費(fèi)用圈增流，并轉(zhuǎn)步驟 1。 39 ? 3 算法的計(jì)算復(fù)雜性 ? 給定網(wǎng)絡(luò)中有 n個(gè)頂點(diǎn)和 m條邊，且每條邊的容量不超過(guò) M， 每條邊的費(fèi)用不超過(guò) C。 ? 最大流的費(fèi)用不超過(guò) mCM， 而每次消去負(fù)費(fèi)用圈至少使得費(fèi)用下降 1個(gè)單位，因此最多執(zhí)行 mCM次找負(fù)費(fèi)用圈和增流運(yùn)算。 ? 用 BellmanFord算法找 1次負(fù)費(fèi)用圈需要 O(mn)計(jì)算時(shí)間。 ? 最小費(fèi)用流的消圈算法在最壞情況下需要計(jì)算時(shí)間 )( 2 nCMmO40 最小費(fèi)用路算法 ? 1 算法基本思想 ? 消圈算法首先找到網(wǎng)絡(luò)中的一個(gè)最大流，然后通過(guò)消去負(fù)費(fèi)用圈使費(fèi)用降低。 ? 最小費(fèi)用路算法不用先找最大流，而是用類似于求最大流的增廣路算法的思想，不斷在殘流網(wǎng)絡(luò)中尋找從源 s到匯 t的最小費(fèi)用路，然后沿最小費(fèi)用路增流，直至找到最小費(fèi)用流。 ? 殘流網(wǎng)絡(luò)中從源 s到匯 t的最小費(fèi)用路是殘流網(wǎng)絡(luò)中從 s到 t的以費(fèi)用為權(quán)的最短路。 ? 殘流網(wǎng)絡(luò)中邊的費(fèi)用定義為： ? 當(dāng)殘流網(wǎng)絡(luò)中邊 (v,w)是向前邊時(shí)，其費(fèi)用為 cost(v,w)； ? 當(dāng) (v,w)是向后邊時(shí)，其費(fèi)用為 cost(w,v)。 ?????????PwvvwtPwvwvtwvwt),(),(c o s),(),(c o s),(41 最小費(fèi)用流的最小費(fèi)用路算法 步驟 0： 初始可行 0流。 步驟 1： 如果不存在最小費(fèi)用路，則計(jì)算結(jié)束，已經(jīng)找到最小費(fèi)用流； 否則用最短路算法在殘流網(wǎng)絡(luò)中找從 s到 t的最小費(fèi)用可增廣路，轉(zhuǎn)步驟 2。 步驟 2： 沿找到的最小費(fèi)用可增廣路增流，并轉(zhuǎn)步驟 1。 42 ? 3 算法的計(jì)算復(fù)雜性 ? 算法的主要計(jì)算量在于連續(xù)尋找最小費(fèi)用路并增流。 ? 給定網(wǎng)絡(luò)中有 n個(gè)頂點(diǎn)和 m條邊，且每條邊的容量不超過(guò) M， 每條邊的費(fèi)用不超過(guò) C。 ? 每次增流至少使得流值增加 1個(gè)單位，因此最多執(zhí)行 M次找最小費(fèi)用路算法。 ? 如果找 1次最小費(fèi)用路需要 s(m,n,C)計(jì)算時(shí)間，則求最小費(fèi)用流的最小費(fèi)用路算法需要O(Ms(m,n,C))計(jì)算時(shí)間。 43 網(wǎng)絡(luò)單純形算法 ? 1 算法基本思想 ? 消圈算法的計(jì)算復(fù)雜度不僅與算法找到的負(fù)費(fèi)用圈有關(guān)，而且與每次找負(fù)費(fèi)用圈所需的時(shí)間有關(guān)。 ? 網(wǎng)絡(luò)單純形算法是從解線性規(guī)劃問(wèn)題的單純形算法演變而來(lái)，但從算法的運(yùn)行機(jī)制來(lái)看，可以將網(wǎng)絡(luò)單純形算法看作另一類消圈算法。 ? 其基本思想是用一個(gè)可行支撐樹(shù)結(jié)構(gòu)來(lái)加速找負(fù)費(fèi)用圈的過(guò)程。 ? 對(duì)于給定的網(wǎng)絡(luò) G和一個(gè)可行流，相應(yīng)的 可行支撐樹(shù) 定義為 G的一棵包含所有弱流邊的支撐樹(shù)。 ? 網(wǎng)絡(luò)單純形算法的第一步是構(gòu)造可行支撐樹(shù)。 ? 從一個(gè)可行流出發(fā)，不斷找由弱流邊組成的圈，然后沿找到的弱流圈增流，消除所有弱流圈。 ? 在剩下的所有弱流邊中加入零流邊或飽和邊構(gòu)成一棵可行支撐樹(shù)。 ? 在可行支撐樹(shù)結(jié)構(gòu)的基礎(chǔ)上，網(wǎng)絡(luò)單純形算法通過(guò)頂點(diǎn)的勢(shì)函數(shù)，巧妙地選擇非樹(shù)邊，使它與可行支撐樹(shù)中的邊構(gòu)成負(fù)費(fèi)用圈。然后，沿找到的負(fù)費(fèi)用圈增流。 44 ? 定義了頂點(diǎn)的勢(shì)函數(shù) Φ后 ， 殘流網(wǎng)絡(luò)中各邊 (v,w)的勢(shì)費(fèi)用定義為： ? c*(v,w)=c(v,w)(Φ(v) Φ(w))。 ? 其中 ， c(v,w)是 (v,w)在殘流網(wǎng)絡(luò)中的費(fèi)用 。 ? 如果對(duì)可行支撐樹(shù)中所有邊 （ v,w） 有 c*(v,w)=0， 則相應(yīng)的勢(shì)函數(shù) Φ是一個(gè)有效勢(shì)函數(shù) 。 ? 對(duì)于一棵可行支撐樹(shù) ， 如果將一條非樹(shù)邊加入可行支撐樹(shù) ， 產(chǎn)生殘流網(wǎng)絡(luò)中的一個(gè)負(fù)費(fèi)用圈 ， 則稱該非樹(shù)邊為一條可用邊 。 ? 可用邊定理： 給定一棵可行支撐樹(shù)及其上的一個(gè)有效勢(shì)函數(shù) ， 非樹(shù)邊 e是一條可用邊的充分必要條件是 ， e是一條有正勢(shì)費(fèi)用的飽和邊 ， 或 e是一條有負(fù)勢(shì)費(fèi)用的零流邊 。 ? 事實(shí)上 ， 設(shè) e=(v,w)。 ? 邊 e與樹(shù)邊 t1,t2,… ,td構(gòu)成一個(gè)圈 cycle: t1,t2,… ,td， t1, 其中 v=t1， w=td 。 ? 按照邊的勢(shì)費(fèi)用的定義有： ? c(w,v)=c*(w,v)+ Φ(td) Φ(t1) ? c(t1,t2)= Φ(t1) Φ(t2) ? c(t2,t3)= Φ(t2) Φ(t3) ? … ? c(td1, td)= Φ(td1) Φ(td) 45 ? 各式相加得： cost(cycle)=c*(w,v)。 ? 由此可見(jiàn) ， e是一條可用邊當(dāng)且僅當(dāng) cost(cycle)0； ? 當(dāng)且僅當(dāng) c*(w,v)0； ? 當(dāng)且僅當(dāng) e是一條有正勢(shì)費(fèi)用的飽和邊或 e是一條有負(fù)勢(shì)費(fèi)用的零流邊 。 ? 最優(yōu)性條件： 給定網(wǎng)絡(luò) G的可行流 flow及相應(yīng)的可行支撐樹(shù) T， 如果不存在 T的可用邊 ， 則flow是一個(gè)最小費(fèi)用流 。 ? 事實(shí)上 ， 如果不存在 T的可用邊 ， 則由可用邊的定義知?dú)埩骶W(wǎng)絡(luò)中沒(méi)有負(fù)費(fèi)用圈 。 又由最小費(fèi)用流問(wèn)題的最優(yōu)性條件知 flow是一個(gè)最小費(fèi)用流 。 最小費(fèi)用流的網(wǎng)絡(luò)單純形算法 步驟 0： 構(gòu)造 flow為 初始可行 0流 。 構(gòu)造相應(yīng)的可行支撐樹(shù) T和有效的頂點(diǎn)勢(shì)函數(shù)。 步驟 1： 如果不存在 T的可用邊 ，則計(jì)算結(jié)束，已經(jīng)找到 最小費(fèi)用流 ；否則轉(zhuǎn)步驟 2。 步驟 2： 選取 T的一條可用邊與 T的樹(shù)邊構(gòu)成負(fù)費(fèi)用圈，沿找到的負(fù)費(fèi)用圈增流， 從 T中刪去一條飽和邊或零流邊，重構(gòu)可行支撐樹(shù)，并轉(zhuǎn)步驟 1。 46 ? 3 算法的計(jì)算復(fù)雜性 ? 給定網(wǎng)絡(luò)中有 n個(gè)頂點(diǎn)和 m條邊 ， 且每條邊的容量不超過(guò) M， 每條邊的費(fèi)用不超過(guò) C。 ? 最大流的費(fèi)用不超過(guò) mCM， 而每次消去負(fù)費(fèi)用圈至少使得費(fèi)用下降 1個(gè)單位 ， 因此最多執(zhí)行 mCM次找負(fù)費(fèi)用圈和增流運(yùn)算 。 ? 用網(wǎng)絡(luò)單純形算法找 1次負(fù)費(fèi)用圈需要 O(m)計(jì)算時(shí)間 。 ? 因此 ， 求最小費(fèi)用流的網(wǎng)絡(luò)單純形算法在最壞情況下需要計(jì)算時(shí)間 )( 2CMmO47 課后作業(yè) ? 習(xí)題 83， 810， 819， 825， 828