運輸表中第 行是產地 的供給,第 列是目的地 的需求。這裏假設所有路線均可用,供給與需求非負且總量相等,單位費用為有限實數。樹是記錄基本變量的工具;樹邊上的運量可以為零,這正是處理退化所必需的。
平衡方程與樹
令 為由產地 運往目的地 的運量,限制為
行方程總和等於列方程總和;因為總供給等於總需求,任意一條方程可由其餘方程推出。把產地與目的地看作完全二部圖的兩類頂點,每個格 對應一條邊。 個產地和 個目的地組成的生成樹有 條邊。
定義 23.1.1
(運輸樹及其基本解)
運輸樹是一組格,其邊構成 個產地與 個目的地上完全二部圖的生成樹:連通、無環、到達每個產地與目的地,並有 個格。這些格稱為基格。對應的基本解把所有非基格設為零,再在樹格上解平衡方程。若所有運量非負,它就是基本可行解。
下述定理說明樹格對應的列線性無關,因此平衡方程的秩恰為 。部分基本運量可以為零,所以單靠數正運量並不能辨認一個基。
定理 23.1.2
(樹唯一決定基本運量)
供需平衡時,任意連接全部產地與目的地的生成樹,都唯一決定一個僅在樹邊上可能非零、滿足平衡方程的實數運量表。它可行當且僅當這些運量均非負。
證明
(逐一剝去葉頂點)
給每個頂點一個剩餘餘額,初始值為其供給或需求。多於一個頂點的有限樹必有葉,葉的唯一鄰邊運量必須等於其當前剩餘餘額。刪去葉及其邊,並從相鄰頂點的剩餘餘額減去這個運量。剩餘供給與需求的總和仍相等。重複此步驟,所有邊的數值被唯一決定,最後頂點的餘額為零。每個刪去的頂點按構造滿足原方程,最後頂點也因餘額為零而滿足方程。因此實數解存在且唯一;它恰在所有運量非負時可行。
剝葉的每一步都是被迫的,這給出唯一性;存在性還需要對最後一個頂點多作一點觀察。
證明透視
平衡條件與樹形在哪裏用到
剝葉一步只用到:葉的方程只含一個未知數,所以該未知數被迫決定。無環保證葉總是存在,刪去後仍是一棵較小的樹,程序可一直進行到只剩一個頂點。生成性不可少:不在樹上的頂點沒有任何邊,除非其供給或需求為零,否則它的方程不能成立。
平衡假設只在最後用一次。不變量是:剩餘供給總和等於剩餘需求總和。刪去剩餘餘額為 的葉,一邊因葉消失而減少 ,另一邊因其鄰點被扣減而也減少 ,所以不變量保持。只剩一個頂點時,不變量的一邊是空和,故該頂點剩餘餘額為零,其方程在沒有邊可調整的情況下仍然成立。若沒有平衡條件,同樣的剝葉仍迫定每條邊的數值,但最後一條方程不成立,於是不存在解。
這個證明亦顯示,線性無關與樹形是同一件事的兩種描述。
概念視角組合
基恰好就是生成樹
以 記 在平衡系統中的列:在行方程 與列方程 處各有一個一。一組格的列線性無關,當且僅當這組格不含環。若含環,沿環交替加減這些列得零,因為環上每行每列各以正負號出現一次。若不含環,這些格構成森林;對右端為零的系統作剝葉論證,迫使每個係數為零,所以各列線性無關。由於秩為 ,一個基有 個線性無關的格,而 個頂點上 條邊的無環圖正是生成樹。線性代數要求列線性無關,圖論要求生成樹,兩者選出的是同一批格。
只有 這個數目並不足夠,下面的檢驗說明這一點。
反例模式
格數正確不一定構成基
聲稱:任意 個格都唯一決定一個基本運量。取 、,供給 、需求 ,兩者平衡。四個格 的數目正是 。對每個 ,
的行和為 、列和為 ,所以在這些格上平衡方程有無限多個解。聲稱失敗,是因為這些格含有環 ,又沒有接觸目的地 。若供給為 、需求為 ,同一組格根本無解,因為沒有任何格能運到目的地 。正確的假設是這些格構成生成樹,而不只是數目為 。
價格與換運
在每條樹邊上令 。先任選一個價格(例如 ),再沿樹傳播;樹無環,價格不會矛盾,樹連通,每個價格都被決定。
定義 23.1.3
(樹價格與約化費用)
對一棵運輸樹,若價格 與 在每個樹格上滿足 ,則稱為樹價格。格的約化費用是 ,在樹格上為零。
定理 23.1.4
(非負約化費用證明最優)
設運輸樹的基本解 可行, 為樹價格,且每個非基格都有 。則任意可行表 滿足
而 達到此下界,所以 最優。
證明
(代入約化費用)
把 代入 的費用,並使用平衡方程:
每個 均非負(樹格上為零,其餘按假設非負),而每個 ,所以最後一項非負。 只在樹格上可能非零,那裏 ,故取 時最後一項為零, 達到下界。價格本身可以為負,重要的只是約化費用的不等式。
若某非基格的約化費用為負,把它加進樹會形成唯一的環。從該格開始交替加減 ;每個涉及的行與列各有一次加和一次減,所以餘額不變。取減號格當前運量的最小值為 ,並刪去一個變為零的減號邊,便得到新樹。費用變化為 ,因為樹邊上的價格沿環相消。若 ,換基不改變運量或費用,稱為退化換基;此時單憑該基的負約化費用不能斷言當前運量非最優。重複退化換基可能循環;保證終止需要適當的防循環規則。
例題詳解
例題 23.1.5
(一次換基和最優性證書)
供給為 、需求為 ,費用與初始表為
初始費用為 。以四個正格為樹,取 ,樹方程給出 、、、。格 的約化費用為 。環上 依次取號 ,步長為 。新表為
兩個減號格同時變零;保留 為零基格,移除 。新樹價格為 、,非基格約化費用 、 均非負。下界為 ,等於實際費用,所以新表最優。保留零邊是為了維持生成樹,不代表該路線有正運量。
例題 23.1.6
(剝葉產生零值基格)
供給為 、需求為 ,樹由格 組成。它有 個格且連通:產地 連到目的地 ,產地 連到目的地 。
目的地 是葉,所以 ,產地 剩餘餘額為 。目的地 是葉,所以 ,產地 剩餘餘額為 。此時產地 只剩格 ,成為葉,故 ,目的地 仍剩餘 。最後一條邊給出 ,產地 與目的地 的餘額同時歸零。
行和 、列和 均正確。這個解可行而且退化:基格 的運量為零。只有三個格為正,但基有四個格;若去掉 ,產地 便與樹的其餘部分斷開,價格亦無法傳播。
例題 23.1.7
(基本解不可行的樹)
供給為 、需求為 ,樹由格 組成。產地 是葉,所以 ,目的地 剩餘 。目的地 與 是葉,所以 、,產地 剩餘 。最後一條邊給出 ,兩個剩餘餘額隨即為零。
行和為 、列和為 ,平衡方程成立,正如定理所說。元素 使這個表不可行。任何樹都給出基本解,但單純形法只能使用基本解非負的樹;在這裏計算的樹價格不能證明任何事。
常見錯誤
常見錯誤
(以正運量的數目找基)
退化可行解的正運量少於 個。只取正格作為基,得到的是森林而不是樹,價格方程便有多於一個自由價格。應加入零值格把森林重新連接,而不形成環,就像第二個例題那樣。
常見錯誤
(把負約化費用當作非最優的證明)
負的 只表示這個基未能證明最優,並不表示運量可以改善:若環上某個減號格的運量已是零,步長 ,費用不變。同一運量的另一棵樹可能所有約化費用均非負。
練習
快速檢查
(對第一個例題的最優表,用所列價格驗證兩個非基格的不等式,並直接計算費用。)
解答 · 答案
格 與 的價格和為 、。費用為 ,等於價格下界。
快速檢查
(某入基格的約化費用為 ,但一個減號基格的運量為零。容許步長是多少?可以得出甚麼結論?)
解答 · 答案
瓶頸為零。讓該格入基並移除一個運量為零的減號樹格;運量表和目標值都不變。此步既不能證明嚴格改進,也不能證明最優,應繼續計算約化費用。
快速檢查
(兩個產地、兩個目的地,供給 、需求 ,費用矩陣為 。找兩個不同的最優表,並解釋其費用為何相同。)
解答 · 答案
對角表與反對角表的費用都是 。事實上 ,所以沿四格環的任何可行換運費用變化為零。每個可行表都形如 ,,其費用 與 無關,故每個可行表都最優。