當某些路線禁止使用時,總供應等於總需求並不保證運輸計劃存在。即使整體貨物足夠,一組工廠可以到達的客戶也可能無法接收這組工廠的全部供應。在最小化運費或構造運輸基之前,我們先要知道允許的路線能否實現供需平衡。
子集判準
定義 14.1.1
(允許路線計劃與鄰域)
設 分別為有限的出發地及目的地集合,供應量 、需求量 均為非負實數,允許路線集合為 。可行計劃是在 上給出非負運量 ,並滿足
對 , 的鄰域是 ,即 可到達的目的地集合;空集沒有鄰點。
禁運路線根本沒有變量。假設 。可行性的必要條件是
因為 的所有供應都必須送往 ,其目的地的總需求便限制了可接收量。這些不等式其實也足以保證可行。
定理 14.1.2
(允許路線的可行性判準)
對有限的 ,若供應和需求非負且總量同為 ,則存在只使用 的可行計劃,當且僅當每個 均滿足 。
證明
(流網絡、割與殘量割)
必要性可由 內的行平衡式求和得出:送入 的運量不超過該集合的列需求總和。證明充分性時,構造有向網絡:源點 到出發地 的弧容量為 ;每條允許路線 的容量為 ;目的地 到匯點 的弧容量為 。值為 的流會飽和所有源點及匯點的弧,故其路線流量就是可行計劃;反過來,可行計劃亦給出值為 的流。路線容量取 已足夠,因為任何路線都不需要運送超過總供應。
現在證明每個 – 割的容量至少為 ;割容量只計算從源點側指向匯點側的原弧。設割的源點側包含出發地 及目的地 ,其容量為
若至少一條允許路線跨越割,最後一項已至少是 。否則 ,由假設得 ,故前兩項之和已至少為 。
為甚麼割的下界保證存在值為 的流?最大流存在:有限維弧流向量處於閉且有界的集合,而流值連續。若最大流的殘量網絡有 – 路徑,就可沿正向殘量弧增加流量、沿反向殘量弧減少流量,步長取路徑上的最小殘量容量,從而增大流值,矛盾。令 為殘量網絡中從 可到達的頂點,則 ;所有離開 的原弧均飽和,所有進入 的原弧均為零流量。在 上對流量守恆式求和,得到流值等於此割容量。由割下界知流值至少為 ,源點弧的容量又給出上界 ,所以流值等於 ,可行計劃存在。
證明分兩半:每個割的容量下界,以及一個容量等於流值的割。子集不等式在前一半使用。
證明透視
子集條件究竟控制甚麼?
關鍵一步是每條路線弧都取容量 。這個容量大到從不限制可行計劃,但任何讓允許路線由源點側跨到匯點側的割,容量已至少為 。這類割因此無害,需要檢查的只有 的割。此時容量為 ,最小的選擇是 ;這正是不等式要對一組出發地 連同其全部鄰點一起檢查、而非逐個出發地檢查的原因。
各假設在不同位置使用。共同總量 使值為 的流同時飽和源點弧與匯點弧,於是行方程與列方程都成立。有限性使弧流向量組成閉且有界的集合,最大流因而存在。收尾一步用到反向殘量弧:可到達集 之所以是容量等於流值的割,是因為每條進入 的弧都是零流量;若有正流量的弧進入 ,它會給出一條離開 的反向殘量弧,其起點便也可到達。若總量為零,所有供應和需求均為零,即使沒有允許路線,零計劃也可行。
例題 14.1.3
(群組瓶頸與修補)
設供應為 、需求為 ;出發地 只能運往目的地 ,出發地 能運往 。總量都是 ,每個出發地和目的地都有路線,每個出發地單獨的鄰接需求也足夠。然而 的供應為 ,而 的需求只有 。不等式不成立,故沒有可行計劃。在流網絡中,源點側取 ( 表示網絡中目的地 的頂點),所得割容量為 :其中 來自 至出發地 ,另有 來自兩個目的地至 。
若開放路線 ,以下計劃滿足所有平衡式:
其行和為 ,列和為 。新路線消除了上述特定障礙;真正證明可行的是列出的計劃,而非單憑開放路線。
用殘量路徑修正早前選擇
例題 14.1.4
(殘量路徑撤銷貪心運量)
設供應與需求均為 ,路線為 。若先在 運送兩單位,出發地 唯一的路線通往已滿的目的地 ,因此不能只靠正向路線增廣。殘量路徑 的瓶頸為 :中間的反向弧撤銷 的早前運量。增廣後得到 、、。行和為 、列和為 ,且只用允許路線,所以這是可行計劃。
整數計劃
增廣路徑論證亦控制所得計劃的算術性質。
推論 14.1.5
(整數數據給出整數計劃)
若所有供應與需求都是整數,且子集判準成立,則存在只使用 、所有運量均為整數的可行計劃。
證明
(以整數單位增廣)
若供應與需求均為整數,所有容量都是整數。從零流開始,每次的殘量容量和正瓶頸都是整數,因此增廣保持整數性,並使流值至少增加一。流值不超過 ,所以至多 次增廣後便再沒有增廣路徑。當判準成立時,上述殘量割論證給出流值 ,所得可行計劃便是整數計劃。
這是存在性陳述,並非說每個可行計劃都是整數。成本與可行性判準無關;求得計劃後,最小成本仍需另外的最優性論證。
例題 14.1.6
(檢查每個子集,包括沒有路線的出發地)
設供應為 、需求為 ,路線為 、,而出發地 完全沒有允許路線。總量為 。各非空子集給出
七個不等式全部成立,所以計劃存在;數據是整數,因此亦存在整數計劃。出發地 必須經 運出一單位;目的地 還欠一單位,只能來自出發地 ,出發地 餘下的一單位則運往目的地 :
行和為 ,列和為 。邊界情形是出發地 :沒有路線的出發地恰在供應為零時無害,而單元素不等式 正記錄了這一點。
常見錯誤
最誘人的捷徑是每次只檢查一個出發地。
反例模式
只檢查單一出發地並不足夠
聲稱:若總量平衡、每個頂點都有允許路線,而且每個單一出發地都滿足 ,則可行計劃存在。設供應 、需求 ,路線為 、、。每個出發地和目的地都有路線,單一出發地不等式為 、、。然而出發地 與 各只有一條路線,故 、 是被迫的,目的地 至少收到 單位,需求卻只有 。沒有可行計劃。子集 偵測到這一點:。修正後的陳述就是判準本身:檢查出發地的每個子集。
常見錯誤
(以高成本代替禁運路線)
禁運路線沒有變量。給它一個很高但有限的成本,仍容許貨物經過,因此含這種路線的成本模型可能給出不被允許的計劃。相對於 的可行性,應在任何成本進場之前判定。
常見錯誤
(把貪心死路當作不可行)
正向增廣停頓時,目前的計劃可能只是早前選擇欠佳,正如殘量路徑例子所示。貪心法遇到死路不能證明不可行;只有容量小於 的有效割或違反的子集不等式才是證書。
練習
快速檢查
(供應為 ,需求為 ,路線為 、、。找出違反的子集不等式或一個可行計劃。)
解答 · 答案
的供應為 ,鄰接需求為 ,故不可行。所有單一出發地的不等式都成立,因此群組測試很有用。
快速檢查
(供應和需求均為 ,只允許對角線路線。 是否可行?給出允許的計劃或不可行證書。)
解答 · 答案
不可行:這兩個運量使用了禁運路線。對角計劃 可行。
快速檢查
(供應為 ,需求為 ,路線為 、。找出容量低於總供應的割,並指出目的地 至少需要增加多少需求,才能消除該特定不等式的違反。)
解答 · 答案
對 ,。將 、出發地 、目的地 放在源點側,割容量為 。將該鄰點的需求至少增加 ,可消除這個不等式的違反;但改變需求也會改變總平衡,必須適當調整模型後才能判斷可行性。