從供應和需求到方案
單獨看最便宜的路線,未必能得到整體最便宜的運輸方案:該路線會消耗可用於其他地方的供應與需求,我們必須一起決定所有運量。本節研究有限的平衡運輸模型。
定義 2.3.1
(平衡運輸問題)
設有 個供應點和 個目的地,供應量 、需求量 ,每一對供應點與目的地之間都有有限單位成本 。若 ,稱模型為平衡。方案是矩陣 ,滿足 、行和 及列和 ;其總成本為 。
這些是等式要求,而非上界;剩餘供應或未滿足需求需要另行建模。供應或需求可以為零。成本可為負;固定的有限總運量使本模型不會因此向下無界。
命題 2.3.2
(平衡且路線完整的模型必可行)
若模型平衡,且每一對供應點與目的地均可運輸,則存在方案。
證明
(反覆運送較小剩餘量直至全部用完)
記剩餘供應 及剩餘需求 ,初值為 和 。只要某個 ,剩餘總量相等,便有某個 。由 向 運送 ,並從兩個剩餘量中減去;其中至少一個變為零。每一步都減少正剩餘量的個數,所以最多 步便停止。此時每個 ,由平衡知每個 。運量非負,並具有所需的行和與列和。
證明無論選中哪一對 都用到該路線,完整性正是在這裏起作用。
反例模式
單靠平衡不能保證可行
有禁運路線時,平衡不保證存在方案。取供應 、需求 ,只容許路線 和 。模型平衡,但目的地 的列和是 ,因為兩個變量都不存在。有禁運路線或容量限制時,必須另行檢查可行性。
價格提供下界
對供應點和目的地分別指定實數 ,使每條路線滿足 。這樣的 稱為可行價格。
定理 2.3.3
(價格下界與緊路線最優性)
設 是方案, 對所有 滿足 。則
若再有 只出現在緊路線,即 的路線上,則等號成立,而 是最低成本方案。
證明
(以方案運量為權把價格不等式相加)
把每個不等式 乘以非負的 再求和,得 。行和把第一項化為 ,列和把第二項化為 。差額是
是一串非負項之和。若所有已用路線都緊,每項均為零,所以 的成本等於下界。其他方案的成本都不低於同一下界,故 最優。
供需是等式約束,因此價格的正負不受限制。此證書是充分條件;論證不必假設有算法能為每個輸入找到價格。
證明透視
把可行性和證書分開
假設在哪裏用上: 非負,令每個價格不等式乘上去後方向不變;行和與列和的等式把加權價格和化為下界。方案只在這兩處起作用,這也是價格可取任何符號的原因: 或 的不等式從未被乘以負數。
關鍵一步:差額是「運量乘以鬆弛量」之和。嚴格鬆弛的路線若有正運量,差額便為正;所有已用路線都緊,差額便為零。
缺了甚麼會出錯:路線緊不能補救不正確的行和或列和。用下面例子的價格,只有 、 而其餘為零的矩陣只用緊路線,成本 ,低於下界 ;它不符合第一行及第三列的和,所以證明中的等式一步不適用。
如何收結:定理證明的是某一方案的最優性,並不聲稱每個最優方案都有緊價格。這個逆命題屬於對偶定理,本節不予證明。
常見錯誤
(只檢查已用的路線)
若所有已用路線都緊,證明中的恆等式會自動令成本等於下界,不論未用路線如何。所以在檢查每條未用路線的不等式之前,這個等式甚麼也證明不了。在下面的例子中,、 在三條已用路線上都緊,數值亦為 ,但 及 ,所以它們不是可行價格,不能作證書。
完整例子
例題 2.3.4
(同值的方案與價格)
供應為 ,需求為 ,成本矩陣和方案為
行和為 ,列和為 ,方案成本是 。取 、,則各 排成 ,逐項不大於 。價格下界為 ,等於方案成本,故方案最優。負的供應點價格是允許的,並不表示運量為負。
常見錯誤
(因價格為負而否定證書)
供需約束是等式,所以其價格可取任何符號。上面的 完全合法。要求 是 這類不等式約束的規則,屬於另一個模型。
概念視角結構
價格並非唯一
對任意實數 ,把每個 加 、每個 減 ,路線上的和不變。由平衡條件,下界的變化 等於零。因此同一證書有無數種表示;沒有選定正規化時,單個價格沒有獨立意義。
第一個例子的價格是給定的。它們可以由方案算出,而退化方案需要多一步。
例題 2.3.5
(由退化方案計算價格)
沿用同一數據。每條緊路線給出一條方程 ;五個未知數除上文所說的平移外由這些方程確定,所以設 後需要 條緊路線。方案只用了三條:、、。它們給出 和 ,但 沒有把第二行與其餘部分連起來。
指定一條未用路線以零運量取緊,例如 :則 、,正是第一個例子的價格。其餘兩條路線的鬆弛量是 及 ,均非負,所以價格可行。
改選 ,則 、。此時 的鬆弛量是 , 的是 ,同樣可行,下界為 。退化方案可以有真正不同的證書,而不只是平移;每個選擇都要在全部六條路線上檢查。
平衡且路線完整的模型以外
供應超過需求時,可以加入虛擬目的地,其需求為剩餘量,成本表示所指定的剩餘供應處理成本。這是建模選擇,並非自動假設浪費免費。短缺亦可在明確指定其含義與成本後,用虛擬供應點表示。若某些路線禁運,移去其變量及不等式,並另行檢查可行性。路線容量會加入額外約束,對偶證書也要相應修改。
例題 2.3.6
(以虛擬目的地處理剩餘供應)
把供應改為 ,需求仍是 ,並假設剩餘供應可零成本棄置。加入需求為 的第四個目的地,成本 。把方案延伸為 ,即在 後加一列 ;行和為 ,成本仍是 。
已用路線的緊方程給出 、、、 及 。未用路線的不等式 和 要求 。取 ,則 。八條不等式全部成立:兩行的和都是 ,對應成本分別為 和 。下界是 ,故方案最優。零成本棄置路線迫使 :供應點 多出的一單位既可免費棄置,其價值便不能為負。
練習
快速檢查
(驗證方案的行和、列和,並獨立計算成本。)
解答 · 答案
行和為 ,列和為 ;成本為 。
快速檢查
(檢查六個價格不等式並計算下界。)
解答 · 答案
六個價格和為 ,分別不大於成本 ;下界為 。
快速檢查
(只把 由 改為 ,原價格仍可行嗎?僅靠這一點能否判斷原方案是否最優?)
解答 · 答案
不可行:。此證書失效本身不能證明方案最優或不最優。事實上原方案仍最優:可行價格 、 證明其新成本 。
快速檢查
(取 平移價格,計算新價格和下界,解釋下界為何不變。)
解答 · 答案
新價格為 、,下界為 ;平衡使平移項相消。