網(wǎng)絡(luò)最大流問題的應(yīng)用

朱淑芹++杜海峰++崔鵬飛等

摘 要：最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。該文列舉了網(wǎng)絡(luò)最大流問題在匹配問題，圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用。

關(guān)鍵詞：組合優(yōu)化 線性規(guī)劃 網(wǎng)絡(luò)優(yōu)化 最大流 最小截

中圖分類號：F224 文獻標識碼：A 文章編號：1674-098X（2014）05（c）-0043-02

最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，也是特殊的線性規(guī)劃問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。因此許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。發(fā)現(xiàn)具體應(yīng)用問題和最大流或最小截問題的聯(lián)系是最大流問題或最小截問題應(yīng)用研究的關(guān)鍵[1]。

1 網(wǎng)絡(luò)最大流問題的數(shù)學(xué)描述

定義1[2]：對于以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C），其上的一個流，f是指從N的弧集A到R的一個函數(shù)，即對每條?。╥，j）賦予一個實數(shù)fig（稱為?。╥，j）的流量），如果流f滿足

（1）

則稱f為可行流。

考慮在以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C）：節(jié)點vs為網(wǎng)絡(luò)中唯一的源點，vt為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流f，此時稱流f的流量為ds，通常記為v或v（f），即v=v（f）=ds=-dt，最大流問題就是在N=（vs，vt，V，A，C）中找到流值最大的可行流（即最大流）。

因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：

（2）

2 網(wǎng)絡(luò)最大流問題的應(yīng)用

2.1 求最大匹配問題

2.2 求圖的邊連通度問題

定義5[4]設(shè)G=（V，E）是連通圖，如果e是G中的一條邊，且G-{e}不連通，則稱e是G的一條割邊。若E1是E的非空子集，G-E1不連通，但對E1的任何真子集E2都有G-E2連通，則稱E1是G中一個邊割集。割點構(gòu)成只含一個點的點割集。割邊構(gòu)成只含一條邊的邊割集。

定義6[4]設(shè)G是一個非平凡的連通圖，則我們稱λ（G）=min{|E1||E1是G的邊割集}為G的線連通度。即λ（G）是使得G不連通所必須刪除的邊的最小條數(shù)。求圖的邊連通度問題可轉(zhuǎn)化為求圖的權(quán)全為1的全局最小截問題，所謂全局最小截是指所有點對間最小截中的值最小的截，又最小截問題的對偶問題是最大流問題，故求圖的邊連通度問題可轉(zhuǎn)化為求弧的最大容量為1的最大流問題?，F(xiàn)以舉例說明，求圖3的連通度。

解：在5個點中任選兩點分別作為網(wǎng)絡(luò)中的源點和匯點，則可以組成10個網(wǎng)絡(luò)圖，若以v1為源點，v5為匯點，且各弧上的最大容量為1的最大流問題.如圖4所示。通過Ford-Fulkerson標號法求得最大流量為2。若以v1為源點，v3為匯點，且各弧上的最大容量為1的最大流問題如圖5所示。通過Ford-Fulkerson標號法求得最大流量為3，總之我們需要求10個網(wǎng)絡(luò)的最大流，限于篇幅不一一列舉，在這些最大流中最小的流量為2，所以圖的連通度為2。

2.3 資源分配問題

例 某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道；修建一座人行天橋；修建一條道路及道路維修。工期和所需勞動力如表1所示，公司共有120人，任一項工程在一個月內(nèi)的勞動力不能超過80人，則公司如何分配勞動力完成所有工程。

解：將工程計劃用如下網(wǎng)絡(luò)圖6表示，其中標號5、6、7、8分別表示5～8月份，Ai， Bi，Ci，Di表示工程在第i個月內(nèi)的完成部分，用弧表示某月完成某項工程的狀態(tài)，弧的流量為勞動力限制。合理安排每個月個工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求上圖從發(fā)點到收點的最大流問題。用Ford-Fulkerson標號法求得的一個最大流量方案如圖7所示，可知5月份有剩余勞動力20人，4項工程恰好按期完成。

3 結(jié)語

該文列舉、分析了網(wǎng)絡(luò)最大流問題在匹配問題、圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用并給出了對應(yīng)的解決方案。

參考文獻

[1] 張憲超，陳國良，萬穎.網(wǎng)絡(luò)最大流問題研究進展[J].計算機研究與進展，2003，40（9）：1281-1292.

[2] 《運籌學(xué)》教材編寫組，運籌學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

[3] 耿素云，屈婉玲.離散數(shù)學(xué)[M].北京：高等教育出版社，2004.

[4] GARY Chartrand，Ping Zhang.Introduction to Graph Theory[M].范益政等譯.北京：人民郵電出版社，2006.endprint

摘 要：最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。該文列舉了網(wǎng)絡(luò)最大流問題在匹配問題，圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用。

