任孝忠，韓震華

(四川省工業(yè)貿(mào)易學(xué)校 公共課教研室，成都 610081)

1 引例［1－2］

某地區(qū)的河流從一源點開始向外流出，在某些城市上分成若干份，成樹形分布，共有m個支流，每一支流河流分別受到不同程度的污染w［i］。若現(xiàn)有n個治理方案，每個方案均需要沿河流的連續(xù)城市共同處理，每個方案有一個最大執(zhí)行力度上限l［i］，每單位執(zhí)行力度需要消耗 c［i］的財力，并可取得一單位的污染治理成果。設(shè)計一種安排方案使得在治理完所有污染的前提下的總計財力花銷最小。

例:在圖1中，城市1到城市2的支流需3單位執(zhí)行力度的治理，城市1到城市3的支流需1單位執(zhí)行力度的治理，城市3到城市4的支流需2單位執(zhí)行力度的治理;從城市1到城市2的治理方案有執(zhí)行力度上限4，單位執(zhí)行力度消耗1單位的代價;從城市1到城市4的治理方案有執(zhí)行力度上限2，單位執(zhí)行力度消耗2單位的代價。

圖1 有向圖

2 問題分析［3－4］

設(shè)列向量x，其中x［i］表示第i個治理方案的執(zhí)行力度;設(shè)矩陣A，A［i］［J］表示第一個支流是否被第j個治理方案包括。將c行向量化，l和w列向量化。則本問題可以表述為以下線性規(guī)劃問題:

因此對于圖1有:

對于這樣的問題，傳統(tǒng)方法是使用線性規(guī)劃來解決，然后由于線性規(guī)劃的算法效率較低，往往在實際應(yīng)用中受到諸多限制。

3 算法優(yōu)化

3.1 (點邊)關(guān)系矩陣［5］

此時，關(guān)系矩陣具有以下性質(zhì):每一列有且僅有一個1與 －1(適合有向圖)。

對于本問題，矩陣A不能視作一個圖的關(guān)系矩陣，因此，需要做對應(yīng)的矩陣變換。

3.2 矩陣變換

首先，考慮將不等式Ax≥w的不等號去除掉。

對矩陣和向量進行以下設(shè)定:

其中，向量y為上界差值，通過這些設(shè)定使得A'成為(m+1)×(n+m)規(guī)格的矩陣。

可以注意到新增的列與矩陣A中原始的行存在一一對應(yīng)關(guān)系。于是可寫成等式A'×x'=w'。

這樣，我們通過引入上界差值y，將不等號表述為等號。

根據(jù)圖1，設(shè)矩陣A'及向量c'，w'，l'具有以下數(shù)值:

當約束條件變?yōu)锳×x＜w時，只需將A'中的－i變成i即可。

繼續(xù)做行變換，得到A″和w″滿足以下條件:

我們可以嘗試從圖論角度理解該問題。該變換的實質(zhì)即為，對每一條支流所對應(yīng)的行與其下游支流所對應(yīng)的行相減。新增的行則可以抽象為所有從源點出發(fā)的支流的起源支流。這時我們分別考慮兩種列，一為原始矩陣A存在的列，二為新增的列。

對于原始存在的額列，即某一治理方案，其最下游的支流所對應(yīng)的行為1，最上游的支流所對應(yīng)的行為－1，其余支流均為0。

對于新增的列，其對應(yīng)的行為1，對應(yīng)行的上游支流所對應(yīng)的行為0，其余行為0。故A″矩陣中的每一列有且僅有1個1和－1。

這樣，由關(guān)系矩陣的特性可知，A″可以視作某個圖的點邊關(guān)系矩陣，至此，我們可以通過建立最小費用流模型來解決此問題。此時，圖1中的矩陣A和向量w經(jīng)過轉(zhuǎn)換后得到如下所示的A'和w'。

3.3 最小費用流

針對以上問題分析驗證可發(fā)現(xiàn)，最小費用流能夠解決的問題可以用以下形式表示:

其中，A為關(guān)系矩陣;c為邊的單位流量費用向量;x為邊的流量列向量;w為點的平衡條件;1為邊的流量上界列向量。顯然，經(jīng)過轉(zhuǎn)換的矩陣滿足上訴條件，顯而易見，可以使用最小費用流方法來解決。

最小費用流的常見解決辦法主要有消負圈［6］和連續(xù)最小費用增廣路，其復(fù)雜度上界均為O(max f×n×m)，因此，并不是嚴格的多項式算法。而在以往的研究中，確實存在一些嚴格多項式算法復(fù)雜度的最小費用流方法［7］。

但是，正如同在線性規(guī)劃問題中，最普通的單純形法的效率往往比嚴格多項式算法更高，對同一個問題用最小費用流的求解速度遠遠快于用線性規(guī)劃的速度。

這樣，我們就得到了一個很好地在類多項式時間內(nèi)解決該問題的算法了，那么，什么樣的問題可以用該算法來解決呢?

4 結(jié)論

從線性規(guī)劃的角度講，如果約束矩陣的每一列是由若干連續(xù)的1組成的，那么該問題即可以解決。我們令矩陣A″滿足下列條件即可:

顯然，這時矩陣A″每一列僅有一個1和－1。

從問題的原始描述角度上講，如果問題是對某一連續(xù)區(qū)間產(chǎn)生的影響，那么該問題統(tǒng)一可以用此方法解決?？闪罹仃嘇″滿足:

即可將原問題轉(zhuǎn)化為可使用最小費用最大流解決的問題形式。

5 結(jié)束語

采用傳統(tǒng)的線性規(guī)劃解法和最小費用流算法對圖1所示的問題進行編程實驗驗證，兩種算法皆采用C語言編寫實現(xiàn)。對于線性規(guī)劃解法，采用了運行速度較快的單純形法［8］，得到了如下結(jié)果:

而采用最小費用流算法得到了如下結(jié)果:

通過驗證發(fā)現(xiàn)，采用最小費用流算法的效率提升了47倍，如果把讀入時間考慮進去，實際的效率提升會更大!該算法的重要性和意義也不言而喻?？梢灶A(yù)見，該算法在實際應(yīng)用中還有很多值得推廣和進一步研究的空間。

［1］Ravindra K Ahuja，Thomas L Magnanti，James B Orlin.Network flow:theory，algorithms，and applications［M］.Beijing:China Machine Press，2005:602－604.

［2］李凱鎮(zhèn) .River Problem［EB/OL］.［2013－04－21］.http://acm.hdu.edu.cn/showproblem.php?pid=3947.

［3］劉汝佳，黃亮.算法藝術(shù)與信息學(xué)競賽［M］.北京:清華大學(xué)出版社，2004:319－320.

［4］劉汝佳.算法競賽入門經(jīng)典［M］.北京:清華大學(xué)出版社，2009:211－212.

［5］Douglas B.West introduction to graph theory［M］.Beijing:China Machine Press，2006:367－368.

［6］Andrew V Goldberg，Robert E Tarjan.Finding minimumcost circulations by canceling negative cycles［J］.Journal of the ACM(JACM)，1989，36(4):873－886.

［7］James B Orlin.A faster stronglypolynomial minimum cost flow algorithm ［J］.Operations Research March/April，1993，41(2):338－350.

［8］James P Ignizio，Tom M Cavalier.Linear programming［M］.USA:Prentice－Hall，1994.