強制運量改變了哪些決定可以撤銷。若路線現有五單位流量,但合約要求最少三單位,反向殘量路線只能撤銷兩單位。本節連接下界可行性轉換與固定平衡網絡中的成本改良環,推導最優性判準及可獨立核對的數值下界。
模型與剩餘操作
設 是有限有向圖,沒有自環,允許分別標記的平行及反向弧。每條弧 有有限實成本 及界限 。可行流 滿足各弧界限,並在每個節點有指定的流出減流入 。假設至少有一個可行流,因此 。成本是 。
定義 18.1.1
(具有強制運量的殘量網絡)
每條原弧 的兩個剩餘方向均保留其標籤:正向 的容量為 、成本為 ;反向 的容量為 、成本為 。只保留容量嚴格為正的殘量弧。勢函數 給原弧的約化成本為 。
沿正容量殘量環增廣 時,正向弧上的原流量增加,反向弧上的減少。只要 不超過瓶頸容量,所有界限都保持成立;每個節點增加的剩餘流入與流出相等,因此平衡不變。總成本改變等於 乘以殘量環成本之和,反向成本必須帶負號。若簡單環同時使用同一原弧的兩個方向,兩者互相抵銷,該環不可能是負成本環。
最優性與可核對的下界
定理 18.1.2
(有界流的最優性與價格)
對可行流 ,以下三者等價:
- 在所有可行流中成本最低。
- 其正容量殘量網絡沒有負成本有向環。
- 存在勢函數 ,使每條正容量殘量弧的約化成本非負。等價地,對每條原弧,
- 蘊含 ;
- 蘊含 。
不論 是否最優,任何勢函數都給每個可行流以下成本下界:
若某可行流達到 ,它便是最優流。
概念視角結構
下界即放鬆平衡方程所得
設 為頂點—弧矩陣,使 是 處的流出減流入。由於 ,下界可寫成
平衡方程以乘數 移入目標函數,只剩下逐弧分離的上下界約束。每個可行的 都使附加項為零,這就再次得到下界。定理進一步說明,最佳的乘數能消除差距:存在 使 等於最小成本。
證明
(環分解、最短路價格與弱對偶恆等式)
若存在負殘量環,沿該環增廣正的瓶頸量便得到成本更低的可行流,故最優流不可能有負環。反過來,對任意另一可行流 ,若 ,把差額放在正向殘量弧;若差額為負,則把 放在反向殘量弧。界限保證所需殘量容量足夠。兩流平衡相同,故得到非負殘量循環流。沿正流量的弧走至節點重複,取出有向環並減去環上最小流量;平衡維持,而至少一條正流量弧消失。重複此過程可在有限步內分解成非負權重的有向環。成本差 是各環成本的加權和;若沒有負環,差額便非負。
若所有剩餘約化成本非負,則勢函數差在環上相消,每個環成本都非負。反之,若沒有負環,加入一個以零成本弧連至所有節點的臨時源點,令 為其最短路距離。任何重複環均可移除而不增加路徑成本,所以只需考慮有限條簡單路,距離有限。距離不等式 使每條殘量弧約化成本非負。反向弧的約化成本是 ,由此得到兩條原弧符號條件。固定弧沒有剩餘方向,不受符號限制。
最後,對任何可行 ,由平衡方程得
每個 均不小於它在 上的最小值,故得到下界。若可行 達到此下界,便沒有更便宜的可行流。特別是上述符號條件令每個 都使 在其區間內最小,因此最優價格能使等號成立。
證明透視
上下界各自的作用
下界只在證明的一處進入:把 寫成剩餘分配。減少量 放在反向弧上,而因 ,它不超過反向容量 ;同理,增加量不超過 。正因如此,殘量網絡必須使用 而非 。由「沒有負環」推到價格只需要有限性:路徑可縮短為簡單路,所以最短距離存在。最後的恆等式需要兩流平衡相同,區間最小值便讀出符號條件:正約化成本偏好下端點,負約化成本偏好上端點;內部流量同時有兩個剩餘方向,迫使約化成本為零;固定弧則不受限制。遺漏勢函數項會改變下界的數值,剩下的和一般不是有效下界。
例子
例題 18.1.3
(合約阻止看似可行的撤銷)
弧為 、、,上界均為 ,下界依次為 ,成本依次為 。令 、、。守恆迫使流量為 ,界限給出 。成本為 ,故 最優,成本為 。
不枚舉 也可驗證:取 ,原弧約化成本為 。因此
常見錯誤
(撤銷至合約下限以下)
在 ,第一條路線恰好處於下界,其反向殘量容量為 。若錯誤地用 作反向容量,便會虛構成本為 的負殘量環 。沿此環增廣會令 低於合約下限,故並非合法操作。
例題 18.1.4
(增廣至另一端點)
保持網絡和界限,但將成本改為 。在 ,殘量環 的成本為 ,瓶頸為 :其中 的反向容量為 。增廣一次得到 ,成本由 降至 。取 ,約化成本為 ,而 ,故新流最優。 的正約化成本與其流量處於零下界相容;並非所有原弧的約化成本都要為零。
反例模式
只檢查一個方向並不足夠
在第二個例子中,於 取 ,所有原弧成本都是正數,但反向殘量弧成本為負。只測試原弧正向會錯判為最優;上面的負環明確給出更便宜的可行流。
第三個例子專門處理一條弧完全沒有剩餘方向的邊界情況。
例題 18.1.5
(固定弧的約化成本可為任意符號)
取弧 ,、成本 ;以及 、,界限 、成本 。令 、、。 的守恆給出 , 的守恆給出 ,所以 是唯一可行流,成本為 。
與 的流量都在區間內部,故證書要求 。取 ,便迫使 ,再得 ;固定弧的約化成本是 。於是
即使正約化成本出現在上界,證書仍然準確。若第一條弧的界限改為 ,同一符號便違反條件 ;事實上,此時把三單位全部改經 運送,成本只有 。
算法與限制
消環法由可行流開始,在整個殘量網絡搜尋負環,增廣至瓶頸後重複。若界限、平衡及起始流均為整數,每次瓶頸及隨後流量均為整數。有限容量只容許有限多個整數可行流,而每次負環增廣都嚴格降低成本,即使成本為實數亦然。因此此整數起始版本終止,定理證明終點最優。整數數據若通過下界可行性測試,便存在整數可行起點。這個有限狀態證明沒有給出多項式時間界,也沒有證明任意實數起點必定有限步終止。
所有節點的勢函數同加一個常數,不會改變約化成本或 ,因為總平衡為零。價格證書須涵蓋每個剩餘連通部分,而非只涵蓋某供應節點可到達之處。實際數值運算須另行處理捨入;此處使用精確的嚴格符號及等式。
習題與解答
快速檢查
(在第一個例子取 。求成本,並計算沿 增廣至瓶頸時的成本變化。)
解答 · 答案
流量為 ,成本為 。環成本為 ;瓶頸為 ,因為 的反向容量為 。成本下降 至 。
快速檢查
(若 、、,哪個端點使 最小?若這個勢函數為某可行流提供最優性證書,該流在此弧上必須如何?)
解答 · 答案
最小值 在 達到。證書取等要求 ;等價地,在此證書下,負約化成本不容許正的正向殘量容量。
快速檢查
(一條弧有 及 。最優證書是否要求其約化成本為零?它對區間最小值的貢獻是多少?)
解答 · 答案
不需要。兩個方向都沒有正殘量容量。區間只有 ,最小值為 。
快速檢查
(在第二個例子中把 換為 。重算 並解釋為何不變。)
解答 · 答案
約化成本仍為 。平衡項是 ,區間項總和為零,所以 。所有勢同加常數時, 的變化是該常數乘以 。