一條路線可以同時有最低承諾和最高容量。例如,運輸合約要求某條路線至少運送兩個單位,另一條路線卻最多只能承載三個單位。這些都是決策本身必須滿足的約束。把一條路線的成本調低,並不等於保證最低運量;把成本調高,也不等於禁止超出容量。
較早的允許路線準則,把每條可用路線視為足以承載全部貨物。本節保留有限容量,並加入運量下界。我們要解答的問題仍然很具體:所有節點的供需平衡及所有路線承諾,能否同時成立?答案不是給出一個可行流,就是找出一組節點,清楚說明它們的要求為何互相衝突。
動機
假設 到 的路線至少要運送三個單位。我們很容易想到:先放入這三個單位,把該路線的容量減三,再照原來的節點平衡去解剩下的問題。但預先放入的貨物,已令 多送出三個單位,也令 多收到三個單位。除非原定平衡剛好已被滿足,否則剩下的流必須補償這個改變。
所以,正確轉換要同時修改兩項數據:每條路線剩餘的容量,以及每個節點剩餘的平衡要求。完成這個轉換後,就能使用普通的最大流問題判斷可行性。最大流中的割,再翻譯回原問題,便成為關於上下界的精確不等式。
定義
設 是沒有自環的有限有向圖。容許平行弧及方向相反的弧,但每條弧都須有獨立標記。對每條弧 ,給定有限實數上下界 ;對每個節點 ,給定實數平衡 。本節採用流出量減流入量的慣例:
因此, 表示淨供應, 表示淨需求。把全部節點等式相加,每條弧的流量會一正一負地抵消,所以 是必要條件。以下假設這個等式成立。若所有 ,便稱為循環流;循環流不一定是零流。
定義 16.1.1
(邊界記號與剩餘問題)
對 ,以 表示離開 的弧,以 表示進入 的弧。兩端都在 內的弧,不屬於這兩個邊界。記 ;對弧集合的上下界或流量,也使用同樣的加總慣例。
令 、,並定義
則原問題等價於:在 下,使每個節點的淨流出量等於 。此外,。
這個等價關係可逐條等式驗證,而且兩個方向都成立:從可行 減去 ,會得到可行 ;從可行 加回 ,也會得到可行 。單獨把每條弧放到下界,不一定已經符合節點平衡。向量 正好記錄還欠下甚麼。
定理 / 命題
定理 16.1.2
(同時有流量上下界的可行性)
在上述有限圖、有限上下界及總平衡為零的假設下,存在可行 ,當且僅當每個 都滿足
等價地,每個 都滿足雙向邊界限制
若全部 都是整數,而且這些條件成立,則至少存在一個整數可行流。
條件 (1) 說的是:一組節點被要求的淨輸出,不能超過它最多能送出的數量,再減去無法避免的輸入。組內的運送不須計入,因為它只是把貨物從組內一處搬到另一處。對循環流而言,條件成為 :必須流入一組節點的數量,必須有能力再流出去。
把 (1) 用於補集 ,再利用 ,便得到 (2) 的左側不等式。所以,雙向形式有助理解,卻不需要另一套獨立的檢驗。
證明思路
證明
(以加總證明必要性,以輔助最大流證明充分性)
必要性。 把 內全部節點的平衡式相加。內部弧相互抵消,剩下
充分性。 先作下界代換,再加入兩個新節點 。原來每條弧保留,但容量改為 ,下界改為零。若 ,加入容量 的弧 ;若 ,加入容量 的弧 ;若 ,便毋須加入弧。令
流值為 的輔助流,必須把所有離開 及所有進入 的弧都飽和。由每個舊節點的流量守恆可知,原圖弧上的淨流出量正好是 。反過來,任何可行 都能透過把新增弧飽和,延伸成流值為 的輔助流。這些弧的方向不能弄反:仍需要正淨輸出的節點,先從 收到貨物,再經原圖送出去。
每個 – 割的源點一側,都能寫成 ,其中 。其容量為
另一方面,把 的定義在 內加總,得到
因此,(1) 恰好等價於 ,也就是 (3) 中每個割的容量都至少為 。
以下補上最大流步驟的存在性論證,讓實數容量的情況也有依據。輔助圖的可行流集合非空、閉且有界,故最大流值可以取得。在最大流的殘量圖中,不可能有 到 的路徑:否則可沿該有限路徑,以其最小正殘量容量增廣,使流值增加。設 是從 沿殘量弧能到達的節點集合。因為 ,所以 是一個割的源點側。每條離開 的輔助圖弧都已飽和,每條進入 的輔助圖弧流量都為零,否則便有殘量弧離開 。這也包括新增的源點弧及匯點弧。把 的守恆式相加,可知流值等於此割容量。割的下界使流值至少為 ,而 的總流出容量又只有 。故最大值恰為 ,加回 就得到所需的 。
若數據都是整數,輔助圖容量也全是非負整數。從零輔助流出發,沿殘量路徑增廣。每次正瓶頸都是整數,因此流量一直是整數,流值每次至少增加一。至多經過 次增廣,就會到達流值 ,或不再有增廣路徑。上面的殘量割論證說明,在條件 (1) 成立時,後一種情況的流值也必須是 。最後 是整數流。這個步數按容量單位計算,並不是關於二進制輸入長度的多項式界。對任意實數數據,緊緻性論證保證最大值存在,卻沒有聲稱任意增廣路徑規則都有限終止。
證明透視
同一個轉換內的三種不同責任
減去下界,是逐項可逆的代數轉換,還沒有用到流定理。接著的割容量計算,證明輔助圖的每種障礙都能翻譯回原圖。最大流的存在性,才把「沒有這類障礙」變成「存在可行解」。至於整數性,還須另外用整數瓶頸來證明,不能單憑實數數據的存在性結論推出。
若輔助最大流值是 ,其殘量割會給出一個 ,使
這就是有數值的不可行證書:該組節點要求的淨輸出,比容許的最大值多了這個數量。把某條路線的上界增加這麼多,只有在該路線離開此組時,才可能消除這一個障礙;其他割仍然必須滿足。直接展示一個修正後的可行流,比只移除某條失敗不等式更有說服力。
例題詳解
例題 16.1.3
(先保留承諾,再解剩餘平衡)
取節點 ,平衡為 ,弧數據如下:
| 弧 | 下界 | 上界 | 剩餘容量 |
|---|---|---|---|
| 2 | 4 | 2 | |
| 1 | 4 | 3 | |
| 0 | 2 | 2 | |
| 0 | 1 | 1 |
下界所代表的運送,其淨流出量為 。所以 ,並不是原來的平衡向量。此時 。加入容量各為一的 、,以及容量為二的 。沿 及 ,各送一個單位。
按表格次序,原圖剩餘流是 ,因此 。節點 的淨流出量是 ;節點 是 ;節點 是 。全部路線上下界都成立。即使 沒有收到任何剩餘流,必須運送的兩個單位仍已包含在 中。
在此 下, 的反向殘量容量是 ,不是二。取消任何正數流量,都會違反最低運量承諾。 的反向殘量容量則是 。
例題 16.1.4
(必須流入的數量可使循環流不可能存在)
只有兩條弧: 的上下界為 , 為 ;兩個節點都要求零平衡。每個區間本身都非空,但 至少收到三個單位,卻最多只能送出兩個。條件 (1) 要求 ,顯然不成立。
下界的淨流出量是 ,故 、。輔助圖有容量均為三的 和 ,但 到 最多只能通過兩個單位。源點側為 的割容量是二,式 (4) 給出的短缺量是一。若把 上界增至三,則 是可行循環流,直接證明這次修正確實成功。
例題 16.1.5
(運輸配額與完整的成本計算)
兩個起點的供應為 ,兩個目的地的需求為 。四條路線全部存在,下界、上界及單位成本分別是
減去 後,起點剩餘供應是 ,目的地剩餘需求也是 ;路線剩餘容量為 。剩餘運輸方案 滿足這些容量與平衡。加回 ,得到 。
為了進一步證明它也有最小成本,先解四條平衡等式。令 ,則每個平衡方案都可寫成
四條路線的上下界合起來,恰好給出 。成本為 ,所以在 取得最小值 。從剩餘問題看,預留的下界運送成本為 ,最優剩餘運送成本為 。漏掉常數八,雖不會改變使成本最小的決策,卻會把原問題的目標值報錯。可行性本身沒有證明最優成本;這裏的一參數計算才完成該項證明。
命題 16.1.6
(有容量限制的運輸準則)
設起點集合 、目的地集合 都有限,供應 及需求 非負,總量平衡 ,而每條允許路線有有限上下界 。在路線圖中把起點平衡設為 ,目的地平衡設為 。對包含起點集合 及目的地集合 的節點組套用 (1),得到精確可行性準則
證明
(讀出起點—目的地節點組的邊界)
路線圖的每個節點集合都可寫成 ,其中 、;而平衡總和為 ,所以可行性定理適用。 的平衡是 。每條路線都由起點通往目的地,因此一條路線離開 ,當且僅當它由 通往 ;進入 ,當且僅當它由 通往 。於是 的條件 (1) 是
移項即得 (5)。由於對所有 的 (5) 就是對所有 的 (1),它是充分必要條件。
例如, 是指定端點之間所有允許路線的上界總和;禁用路線不出現在圖內,也可等價地把其上下界都設為零。此式保留組內目的地的需求,以及跨越邊界的路線容量。只知道鄰接集合,已經不足以表達這些資訊。
概念視角組合
從鄰接障礙走向容量障礙
若所有下界都是零,而且每條允許路線的容量都是總供應 ,在 (5) 中選 ,則沒有路線從 通往 ,便重新得到 。任何 只會給出更弱的不等式,因為 。至於其他 ,至少有一條允許路線從 跨到 ;該路線的容量 就令 (5) 自動成立,因為 且 。因此,較早的鄰接準則確實是本節結果的特例。有限路線容量及不可避免的流入,正是較簡單公式所省略的資訊。
常見錯誤
反例模式
全部鄰接檢驗通過,仍可被容量阻擋
供應與需求都是 ,四條路線全部允許,下界全部為零。通往目的地一的每條路線容量為 ;通往目的地二的每條路線容量為二。每個非空起點組都同時鄰接兩個目的地,所以全部不計容量的鄰接不等式都成立。但是,目的地一合共最多只收到一個單位,少於需求二。
在 (5) 中取 、,就會要求 。從圖的準則看,這一組節點需要淨輸出二,向外容量卻只有一。障礙來自容量,不是缺少路線。
常見錯誤
(取消必須運量的殘量弧)
有下界的殘量圖中,正向容量為 ,反向容量為 。反向弧只能取消高於最低承諾的流量。方向相反的原有弧,仍須保留各自標記;反向殘量弧並不代表可以改寫另一條原有弧的流量。
常見錯誤
(過度解讀整數性與證書結論)
整數數據保證存在整數可行流,但也可以同時存在分數可行流。另外,數值算法留下很小的平衡誤差,也不是精確的不可行證書。必須有一個割,且其算術確實違反 (1)。若模型使用無窮上界,就須另行證明可用哪個有限上界代替,或採用其他存在性論證;本節的緊緻性證明明確依賴有限上下界。
小結
先減去路線下界,再從原定節點平衡減去這些下界的淨流出量。接著透過把輔助源點弧飽和,解零下界的剩餘問題。每次無法完全飽和,都有割證書 。對整數數據,整數增廣給出一個整數可行代表。這些都是可行性結論;若還有成本目標,仍須另行證明最優性。
練習
快速檢查
(兩條弧 、 的上下界分別為 、,要求平衡為 。求 ,用一個參數描述全部可行流,並在 時計算每條弧的正向及反向殘量容量。)
解答 · 答案
下界的淨流出量為 ,剛好等於要求,所以 ,輔助問題毋須任何源點或匯點弧。令 ,則平衡要求 ,兩條弧的上下界合起來恰為 。在 下, 的正向、反向殘量容量分別為 、; 的相應容量為 、。
快速檢查
(在第一個例題的三節點網絡中,有人減去路線下界後,仍保留原平衡 。說明:若解出這個錯誤剩餘問題的可行流,再加回下界,為何不符合原定平衡?寫出正確的輔助弧,並展示使其飽和的流。)
解答 · 答案
下界的淨流出量為 。把它加到錯誤的剩餘平衡,就得到 ,而不是 。正確剩餘平衡為 。加入容量為一的 、,以及容量為二的 。沿 和 各送一個單位,就能飽和新增弧,恢復原流量 。
快速檢查
(零平衡網絡只有三條弧: 的上下界為 , 為 , 為 。給出一條失敗的割不等式,計算輔助最大流值,再只修改 的上界,以盡可能小的改動使問題可行。)
解答 · 答案
取 ,(1) 右側為 ,小於 。下界淨流出量是 ,所以 、。輔助圖中全部 – 路徑都要通過剩餘容量為二的 。沿 運送兩個單位,便達到這個上界,故最大流值為二。失敗的割要求把 的上界至少增至三;增至三也已足夠,因為原圖循環流 滿足全部上下界。因此,最小增加量是一。
快速檢查
(在運輸成本例題中,只把路線 的下界從一增至二。求全部可行方案及最小成本。解釋為何只改變該路線成本、以鼓勵運送的做法,不是等價模型。)
解答 · 答案
全部平衡方案仍是 。新配額要求 ,原有上界要求 ,所以只有方案 ,成本為 。有限的有利成本可以鼓勵使用某條路線,卻沒有把 的可行方案從可行集合中剔除。改變目標與加入約束,是兩種不同操作。
快速檢查
(兩條有獨立標記的平行弧都從 通往 ,上下界均為 ,平衡為 。各舉一個整數及分數可行流。定理究竟保證哪種整數性?若第二條弧的下界變成 ,能否套用整數數據結論?這個特定算例又是否仍有整數可行流?)
解答 · 答案
弧流量向量 與 分別是整數及分數可行流。定理保證存在整數代表,並非每個可行點都是整數。第二下界改為 後,數據不再全是整數,不能使用該充分假設。但是, 在這個例子中仍是整數可行流。充分條件不成立,並不能反過來證明結論不成立。