方案要承受所聲明的不確定性
生產方案可能在實際資源消耗確定前已選定。名義約束只檢查一個估計係數向量;穩健約束要求同一固定方案對指定不確定集合內每個係數向量都滿足限制。這是最壞情況要求,不是概率陳述;若真實係數落在集合外,它也不提供保證。
以下使用精確實數運算,並假設決策在觀察不確定係數前選定一次。
定義 8.5.1
(一條資源約束的穩健可行性)
設 是係數向量的不確定集合, 是已知容量。若
則稱決策 穩健可行。等價地,。只含 、而解集與之完全相同的不等式,稱為該約束的穩健對應式。
獨立區間
定理 8.5.2
(獨立區間及非負決策下的穩健對應式)
設 ,其中 均有限,並設 。則 穩健可行當且僅當
證明
(逐項上界與一個測試向量)
充分性。 對每個 及每個 ,由 與 得 。求和得 。
必要性。 所有上端點可在乘積集合中同時出現,所以 是容許向量。對它應用穩健可行性,便得 。
證明透視
證明的兩半各用哪個假設
證明的兩半依賴不同的假設。充分性只用到決策的正負:上端點使單一項 最大,是因為 非負。必要性只用到不確定集合的形狀:端點向量 本身必須屬於 ,而乘積結構保證了這一點。兩半各自都可能失效。
若某個固定的 為負,最大值反而在下端點;對正負自由的決策,乘積集合的精確最壞值是對 求 與 中較大者之和。若 不是乘積集合,上端點之和仍是安全上界,但可能無法達到,因此該不等式不再精確;下文的耦合集合就是這種情況。
生產例子
例題 8.5.3
(獨立區間下的穩健最優方案)
選 最大化 ;單位資源係數各自獨立取 中的值,容量為 。由定理,穩健可行等價於 ,即 。因 ,而 達到 ,方案 穩健最優,目標值為 。
例題 8.5.4
(不穩健可行的名義最優方案)
若只代入名義係數 ,約束為 ,名義最優為 ,價值 。但容許係數 對此方案消耗 單位,超過容量 。因此名義最優不是穩健可行證書。在退化情況下,若所有 都有 ,兩個模型便一致。
耦合不確定性改變答案
定理 8.5.5
(單參數耦合集合的最壞情況)
設 。對 ,
所以容量為 時,穩健對應式是兩條不等式 、。
證明
(最大化參數的線性函數)
對固定的 , 是 的線性函數,所以在符號與 相配的端點取最大值,其值為 。恆等式 完成計算,而 等價於 且 。
例題 8.5.6
(耦合不確定性容許較大的方案)
兩個係數各自都介於 和 ,但不能同時為 。在耦合集合下,最佳方案是在 上最大化 ,即 ,目標值 。若用較大的獨立方盒 取代此集合,會要求 ,最優值變成 。該方盒對耦合集合是安全的,但較保守,因為它包含模型說明不會同時出現的係數組合。
常見錯誤
反例模式
單獨的範圍不能決定聯合不確定性
在耦合集合的最優方案 ,每個容許的 都恰好消耗四單位,因為 。獨立方盒中的係數向量 會消耗八單位,但任何單一 都不能產生它。相同的各係數範圍因此可以給出不同的精確穩健可行集,必須說明哪些組合可以同時出現。
常見錯誤
(對負決策代入上端點)
若 、,則 取值於 ,在下端點最大。使用 會把最壞情況低估 ,並可能接受不可行的方案。
常見錯誤
(期望在聲明的集合以外仍受保護)
穩健方案 對 中的係數是安全的。若第一個係數實際上是 ,它會消耗 單位,違反容量 。保證只涵蓋所聲明的不確定集合。
練習
快速檢查
(獨立區間 、容量 時, 和 各自穩健可行嗎?)
解答 · 答案
最壞用量分別為 和 。前者可行,後者不可行。
快速檢查
(在耦合模型取 、,求一個達到最大值的 和最壞資源用量。)
解答 · 答案
,故取 ,係數為 。最壞用量為 。
快速檢查
(在耦合集合及容量 下,對穩健可行的非負 驗證上界 。)
解答 · 答案
穩健可行給出 和 ,所以 ,在 取等號。
快速檢查
(若 、,哪個端點使 最大?為何非負變量公式失效?)
解答 · 答案
下端點給出 ,大於上端點的 。乘以負決策會倒轉端點的次序,所以證明的充分性部分不再適用。