動機
模型已解好,某項工作需求卻增加。舊基仍描述相同列及價格,但重新求出的基本值可能變負。若立即從無關起點重做,便丟掉已有證書資訊。對偶單純形保留價格可行性,改為修補決策點。
這與原始單純形的不變量相反:原始法保留可行點,利用約化成本改善目標;對偶法保留可行約化成本,逐步消除負基本值。計算中暫容負基本值,不等於模型接受負決策。只有最後雙方可行才可報告最優;若修補失敗,則要給乘數證明新限制根本無法滿足。
成本變動與需求變動不同。成本不改舊點可行性,卻可破壞價格不等式。不能只因問題名叫「重新優化」就固定使用一種算法。我們先推不變量,再據此判斷每類變動後甚麼計算合法。
定義
定義 21.1.1
(對偶可行的最小化字典)
採 , 有滿行秩。基 及其餘列 給
其中 。 等價於 ,稱為基對偶可行;原始可行還要求 。
兩者同時成立時,非基本量設零便得目標 的原始可行點,與對偶界相等,故最優。
即使目前基本點不可行,對偶乘數仍限制全部真正原始可行點的成本。下界有效不要求我們已找出一個可行點,只要求全部乘數不等式成立。這解釋為甚麼修補期間還有可保留的資訊;反過來,若成本變動令某個約化成本負,該下界論證便不能照搬,哪怕目前基本值全部正。判斷算法前須分別檢查這兩邊,不能只看目標數字是否合理。
若 ,其行為
只有 的非基本列能修補此行。基本位置是行位置,離基變量另有原列編號,重排基時不可混淆。 選變換後行,乘 才回到原限制座標;不能直接把行號當乘數。
合資格列的對偶比值為 。其分子是約化成本,不是基本值,所以不是原始步長比值。未寫出標準行便照抄已解行的加減號,容易把合資格方向反轉。
定理/命題
定理 21.1.2
(對偶比值保留價格證書)
選 的行。若有合資格列,取達到
的列進基,換走 。令 ,則新乘數 仍對偶可行,值 ;新進基值為正 。
定理 21.1.3
(失敗行給 Farkas 證書)
若 ,但全部非基本係數 ,則 滿足 。原始系統不可行,且此結論與成本無關。
最小比值可為零,造成對偶退化主元而界不增加,任意選擇可能循環。若每步比值嚴格正,對偶值嚴格增、基數有限,便有限終止。不能只說基有限就當證完;下面的定理給出有限的精確規則。
概念視角幾何
對偶單純形是沿對偶多面體邊行走
對偶問題是 ,它在基乘數處的鬆弛量正是約化成本。對偶可行基就是這個多面體的一個頂點,基本列對應的限制在該處取等號。步驟 沿一條邊移動:只放鬆 的限制,目標的變化率為 。因此負基本值就是一條改進邊,對偶比值是走到某個非基本限制取等號為止的距離,而合資格集為空則給出一條改進射線,對偶目標沿它無界。
定理 21.1.4
(字典序成本擾動使對偶單純形有限終止)
由對偶可行基開始,把其非基本編號排為 ,形式上以 取代 ,並按 多項式的字典序執行對偶比值檢驗。則任何基都不會重複出現;經有限次主元後,方法必到達對原問題原始對偶皆最優的基,或到達一條失敗行,其 Farkas 證書證明原系統不可行。
證明思路
證明
(約化成本在對偶比值步後的變化)
新乘數令每個舊非基本列 的約化成本變成 。非負行係數使它增加;負行係數要求 才保非負。取最小比值使進基列恰緊。舊離基列的新約化成本是 ;其他基本列與 內積零,保持緊。故新乘數對新基可行且基本列全緊,正是新基乘數。
對偶值變化是 。以新非基本量全零解主元行,便得所述正進基值。但其他基本值仍可能負,不能因此立即聲稱原始可行;要重算並繼續修補,直到沒有負值。
這裏沒有證明負基本值的個數每步都減少,也沒有保證每個基本值都更接近零。後面的第一題正展示修補一行後另一行仍會變負。真正單調的是對偶下界,在退化時還要以形式目標加強為嚴格單調;把錯誤的「違反數量一定減少」當進度量,會誤解終止證明。
證明透視
主元規則每個假設各保證甚麼
證明檢查三件事,各自依賴不同假設。符號條件 使進基值 為正,所以這次交換確實修補第 行。比值取最小,使每個約化成本 保持非負:只有行係數為負的列會減少,而最小比值正是它們全部都能承受的最大步長。離基列得到約化成本 ,因為 與它的內積為一、與其他基本列的內積為零;因此 恰好是新基的乘數,而不只是某個對偶可行向量。
論證並不給出原始方面的進展。其他基本值可能變得更負,而且只有 時界才嚴格上升。最優性只在最後得出:當所有基本值都非負,相等的原始值與對偶值互相證明。 的退化步正是需要擾動定理的原因。
證明
(失敗行是 Farkas 證書)
若沒有合資格列,該行對任何非負決策的左端都非負,右端卻負。原座標下,基本列乘積為 ,非基本列乘積為 ,右端乘積為 ,正是擇一定理的不可行證書。零比值仍可作主元運算,空合資格集才是這種失敗,兩者不能混為一談。
退化時的有限精確規則
證明
(字典序成本擾動永不重訪基)
前節擾動右端,這裏有成本側對應。把初始非基本編號排為 ,保持初始基本成本,形式上以 取代非基本成本。初始約化成本成為 ,在字典序嚴格正。在字典序有序多項式環或其分式域使用對偶比值;每步選任一負基本行,需要確定軌跡時可固定選行規則。
對任意基,成本向量模去 行空間後,到非基本約化成本的映射是同構。理由是約化成本全零,恰等價於整個成本向量為某個 ;反向也成立。商空間及約化成本空間的維數都是 。所以不同基之間的約化成本由可逆線性映射連接。
每個新約化成本的擾動多項式不會恆零,因其係數是可逆映射的一個非零行作用在不同冪上。對偶可行遂令它在形式次序嚴格正。因此每個候選比值正,負的實基本值令每步形式對偶目標嚴格增加。同一基唯一決定形式目標,不能重訪;有限個基使算法有限到達可行或失敗行。
取常數項保留非負約化成本,基本值則只由未改的右端及基決定。故終止可行基給原問題最優,失敗行證書也仍屬原系統。任意小浮點容差不能代替這個形式證明;它會抹掉證明中用來區分零值的資訊。
例題詳解
例題 21.1.5
(兩次對偶主元得到可行最優)
最小化 ,需求 ,全部變量非負。用剩餘量寫成
起始 。約化成本非負,基本值卻都負。選第一行, 比值三、二,故 進基:
第二行仍負, 比值一、二,故 進基:
現點 可行,約化成本非負;等式乘數 給界七,與原始值一致。
例題 21.1.6
(右端變動只需一次修補)
只把第一需求由三提高至五,舊基變成
約化成本仍各一,但 不可行。其行只有 的標準係數負,讓它進基得
故 最小十,乘數 也給新界十。舊乘數仍給合法下界九,卻因原始基不可行而不再精確。
例題 21.1.7
(成本變動反而要原始修補)
回到需求三、四,改最小化 。舊點仍可行,但目標成 , 約化成本負,對偶法起始不變量失效。
原始法則可增加 ,令 。,步長二時 離基,得 。故 最優值三,乘數 同值。成本變動破壞的是最優檢驗,不是舊決策可行性。
例題 21.1.8
(失敗行的明確證書)
要求 ,最小化 。起始方程 。第一行進 後,。負第二行無合資格列。
原座標證書 對兩決策列乘積零,對鬆弛列乘積一,右端乘積 。這證明限制本身不可行,不只是目前目標搜尋失敗。
哪個不變量在擾動後保留?
改為 時,乘數及約化成本不變,基本值改為 。 改為 時,基本值不變,乘數改為 ,約化成本為 。這些給精確基範圍。成本及右端同時變,兩種可行性都可能失去,須先用有證明的可行階段,不能盲目指定原始或對偶方向。
常見錯誤
常見錯誤
(由已解行讀取比值檢驗的符號)
對偶比值使用 中的負 係數。在右端變動的例子中,已解行寫作 ,所以 在 的元素是 ,在 是 。若直接照抄 前的加號,便會以為 合資格而 不合資格,正好把正確選擇倒轉。取比值前先寫出標準方程。
常見錯誤
(把負基本值或上升的界當作更好的方案)
負基本值不是模型接受的負決策,對偶界增加也不是不可行點已變成更好的實際方案,而只是下界證書變強了。基本值全部通過符號檢查,才有真正的原始答案。
常見錯誤
(把零對偶步長當作不可行)
零對偶步長不證不可行。無合資格列才產生分離行;退化要另用已證明的防循環政策。只有固定平手規則、卻沒有相應證明,不能當成一般終止保證。
比值檢驗中的最小值也不是可有可無的方便做法,下面的計算說明這一點。
反例模式
任意合資格列都可以進基是錯的
聲稱:對偶比值檢驗中,任何行係數為負的列都可以進基。在第一個例題中,第一行的合資格列是比值為 的 及比值為 的 。若讓 而非 進基,得 、、。 的約化成本為 ,所以新乘數不對偶可行,其值 也不是下界:真正的最小值是 。取最小比值正是保持證書有效的條件。
總結
對偶法保護乘數不等式並修補負基本值。比值由約化成本變化推導,失敗行成為 Farkas 證書。右端變動自然保留其起始不變量,成本變動通常保留原始不變量。形式成本擾動處理普通步長可為零的退化情形。
練習
快速檢查
(第一例需求改 ,從鬆弛基選第一行開始,作對偶主元求 最小值。)
解答 · 答案
第一主元得 ;再進 得 。負 行只容 進基,標準係數負二、比值半。故 。最優 ,值 。
快速檢查
(原最終基把 成本改為 , 成本仍三。求該基保持最優的精確區間。)
解答 · 答案
代入原字典,常數為 ,約化成本 ,同時非負恰為 。基本點保持 ,所以閉區間內該基最優。
快速檢查
(負行 ,,約化成本 。求進基列、對偶步長及界改善。)
解答 · 答案
只前兩列合資格,比值三及一,故第二列進基,,界增加 。舊非基本約化成本變 ,離基量約化成本一,確認對偶可行。
快速檢查
(對 構造非負不可行的 Farkas 向量,解釋為何與成本無關。)
解答 · 答案
給決策列乘積零,兩鬆弛列一,所以 ;右端乘積負一。這與任何非負可行點矛盾,全程不需成本向量。