單純形法每次換基,都會改變所使用的基,卻不一定改變可行點。如果所有算例的比值檢驗步長都大於零,這個差別很容易被忽略:目標值每步嚴格增加,自然不能回到舊基。然而,在退化點上,一個值已經是零的基變量可以離基。即使入基變量的約化成本為正,目標值仍可能保持不變。
較早的單純形筆記用字典序擾動證明了終止性。Bland 規則採取另一種方法:保留原問題,始終按變量的固定編號作選擇。規則本身很短,但其證明揭示入基和離基的選擇為何必須配合。本節會直接證明這種配合,避免把零步長也錯當成目標嚴格改善。
基、它代表的點,以及主元方向
考慮有限維標準形式問題
其中 的行秩為 。假設已經找到一個可行起始基。把所有變量固定編號為 ,包括鬆弛變量及模型中的其他變量。這些編號不會隨表格的行次序改變。
定義 15.1.1
(以變量編號標記的字典式)
基是由 個列編號組成的集合 ,使基矩陣 非奇異。把基列按一致次序排列,並用 表示其補集。解出基變量後得到
這裏 、、,而 。標記為 的行,是以 為基變量的那一行。令 便得到基本點;若每個 ,這個基就是可行基。
不同的基可以代表同一個點,因為某個零座標可能在一個字典式中是基變量,在另一個字典式中卻是非基變量。基記錄要解出哪些列所對應的變量;點則記錄全部變量的數值。若可行基至少有一個基變量的值為零,就稱該基為退化;它代表的點便少於 個正座標。循環是經過非空的一串主元步後回到同一個基。
設 且 。把 從零增加,同時把其他非基變量固定為零,所得方向 為
它滿足 及 。比值檢驗所允許的步長是
如果沒有任何 ,則 的所有基座標均非負。因此,對每個 ,點 都可行,而且目標值趨向正無窮。否則,上述最小值可以取得;把其中一個取到最小值的基列換成 ,就得到另一個非奇異可行基。事實上,在原基座標下,替換矩陣的行列式除列次序所造成的正負號外,就是非零的 。目標值增加 ,只有在 時才可能沒有增加。
定義 15.1.2
(Bland 規則的兩個選擇)
在每個可行字典式中:
- 若所有非基約化成本均滿足 ,便在最優解停止。否則,選取滿足 的最小編號 入基。
- 若入基列沒有正的字典式係數,便以上述改善射線停止。否則,進行比值檢驗,讓所有最小比值候選中基變量編號最小的一個離基。
符號和比值都使用精確比較。只有在並列最小比值的行中,最先列出的行恰好含有這些候選中最小的基變量編號時,選第一行才與這條規則相同。
最優性停止條件直接來自字典式。任何可行點的非基座標均非負;若所有 ,便有 。當前基本點取得 ,所以最優。零約化成本可能容許其他最優解,但規則毋須先走遍它們才確認最大值。
換基後仍成立的成本恆等式
證明會用兩個不同的字典式觀察同一個方向。兩組約化成本的數值看來可能沒有關係,所以先找出它們共同計算的量。
命題 15.1.3
(約化成本可計算每個零空間方向的成本)
對任何基 、其非基集合 及約化成本 ,只要向量 滿足 ,就有
不一定是從該基所代表的點出發、能沿正步長前進的可行方向。
證明
(消去基座標)
齊次約束給出 ,因此 。代入目標內積便有
這是代數恆等式。在零步長主元步中,入基方向可能令某個零基座標在任何正步長下立即變負,但這並不妨礙使用此恆等式。
有限終止定理
定理 15.1.4
(Bland 主元規則不會重複一個基)
假設變量數有限、約束矩陣行滿秩、起始基可行,並以固定變量編號及精確運算執行 Bland 規則的兩個選擇。則原始單純形法不會重複一個基,因而在有限次主元步後終止:不是得到最優基本可行點,就是得到證明目標向上無界的改善可行射線。
證明
(最大變動編號導出符號矛盾)
假設某個基重複出現。只考慮從第一次出現到再次出現之間的非空有限主元序列,包括回到原基的那一步。以下分四步導出矛盾。
第一步:序列中的每一步都是零步長。 每個入基約化成本嚴格為正,每個比值檢驗步長均非負,所以目標值不會減少。一個基唯一決定其基本點及目標值,回到它便回到相同目標值。因此,各步非負增量 的總和為零;每個 都只能是零。序列中所有字典式於是代表同一個點 。
若一個變量在序列中的某些字典式是基變量、另一些卻是非基變量,就稱它為此序列的變動變量。每個入基或離基變量都是變動變量。所有變動變量亦滿足 ,因為它曾在某處非基,而整個序列的點沒有改變。
第二步:選取最大的變動編號。 設 是最大的變動變量編號。選取 某次離基之前的字典式 ,並設該步讓 入基。兩個變量都是變動變量,而且 ,所以 。以 表示這一步的方向,特別有
把這段序列視為從 開始的封閉循環,必要時繞過原來列出的終點。由於序列回到起始基, 離基之後必定再次入基。以 表示某次重新入基之前的字典式,其非基集合為 ,約化成本為 。Bland 入基規則給出
第三步:判斷舊方向 的相關座標符號。 若 且 ,則由 的最大性可知, 的基或非基身份從未改變。因此,它在 中也非基。因為 ,方向定義給出 。
現在考慮 且 。若它在 中也非基,則 為零;當 時則為一,兩種情況均有 。若它在 中是基變量,它就是變動變量,所以 。假如 ,便有 ,令其比值 。離基變量 的比值同樣是零。於是, 便是一個比 更小編號的並列最小比值候選,與 中的離基規則矛盾。因此
第四步:在 中計算同一個成本變化。 由 及前面的恆等式,
當 時,每一項均非正;當 時,每一項均為零;而 那一項嚴格為負,因為 、。所以 ,與在 中算得的嚴格正值矛盾。
故沒有基會重複。大小為 的列集合最多只有 個,因而可用基的數目有限。每個未停止的迭代都會進行一個定義明確的可行主元步,所以算法必定到達其中一個停止條件;前面已證明這兩種停止條件分別給出最優性或無界性的證書。
證明透視
各個假設在哪裏發揮作用?
嚴格為正的入基約化成本,迫使假想循環內所有步長均為零。固定編號讓我們選出最大的變動變量。入基規則控制它重新入基時、較小非基編號的約化成本符號;離基規則則控制它離基時、舊方向相關座標的符號。成本恆等式把這兩種符號限制變成矛盾。只有排除重複後,「基的數目有限」才足以推出終止。
證明沒有使用數據為有理數的假設:它討論的是精確實數比較。它亦沒有聲稱主元步數存在多項式上界。粗略計數 可隨問題大小以指數速度增長。防止循環解決的是邏輯上的終止問題;選擇規則在實際計算中有多快,是另一個問題。
算例:兩次零步長後才真正前進
例題 15.1.5
(點可以不變,但有用的基仍會改變)
最大化 ,約束為
依次加入鬆弛變量 ,起始字典式和目標為
基是 ,對應點為 。只有 的約化成本為正。基變量編號 的比值分別為 。Bland 規則在零比值並列中選編號 ,所以 入基、 離基,步長為零。解出 後得到
現在讓 入基。會減少的基變量是 ,比值分別為零和一。因此, 又以零步長離基,下一個字典式為
例題 15.1.6
(離開退化點並確認最優)
接續上例的第三個字典式。至此三個基都代表 。現在 以約化成本一入基。 均增加;只有 限制步長,其比值為一。讓 離基後得到
非基變量是 ,約化成本為零及負一,故解為 ,目標值一。獨立地,約束 亦證明此值最優。保持 並增加 ,會得到 的其他最優解;所以出現零約化成本與停止完全相容。
| 作選擇前的基 | 入基 | 離基 | 步長 | 換基後目標值 |
|---|---|---|---|---|
| 1 | 3 | |||
| 2 | 4 | |||
| 3 | 5 |
頭兩步沒有改善點,但也沒有重複基。終止定理正是容許這種行為。
反例模式
零步長不是最優性證書
此例的起始點只允許第一步取零步長,但可行點 的目標值更高。若一遇到零步長便宣布最優,就會交出錯誤答案。另一方面,零約化成本也不是 Bland 規則的合格入基條件:必須嚴格為正。只按最小編號選變量、卻不檢查符號,便失去了證明所用的目標單調性。
另一種停止條件是改善射線:入基列沒有正的字典式係數時便會出現。
例題 15.1.7
(以改善射線終止)
最大化 ,約束為 及 。加入鬆弛變量 後,起始字典式為
只有 的約化成本為正,Bland 規則讓它入基。唯一的比值是 ,所以 以步長一離基:
現在 、,所以 入基。它在唯一一行的係數是 ,並非正數,比值檢驗沒有候選,規則停止。方向為 、、,即 。它滿足 ,所以對每個 ,點 都可行,目標值為 。問題向上無界,而這條射線就是證書。
容易混淆的地方
常見錯誤
(單靠最小離基編號不能防止循環)
單靠最小離基編號並不足夠。較早筆記的六步循環例子,已在離基並列時選最小基變量編號,但入基時選最大的正約化成本。Bland 定理還要求選最小的合格入基編號。
常見錯誤
(誤以為規則包辦第一階段或容差處理)
定理從可行基出發。它沒有代替第一階段,也沒有允許對含負基本值的字典式直接套用原始單純形比值檢驗。它同樣不會消除浮點歧義:用數值容差取代精確的零,會改變合格候選和並列集合。程式可能需要數值保障,但那要另作分析。
常見錯誤
(把不重複理解為點不重複)
最優點或其他退化點的基未必唯一。定理排除的是這條主元序列中重複的基,而不是重複的點。運行前把變量重新編號一次,仍可得到另一個適用此證明的固定次序;在主元步之間不斷改編號,則不再滿足假設。
練習
快速檢查
(某可行字典式的非基編號是 ,約化成本分別為 。對選出的入基列,基編號 的 分別是 。選出 Bland 主元步。最後一行會限制正步長嗎?)
解答 · 答案
正約化成本中最小的編號是 ,不是 。編號 的比值並列為零,所以編號 離基,步長為零。編號 的係數為負,故入基變量增加時該基變量也增加,不能提供步長上界。只有 的行可參與取最小值;零或負係數都不限制步長。
快速檢查
(在退化算例的第一次換基後,寫出讓 入基的完整五座標方向。為何其目標斜率為正,卻不能從該字典式的點走任何正步長?)
解答 · 答案
按座標 排列,方向為 。由於目標是 ,有 。但當前點的 且 ,任何正步長都會令 變負。方向給出代數上的目標斜率;比值檢驗則另行施加可行性限制 。
快速檢查
(在終止證明中,為何對 中非基且 的編號,可以斷言 ?為何不能把同一句話直接套在每個 上?)
解答 · 答案
大於 的編號不是變動變量,所以它在 非基就表示在 也非基。舊方向唯一非零的非基座標是入基編號 。較小的編號卻可能改變身份,在 中為基,其方向座標由字典式係數決定;必須結合離基並列規則和零基本值,才可證明該座標非負。
快速檢查
(設 ,起始可行基已固定。不重複基能給出多少次主元步的粗略上界?這個計數是否證明任意維數下的計算都很有效率?)
解答 · 答案
基集合最多有 個,包括起始基。每個主元步到達另一個集合,因此到達終止基之前最多進行九步。奇異或不可行的集合只會令此數減少。一般維數的相應二項式計數可以是指數級,所以這不是多項式複雜度保證。
快速檢查
(把退化算例的目標改成 ,在起始鬆弛基套用 Bland 停止條件。說明為何強行讓 入基不屬定理的範圍,即使它的編號最小。)
解答 · 答案
起始非基約化成本是 ,兩者均非正,所以當前點已最優,值為零; 也給出獨立證書。強行讓 入基違反嚴格正約化成本的資格條件。第一次強行換基恰好是零步長、沒有改變目標值,但這個巧合並不滿足單調性及防循環證明的假設。