整數規劃算法不能修正一個表達錯誤的模型。本節把常見的邏輯條件化成線性不等式,再證明轉換後恰好保留原來允許的決策。
用開關表示一項活動
定義 3.4.1
(啟停開關、最低產量與固定費用)
假設機器的產量 介乎零與已知產能 之間。二元變量 以 表示已啟用、 表示關閉;若
便稱 為 的啟停開關。最低產量 ()則再加上 。啟用機器所需的固定費用 以目標函數中的 表示,另加變動成本 。
定理 3.4.2
(受開關控制的活動的可行產量)
啟停約束投影到 上是 ,而 時強制 。加上最低產量後,投影恰為 。
證明
(兩個二元情況)
若 ,約束化為 (及 ),故 。若 ,約束化為 ,或加上最低產量後的 。反過來, 配 可行,而所述區間內每個 配 都可行。投影就是兩個情況的併集。
這是啟停約束,並沒有說啟用時必須有正產量: 仍然可行。若連續產量可以是任意小的正數,就不能隨意選一個正的 來表達「 當且僅當 」:這樣會錯誤排除較小的正產量。
只要 ,即使機器閒置,固定費用也要支付。若在最小化問題中 ,而在 時只把 由一改成零仍滿足其他所有約束,最優解不會選 :因為這樣改動可以降低成本。但若其他約束也涉及 ,這個論證未必成立;固定費用為零時,也不能推斷閒置的開關必然為零。
例題 3.4.3
(含固定費用的產能選擇)
需求為 單位,不容許超額供應。機器 A 產能為 ,單位成本為 ,啟用費用為 ;機器 B 產能為 ,單位成本為 ,沒有啟用費用。令 ,,模型是
當 ,唯一選擇是 ,成本為 。當 ,代入平衡式得成本 ;由 ,最佳選擇為 ,成本 。所以啟用 A 最佳。A 的物理產能是 ,但本模型的平衡式和非負性也給出 ,故 是此模型有效而更緊的表述。已比較兩個二元情況,因而證明了全局最優性。
條件約束與有效界限
設 包含不論開關狀態均適用的約束。要表達
可使用 ,其中 是二元變量。
定義 3.4.4
(有效的大 常數)
若有限常數 滿足
便稱 對這個蘊涵有效。若不啟用的分支沒有可行點,每個 都有效。
定理 3.4.5
(大 蘊涵的精確性)
若 有效,約束 在 時施加 ,在 時不排除任何允許的點。若在 中各變量都有有限界限 ,則
是有效的。
證明
(分情況檢查與逐項界限)
當 ,不等式還原為 。當 ,它成為 ,按有效 的定義,每個允許的不啟用點都滿足它。至於方盒界限: 時每項 至多為 , 時至多為 ;相加便在整個 上,因而在不啟用分支上,為 給出上界。
反方向的蘊涵並未被加入:不啟用時,原不等式也可能剛好成立。若違反量沒有有限上界,就無法以此方法找到有效的有限 ;無窮大不是線性規劃的係數,必須尋找其他有效界限或改用別的表述。
太小會悄悄排除本來允許的決策;有效但過大的 則會削弱線性鬆弛,亦可能造成數值問題。因此不能只憑「夠大」選值。
例題 3.4.6
(檢驗兩個 值)
設 ,要求 ,而 時整個區間均允許。不啟用時最大的違反量是 ,所以 是最小的有效值,方盒公式亦給出同一數值。取 得 ,在 處成為 ,錯誤排除該點;取 則得 ,保留該點。
擇一決策
例題 3.4.7
(表達兩個不相交的區間)
假設 ,並要求 或 。令 選第一分支, 選第二分支:
當 ,這兩式成為 和 ;當 ,則成為 和 。常數 和 是由整體界限得出的有效大 M 值,分別是第一及第二分支約束可能被違反的最大量。反過來,兩個區間內每個點都可配上相應的 。所以投影到 的可行集合恰好是 。
一般而言「或」包括兩者同時成立:如果兩個分支重疊,重疊處可以容許兩個開關值。若沒有開關而同時施加兩條分支約束,得到的是交集。
二元變量與連續變量的乘積
定理 3.4.8
(二元與連續變量乘積的精確線性化)
假設已知有限界限 , 是二元變量。則滿足 的 符合
當且僅當 。
證明
(檢查兩個二元情況)
若 ,第一組不等式強制 ;第二組化為 ,由 可知成立。若 ,第二組強制 ,第一組便只是 原有的界限。因此每個可行三元組均滿足 ;反過來,每個有界的 和二元 ,連同 ,也滿足全部四條不等式。
證明透視
每組不等式在一個情況收緊、在另一情況多餘
四條不等式是兩組大 M 不等式。 是開關:它在 時把 固定為 ,而在 時無害,只因 本已成立。 是連結:它在 時把 固定為 ,在 時則成為 ,又恰好是 的界限。所以 與 在兩組中都擔當有效大 M 常數的角色。
證明任何地方都沒有用到正負假設; 時同樣成立。用到的是 與 確實是界限。若 小於 可能取得的最大值, 的情況便會施加 ,排除可行點。
下面的反例說明表述的各部分被改動時如何失效。
反例模式
界限為何重要
若 、、,正確的乘積是 。若錯誤加入只適用於非負情況的約束 ,便會排除此點。反過來,如果省去在 時連結 與 的不等式,便容許例如 ,但這並非正確乘積。完整表述及其定義域都不可忽略。
常見錯誤
常見錯誤
(把啟停開關理解為強制正產量)
約束 在 時強制 ,但在 時並不強制 ; 可行。若啟用後產量必須至少為 ,須明確加上 。
常見錯誤
(使用對模型無效的界限)
對 ,若以 寫乘積表述, 的情況便施加 ,排除了允許的點 。用作大 M 常數的界限必須對每個允許點成立,而不只是對預期的最優點成立。
練習
快速檢查
(一項活動要麼關閉,要麼產出 至 單位;啟用固定費用為 ,每單位變動成本為 。寫出可行集合及成本。 可行嗎?)
解答 · 答案
取 、,成本為 。 時 ; 時 ,所以 不可行。
快速檢查
(若 ,而 時容許定義域內所有點,用最小的有效非負 表達 。指出取 時會被錯誤排除的點。)
解答 · 答案
最大違反量為 ,故 有效,而 是最小有效非負值。若 ,原本允許的不啟用點 會違反 。
快速檢查
(若 ,寫出表達 的四條不等式,並求 和 時的 。)
解答 · 答案
四條不等式為 和 。在 ,第二組給出 ,故 ;在 ,第一組給出 。
快速檢查
(在 和「 或 」下最小化 。用上面的擇一表述求解兩個分支。 可行嗎?)
解答 · 答案
時 ,最小值為 ; 時 ,最小值為 。因此整體最小值是 。 不屬於任何一個區間,配任何開關值都不可行。