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

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

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

中圖分類(lèi)號(hào)：F224 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）05（c）-0043-02

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

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

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

（1）

則稱(chēng)f為可行流。

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

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

（2）

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

2.1 求最大匹配問(wèn)題

2.2 求圖的邊連通度問(wèn)題

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

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

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

2.3 資源分配問(wèn)題

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

中圖分類(lèi)號(hào)：F224 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）05（c）-0043-02

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

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

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

（1）

則稱(chēng)f為可行流。

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

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

（2）

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

2.1 求最大匹配問(wèn)題

2.2 求圖的邊連通度問(wèn)題

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

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

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

2.3 資源分配問(wèn)題

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

中圖分類(lèi)號(hào)：F224 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）05（c）-0043-02

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

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

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

（1）

則稱(chēng)f為可行流。

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

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

（2）

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

2.1 求最大匹配問(wèn)題

2.2 求圖的邊連通度問(wèn)題

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

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

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

2.3 資源分配問(wèn)題

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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