任務三　0—1規劃及其求解方法

3.1　0—1規劃問題

0—1規劃是變量只取0或1的一種特殊形式的整數規劃。在實際問題中，諸如開與關、取與舍、有或無等邏輯現象都可以用0—1變量來描述。由于0—1整數規劃在實踐中有著廣泛的應用和獨特的建模技巧，所以在此單獨介紹。

例3-3-1　投資問題　某部門三年內有四項工程可以考慮上馬，每項工程的期望收益和年度費用如表3-3-1所示。假定每一項已選定的工程要在三年內完成，試確定應該上馬哪些工程，方能使該部門可能期望收益最大？

解：這是工程上馬的決策問題，對于任一給定的工程而言，它只有兩種可能，要么上馬，要么不上馬，這兩種情況分別令它對應二進制中的0和1。大凡這樣的實際背景所對應的工程問題，大都可以考慮用0—1規劃建立其相應的模型。

因為每一年的投資不能超過所能提供的資金18千元，因此該0—1規劃的約束條件為

由于期望收益盡可能大，所以目標函數為

maxz＝20x1＋40x2＋20x3＋30x4

3.2　0—1規劃的求解

由于0—1規劃的決策變量只取0、1兩個值，除了能用一般整數規劃的求解方法，例如分支定界法來求解之外，還有其特殊的解法。下面介紹求解0—1規劃的完全枚舉法和隱枚舉法。

3.2.1　完全枚舉法

解0—1規劃時，一種最自然的思路是檢查變量的每一個取值，比較目標函數值的大小，以求得最優解。這種方法稱為完全枚舉法。

例3-3-2　用完全枚舉法求解下列0—1規劃問題。

（x1，x2，x3）共有8種不同的組合，把各種組合下目標函數和約束條件左端的值列入表3-3-2中。

由表可知，該問題的可行解為（0，0，0）、（0，0，1）、（0，1，0）、（1，0，0）、（1，0，1），最優解為（1，0，1），最優值為8。

3.2.2　隱枚舉法

枚舉法可以解決一些0—1規劃問題，可是當變量個數比較多的時候，枚舉法的計算量明顯增大。這時，我們需要找到一種方法，只檢查變量取值的部分組合，就能求得問題的最優解。這種方法稱為隱枚舉法。

用隱枚舉法來求解例3-3-2。

解：先用試探的方法，找到一個滿足所有約束條件的解，如（0，0，1），算出其z值等于5。也就是說，要求的最優值一定不會小于5。所以，可以增加一個約束條件3x1-2x2＋5x3≥5，凡是目標函數值小于5的組合不必討論，這時就得到了一個更簡單的表3-3-3。

從表3-3-3可以看出，最優解為（1，0，1），最優值為8。隱枚舉法是對枚舉法的一種簡化，而這兩種方法的主導思想是趨于一致的。