關(guān)鍵詞：組合優(yōu)化 線性規(guī)劃 網(wǎng)絡(luò)優(yōu)化 最大流 最小截

中圖分類號：F224 文獻標識碼：A 文章編號：1674-098X（2014）05（c）-0043-02

最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，也是特殊的線性規(guī)劃問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。因此許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。發(fā)現(xiàn)具體應(yīng)用問題和最大流或最小截問題的聯(lián)系是最大流問題或最小截問題應(yīng)用研究的關(guān)鍵[1]。

1 網(wǎng)絡(luò)最大流問題的數(shù)學(xué)描述

定義1[2]：對于以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C），其上的一個流，f是指從N的弧集A到R的一個函數(shù)，即對每條?。╥，j）賦予一個實數(shù)fig（稱為弧（i，j）的流量），如果流f滿足

（1）

則稱f為可行流。

考慮在以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C）：節(jié)點vs為網(wǎng)絡(luò)中唯一的源點，vt為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流f，此時稱流f的流量為ds，通常記為v或v（f），即v=v（f）=ds=-dt，最大流問題就是在N=（vs，vt，V，A，C）中找到流值最大的可行流（即最大流）。

因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：

（2）

2 網(wǎng)絡(luò)最大流問題的應(yīng)用

2.1 求最大匹配問題

2.2 求圖的邊連通度問題

定義5[4]設(shè)G=（V，E）是連通圖，如果e是G中的一條邊，且G-{e}不連通，則稱e是G的一條割邊。若E1是E的非空子集，G-E1不連通，但對E1的任何真子集E2都有G-E2連通，則稱E1是G中一個邊割集。割點構(gòu)成只含一個點的點割集。割邊構(gòu)成只含一條邊的邊割集。

定義6[4]設(shè)G是一個非平凡的連通圖，則我們稱λ（G）=min{|E1||E1是G的邊割集}為G的線連通度。即λ（G）是使得G不連通所必須刪除的邊的最小條數(shù)。求圖的邊連通度問題可轉(zhuǎn)化為求圖的權(quán)全為1的全局最小截問題，所謂全局最小截是指所有點對間最小截中的值最小的截，又最小截問題的對偶問題是最大流問題，故求圖的邊連通度問題可轉(zhuǎn)化為求弧的最大容量為1的最大流問題。現(xiàn)以舉例說明，求圖3的連通度。

解：在5個點中任選兩點分別作為網(wǎng)絡(luò)中的源點和匯點，則可以組成10個網(wǎng)絡(luò)圖，若以v1為源點，v5為匯點，且各弧上的最大容量為1的最大流問題.如圖4所示。通過Ford-Fulkerson標號法求得最大流量為2。若以v1為源點，v3為匯點，且各弧上的最大容量為1的最大流問題如圖5所示。通過Ford-Fulkerson標號法求得最大流量為3，總之我們需要求10個網(wǎng)絡(luò)的最大流，限于篇幅不一一列舉，在這些最大流中最小的流量為2，所以圖的連通度為2。

2.3 資源分配問題

例 某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道；修建一座人行天橋；修建一條道路及道路維修。工期和所需勞動力如表1所示，公司共有120人，任一項工程在一個月內(nèi)的勞動力不能超過80人，則公司如何分配勞動力完成所有工程。

解：將工程計劃用如下網(wǎng)絡(luò)圖6表示，其中標號5、6、7、8分別表示5～8月份，Ai， Bi，Ci，Di表示工程在第i個月內(nèi)的完成部分，用弧表示某月完成某項工程的狀態(tài)，弧的流量為勞動力限制。合理安排每個月個工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求上圖從發(fā)點到收點的最大流問題。用Ford-Fulkerson標號法求得的一個最大流量方案如圖7所示，可知5月份有剩余勞動力20人，4項工程恰好按期完成。

3 結(jié)語

該文列舉、分析了網(wǎng)絡(luò)最大流問題在匹配問題、圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用并給出了對應(yīng)的解決方案。

參考文獻

[1] 張憲超，陳國良，萬穎.網(wǎng)絡(luò)最大流問題研究進展[J].計算機研究與進展，2003，40（9）：1281-1292.

[2] 《運籌學(xué)》教材編寫組，運籌學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

[3] 耿素云，屈婉玲.離散數(shù)學(xué)[M].北京：高等教育出版社，2004.

[4] GARY Chartrand，Ping Zhang.Introduction to Graph Theory[M].范益政等譯.北京：人民郵電出版社，2006.endprint

摘 要：最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。該文列舉了網(wǎng)絡(luò)最大流問題在匹配問題，圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用。

關(guān)鍵詞：組合優(yōu)化 線性規(guī)劃 網(wǎng)絡(luò)優(yōu)化 最大流 最小截

