生產計劃依賴預計利潤;估計改變時,原計劃是否仍然最優?可行集合沒有移動,但衡量改進的方向變了。約化成本可先檢驗原有的基,再決定是否需要重新優化。本節討論一般的基檢驗。
改變成本後的證書
定義 22.1.1
(改變目標後的基與約化成本)
考慮有限維線性規劃:在 、 下最小化 ,其中 滿行秩。基是由 的列組成的可逆方陣 ;餘下的列組成 ,相應地分割 及 ,並令 。若 ,稱此基原始可行。對成本向量 ,其乘子及約化成本為
以下一直假設基 原始可行。
定理 22.1.2
(成本變化的精確基檢驗)
若 ,基本解 對新目標最優。反過來,如果存在對偶可行乘子且在所有基列上取等,那麼必有 。所以這些不等式精確描述使此基同時原始可行、對偶可行的成本向量;零約化成本和退化基也包含在內。
證明
(把基變量代入目標)
任一可行解滿足 。代入目標得
若 ,由於 ,最後一項對每個可行解都非負,基本解達到全局最小值。等價地, 和 給出相等的對偶下界。反過來,基列上的等式唯一確定乘子為 ;其餘列的對偶可行條件正是上述不等式。
證明透視
代入恆等式能決定甚麼、不能決定甚麼
假設在哪裏用上: 可逆,令每個可行點都能以非基座標表示; 令基本點可行,才有資格作候選; 把 變成非負的餘項。
關鍵一步:恆等式 對每個可行 都成立,所以檢查有限個係數的符號便控制了整個可行集。
逆命題比表面看來窄:它利用所有基列上的等式唯一確定乘子,所以是關於這個基作為證書的陳述,而非關於基本點。下面的退化反例顯示兩者的分別。
如何收結: 只依賴 ,而 與 無關。成本改變從不威脅原始可行性,因此一組關於 的不等式就是整個檢驗。
定理的逆命題針對的是基證書:退化時同一點可能由另一基表示,因此原基失去對偶可行性也不能斷言該點不最優。
反例模式
最優退化點上基檢驗失敗
一個看似合理的說法是:負約化成本證明基本點不最優。在 、 下最小化 。唯一可行點是 ,所以它最優。以 為基:、、, 的約化成本是 。此基未通過檢驗,但其基本點最優;改以 為基,得 , 的約化成本為 ,證明同一點最優。正確說法是:檢驗失敗只表示這個基不是對偶證書。
單參數與同時變化
令 。先解 ,再計算 。每一分量都是 的仿射函數;相交所有 就得到精確的基證書區間。非基成本變化直接影響其自身約化成本;基成本變化則改變 ,可能影響所有非基約化成本。只改變 時, 不變,原始可行性自動保留。在證書區間內,最優值為 ;區間外此檢驗本身不告訴我們新最優解。
常見錯誤
(以為基變量的成本變化只有局部影響)
改變基變量的成本,不會改變它自己的約化成本(仍為零);它改變乘子 ,再經 影響每個非基約化成本。在下面的例子中,把基變量 的利潤改為 ,兩個鬆弛變量的係數都會改變,分別變成 和 。以為「 是基變量,所以任何 都無礙」是錯的: 時第二個係數為 ,此基不再最優。
每個係數單獨變化時的允許範圍一般不能直接同時使用。應把所有新係數一起代入約化成本。下面的規則是一個充分的快捷方法。
命題 22.1.3
(100% 規則)
設此基對 及每個成本向量 都已獲認證,即其約化成本全部非負。若 且 ,則此基對 亦獲認證。
證明
(已認證成本向量的凸組合)
寫 ,這是凸組合。映射 是線性的,所以組合的約化成本是非負向量的同一凸組合,因而非負。
實際應用時, 是沿指定方向最大的已認證單項變化, 是實際用去的比例。該規則充分但非必要,且依賴所指定的方向與單項範圍。
常見錯誤
(把單項範圍直接疊加)
每個報告的範圍都假設其他係數不變。兩項各自在範圍內的變化,合起來仍可能越出區域:下面關於同時改變兩個係數的練習中 、 各自獲認證,合起來此基卻失效。應檢驗合併後的約化成本,或確認所用比例之和不超過一。
例:利潤改變
例題 22.1.4
(範圍、端點與範圍以外)
最大化 ,約束為 、、。引入鬆弛變量:
選 為基,得到 、,於是
兩個鬆弛變量的係數都非正,當且僅當 。此時基本計劃 最優,值為 ;最大化問題的對偶價格 在此範圍非負且滿足列約束。 時第二個係數為零,所有 ()均最優。當 ,目標等於 ,由 取到,值為 。端點處的折角說明不能把舊仿射公式延伸到證書區間以外。
同一模型中的同時變化
下面關於同時改變兩個係數的練習給出把兩個利潤改為 時的精確區域: 的基保持最優,當且僅當 且 。單項範圍則是 及 。以下兩個例子比較 100% 規則與精確區域。
概念視角幾何
可認證的成本構成一個錐
把利潤寫成 ,精確區域便成為 ,即 ,其中 :目標落在 處兩條緊約束的法向量所生成的錐內。在定理的最小化形式中,可認證的成本向量恰好是 ,這是一個凸錐。100% 規則正是這種凸性的推論。
例題 22.1.5
(100% 規則認證一個合併變化)
取 。第一個利潤的下降用去其至 的範圍的 ;第二個利潤的上升用去其至 的範圍的 。比例之和為 ,所以規則認證此基。
與精確區域核對: 且 。值為 。直接計算, 給出 ,頂點 給出 , 給出 ,所以 確是各頂點中最好的。
例題 22.1.6
(100% 規則看不見的已認證變化)
取 。 超出單項範圍 ,所以 100% 規則根本不適用。精確區域仍認證它: 且 。
驗證:字典係數為 及 ,均非正。值為 。直接計算, 給出 , 給出 。提高第一個利潤擴大了第二個利潤的空間;單項範圍無法記錄這種相互作用,所以規則充分而非必要。
練習與解答
快速檢查
(約束不變,最大化 。求保持同一基證書的範圍。)
代入 及 。
解答 · 答案
代入得 。兩係數非正給出 ;此範圍內值為 。
快速檢查
(由 出發,把兩個係數同時變成 。求同一基證書的精確區域,並檢驗 。)
兩項變化進入同一個字典。
解答 · 答案
字典為 ;區域是 且 。所給點違反後者。兩項變化單獨看都在允許範圍,合起來卻不被認證: 的值為 ,大於 的 。
快速檢查
(在最小化定理中,退化基有負約化成本意味著甚麼?)
回想定理的逆命題是關於甚麼的。
解答 · 答案
只說明這個基未通過對偶檢驗,不能單憑它判定基本點非最優。上面的唯一可行零點就是反例;需要可行改進方向或其他證書。