本節處理先前單純形一節中,現成可行鬆弛基所掩蓋的問題:如何開始、如何節省更新工作,以及如何避免退化主元重複。
動機
紙上字典容易逐項核對,但大型矩陣若每次更新全部項目,會浪費大量工作。修訂單純形法保留當前基的分解,只在考慮某個進基列時求所需數據。變的是儲存與計算安排,不是主元的數學意義。
另一障礙更基本:下限需求或等式限制未必提供可行鬆弛基。不能隨意猜一點便使用原始比值檢驗,因為該檢驗依賴目前基本值非負。第一階段以另一個優化問題決定原系統能否滿足,而非把違反限制當成可接受安排。
合法主元也可能沒有移動決策點。若某基本值已為零,即使進基約化成本為正,容許步長仍可為零。有限個基不保證算法停止,除非有規則防止重訪。下面列出真實六步循環,再用字典序擾動證明如何排除它。
定義
定義 4.1.1
(修訂單純形所需數據)
最大化標準形為 , 有滿行秩。對可行基 ,求解
非基本列的約化成本是 。若其為正,增加 達 時,基本向量變為 ;只在 的行取最小比值 決定離基者。
這些是線性求解,不要求顯式形成逆矩陣。轉置求解後,各約化成本只需一次列內積;選定進基列後,再求一次方向。基分解可作更新,但浮點穩定性及重新分解策略另需分析。
基本值測試原始可行性,約化成本測試目前基是否提供目標上界,兩種小數值不能混淆。精確算術有明確符號;數值容差則要配合尺度並重新核驗。防循環規則本身不會修復病態基的求解誤差。
選好進基列後,方向中非正的行不限制步長,因其基本值不降。若所有方向分量都非正,且約化成本嚴格為正,便有保持等式及非負性的改善射線;這不是「找不到離基者」的算法故障,而是問題目標無界的證書。反之,某個零基本值所在行若有正方向分量,就會把步長壓到零。把這兩種情況分開,才能理解退化與無界為甚麼需要完全不同的處理。
定義 4.1.2
(第一階段問題與人工變量)
按需要將等式行乘負一,使 ,再每行加一個非負人工變量,組成 ,求解
人工單位列給出可行初始基 。
不等式先加入普通鬆弛或扣除剩餘變量,再只在需要處加入人工列。人工量只是計算工具,不是原模型的新決策。
定義 4.1.3
(退化基與循環)
若基本可行解至少有一個基本座標為零,稱為退化。若一串主元回到一個已訪問過的基,稱為循環。
兩者不同:退化主元可以無害,數個基代表同一點也不一定形成循環。
定理/命題
定理 4.1.4
(第一階段究竟證明甚麼)
原非負等式系統可行,當且僅當第一階段最小值為零。正最小值證明不可行。零最小值時,可用結構列的非零係數作零步長主元移除零值人工基本變量,或刪除冗餘的變換後等式,得到第二階段的結構基。
定理 4.1.5
(字典序擾動排除循環)
精確算術下,設 為可行初始基,形式上把右端改為
其中正 小於每個正實常數。依升冪第一個非零係數比較步長。採正約化成本進基與此字典序比值檢驗時,基不會重複,有限步到達最優基或改善無界射線。終止最優基取常數項便給原問題最優解。
擾動必須配合初始基。直接在任意右端加一個正向量,未必使其基本座標為正。把形式符號改成任意很小的浮點數,也不等於獲得精確防循環保證。
概念視角幾何
擾動把退化頂點拉開
在退化頂點處,經過同一點的限制超平面 多於其位置所需,所以幾個可行基指向同一點,它們之間的主元步長為零。在擾動後的問題中沒有基本座標為零,所以不同的可行基給出不同的頂點:擁擠的頂點被拉開成鄰近的多個頂點,每個頂點恰有一個基。於是每次主元都沿一條形式長度為正的真正的邊移動,這就是嚴格改善的幾何含義。
證明思路
證明
(第一階段的值與清理主元)
人工量非負,故第一階段 。原系統若可行,附上 就有值零;反之,非負人工量之和為零迫使每項為零,留下原可行點。正最小值因此排除可行性。第一階段可行且下有界,有限最小值能取得;下一節會以有限維方法證明線性規劃的取得性。
在零最優值處,人工基本量必為零。消去其他基本變量並把人工量設零後,若該行仍有非基本結構變量的非零係數,便可用它換走人工量。進出值都是零,所以即使主元係數為負,表示的可行點仍不變。若已沒有任何結構係數,便只剩 ,可刪除。反覆處理後只留原變量及普通鬆弛、剩餘變量。恢復原目標,重算轉置系統及約化成本,不能沿用輔助目標。
證明
(形式非退化給出嚴格改善)
防循環證明中,初始基本向量為 ,在形式次序下嚴格為正。任意基的基本座標是 的多項式;它不可能恆零,因為擾動係數構成可逆矩陣 的一行。
因此可行擾動基沒有形式退化。兩個候選行的比值也不可能完全相同,否則 的兩行成比例,違反可逆性。最小比值唯一且正,每次有界主元遂嚴格提高形式目標。每個基唯一決定一個目標多項式,不能回到舊基;基只有有限個,所以必停止或發現改善射線。
終止時約化成本是非正實數,因擾動沒有改成本。基本多項式的常數項非負,否則負常數會壓過所有擾動項。故常數項形成原可行基,非正約化成本證明最優。改善射線只取決於方向及約化成本,不取決於右端,所以也證明原問題無界。
這個證明為每個基附上一個嚴格遞增的量,把有限搜尋變成必然終止的過程。下面的剖析記錄每個假設在哪裏使用。
證明透視
只有有限個基還不夠
證明的核心是一個由基決定、並在每次有界主元嚴格遞增的量。在有限集合中取值的嚴格遞增序列不能重複取值,所以基不能重現。普通目標值也由基決定,但在零步長時不嚴格增加;下面的六步循環正是這種失效。
各假設在不同位置使用。 可行,加上擾動中的因子 ,使初始向量 形式上為正。 可逆用了兩次:沒有基本座標恆為零,也沒有兩行給出相同比值,於是離基行唯一,每個步長 形式上為正。正的進基約化成本再把 變成嚴格的形式增量 。精確算術不可少,因為比較讀的是 的係數;捨入可能抹掉兩個比值首個不同的係數。
收尾一步回到原問題。約化成本從不涉及 ,而負常數項會壓過所有擾動項,所以終止基的常數項給出原問題的可行點及最優性憑證。
例題詳解
例題 4.1.6
(第一階段找起點,第二階段改善它)
最大化 ,限制 、 及非負性。引入剩餘 、鬆弛 、人工 :
起始 、、。讓 進基降低 ,比值二及四取二, 離基。得
非基本量全零即 ,證明原可行。刪人工列後,原目標是 。讓 進基, 增而 減,步長二時 離基:
最優 ,值十二。兩階段分別回答可行性及原目標最優性。
例題 4.1.7
(不用完整表格重現主元)
第一階段後基本次序為 ,有
轉置求解給 ,所以 、。剩餘列為 ,解 得 。只第二行限制步長,故取二;舊基本值成 , 進基, 離基,與字典計算完全相同。
例題 4.1.8
(精確六次主元循環)
最大化 ,全部變量非負,限制
普通鬆弛標為 。每次取最大正約化成本進基,進基成本平手時取變量編號最小者;最小比值平手時取編號最小基本量離基,精確求解得:
| 當前基的行次序 | 進基 | 離基 | 約化成本 | 步長 |
|---|---|---|---|---|
| 1 | 5 | |||
| 2 | 6 | |||
| 3 | 1 | |||
| 4 | 2 | |||
| 5 | 3 | |||
| 6 | 4 |
回到 ,決策點始終是原點,目標零。每步都合法,但規則循環;字典序比值會分開零比值平手,阻止重返。這是精確算術障礙,並非只由捨入引起。
常見錯誤
常見錯誤
(人工變量不是決策)
人工量不能當成原模型可隨意使用的實際決策。正值表示原等式尚未滿足,並非可以接受的違反。即使輔助目標已為零,人工量仍可能以零值佔據基本列,所以「第一階段值為零」本身並未完成清理。
最後一點容易被低估,下面用具體系統說明。
反例模式
第一階段值為零仍可留下基本人工變量
聲稱:第一階段最小值為零時,最後的第一階段基只含原變量,可以直接開始第二階段。考慮冗餘系統 、,,人工變量為 :
讓 進基。兩個比值都是一;讓 離基。代入得
中 的係數為 、 的係數為 ,沒有進基變量能降低 ,最小值 已經達到。可是 仍是基本變量,值為零,所以上述聲稱不成立。修正就是定理中的清理:把人工量設為零後, 所在行為 ,沒有結構係數,予以刪除,剩下方程 及結構基 。
常見錯誤
(冗餘行與矛盾行)
冗餘要在消去其他基本變量後的變換系統中判斷,不能憑係數看似重複便下結論。若變換後的行為 且常數非零,那是矛盾,不是冗餘。秩檢查與刪行都必須保留這個區別。
常見錯誤
(只選小離基編號不能防止循環)
最大約化成本規則可以循環,上表已經示範。另一種精確防循環法 Bland 規則,要求進基者取最小合資格編號,離基平手時亦取最小編號基本量;其證明與本節的字典序證明不同。只在離基平手時選小編號並不足夠,因為上面的循環例子已經這樣做。
總結
修訂法以基求解代替完整字典更新;第一階段取得或排除起點,清理後才恢復原目標。退化使普通目標不再嚴格增長,字典序擾動恢復形式上的嚴格改善,才可用有限個基證明終止。
練習
快速檢查
(對 ,寫一個只有一個人工量的第一階段模型並求最小值。)
解答 · 答案
用 及全部非負,最小化 。第二式使 ,所以 。取 達到一,證明原系統不可行。
快速檢查
(修訂例的目標改成 ,求基 的 約化成本,判斷可否改善。)
解答 · 答案
,故 ,、,兩者皆可進基。進 得方向 、步長二,到 ;進 到 。兩點值均四,這個目標有多個最優點。
快速檢查
(比較 與 ;兩者都捨入零會失去甚麼?)
解答 · 答案
首個不同係數在二次項,一小於三,故第一個比值較小。它們都是不同的正形式量;把兩者都當零正是抹掉選離基行的資訊,精確終止證明便不適用。
快速檢查
(零人工基本行消去後為 ,應如何處理?與 比較。)
解答 · 答案
用任一非零結構係數換走人工量,進基值為零,負主元係數也不改目前可行點。該行仍限制結構變量,不可刪; 才是真正不施加限制的冗餘行。