中圖分類號：F224 文獻標識碼：A 文章編號：1674-098X（2014）05（c）-0043-02

最大流和它的對偶問題最小截問題是經(jīng)典的組合優(yōu)化問題，也是特殊的線性規(guī)劃問題，已有40多年的研究歷史，存在許多優(yōu)秀的算法和大量優(yōu)秀的代碼。因此許多問題轉(zhuǎn)化為最大流問題或最小截問題后可以得到十分有效的解決。發(fā)現(xiàn)具體應(yīng)用問題和最大流或最小截問題的聯(lián)系是最大流問題或最小截問題應(yīng)用研究的關(guān)鍵[1]。

1 網(wǎng)絡(luò)最大流問題的數(shù)學(xué)描述

定義1[2]：對于以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C），其上的一個流，f是指從N的弧集A到R的一個函數(shù)，即對每條弧（i，j）賦予一個實數(shù)fig（稱為?。╥，j）的流量），如果流f滿足

（1）

則稱f為可行流。

考慮在以V為節(jié)點集，A為弧集，C為最大容量集的網(wǎng)絡(luò)N=（V，A，C）：節(jié)點vs為網(wǎng)絡(luò)中唯一的源點，vt為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流f，此時稱流f的流量為ds，通常記為v或v（f），即v=v（f）=ds=-dt，最大流問題就是在N=（vs，vt，V，A，C）中找到流值最大的可行流（即最大流）。

因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：

（2）

2 網(wǎng)絡(luò)最大流問題的應(yīng)用

2.1 求最大匹配問題

2.2 求圖的邊連通度問題

定義5[4]設(shè)G=（V，E）是連通圖，如果e是G中的一條邊，且G-{e}不連通，則稱e是G的一條割邊。若E1是E的非空子集，G-E1不連通，但對E1的任何真子集E2都有G-E2連通，則稱E1是G中一個邊割集。割點構(gòu)成只含一個點的點割集。割邊構(gòu)成只含一條邊的邊割集。

定義6[4]設(shè)G是一個非平凡的連通圖，則我們稱λ（G）=min{|E1||E1是G的邊割集}為G的線連通度。即λ（G）是使得G不連通所必須刪除的邊的最小條數(shù)。求圖的邊連通度問題可轉(zhuǎn)化為求圖的權(quán)全為1的全局最小截問題，所謂全局最小截是指所有點對間最小截中的值最小的截，又最小截問題的對偶問題是最大流問題，故求圖的邊連通度問題可轉(zhuǎn)化為求弧的最大容量為1的最大流問題?，F(xiàn)以舉例說明，求圖3的連通度。

解：在5個點中任選兩點分別作為網(wǎng)絡(luò)中的源點和匯點，則可以組成10個網(wǎng)絡(luò)圖，若以v1為源點，v5為匯點，且各弧上的最大容量為1的最大流問題.如圖4所示。通過Ford-Fulkerson標號法求得最大流量為2。若以v1為源點，v3為匯點，且各弧上的最大容量為1的最大流問題如圖5所示。通過Ford-Fulkerson標號法求得最大流量為3，總之我們需要求10個網(wǎng)絡(luò)的最大流，限于篇幅不一一列舉，在這些最大流中最小的流量為2，所以圖的連通度為2。

2.3 資源分配問題

例 某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道；修建一座人行天橋；修建一條道路及道路維修。工期和所需勞動力如表1所示，公司共有120人，任一項工程在一個月內(nèi)的勞動力不能超過80人，則公司如何分配勞動力完成所有工程。

解：將工程計劃用如下網(wǎng)絡(luò)圖6表示，其中標號5、6、7、8分別表示5～8月份，Ai， Bi，Ci，Di表示工程在第i個月內(nèi)的完成部分，用弧表示某月完成某項工程的狀態(tài)，弧的流量為勞動力限制。合理安排每個月個工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求上圖從發(fā)點到收點的最大流問題。用Ford-Fulkerson標號法求得的一個最大流量方案如圖7所示，可知5月份有剩余勞動力20人，4項工程恰好按期完成。

3 結(jié)語

該文列舉、分析了網(wǎng)絡(luò)最大流問題在匹配問題、圖的邊連通度問題及資源分配問題領(lǐng)域的應(yīng)用并給出了對應(yīng)的解決方案。

參考文獻

[1] 張憲超，陳國良，萬穎.網(wǎng)絡(luò)最大流問題研究進展[J].計算機研究與進展，2003，40（9）：1281-1292.

[2] 《運籌學(xué)》教材編寫組，運籌學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

[3] 耿素云，屈婉玲.離散數(shù)學(xué)[M].北京：高等教育出版社，2004.

[4] GARY Chartrand，Ping Zhang.Introduction to Graph Theory[M].范益政等譯.北京：人民郵電出版社，2006.endprint