談隱枚舉法中過濾約束的使用與解題技巧

吳振華 貴文龍 智國建

（桂林電子科技大學商學院，廣西 桂林 540114）

1 引言

在整數規劃中，隱枚舉法（Implicit enumeration algorithm）是用于求解“0-1整數規劃問題”的常見方法，其基本思想是通過增加“過濾約束”舍棄一定不最優解的解組合以求得最優解[1]。在教學過程中發現，許多學生存在這樣的疑問：過濾約束應如何添加？作用何在？為此，本文通過實例闡述隱枚舉法的求解步驟、過濾約束的作用及“隱”字的含義，幫助學生更好地掌握隱枚舉法。

2 目標函數求max的0-1規劃問題求解

[例1] 求以下0-1整數規劃問題的最優解？

求解步驟[2]：

（1）尋找目標函數值下界?？梢耘袛?，當可行解X = (0,1, 0)T時，該問題的目標函數值（－2）最小，因此可以確定目標函數值下界，即3x1-2x2+ 5x3≥－2。

（2）構造過濾約束，并將其加入到原約束條件中。

因函數函數值大于等于“－2”，因此可能是0[X =(0, 0,0)T）]、3[X =(1,0,0)T）]和 5[X =(0,0,1)T）]等，可先構造過濾約束“3x1-2x2+ 5x3≥0”，則原模型變為：

（3）寫出所有解組合，比較目標函數值 Z，并檢查是否滿足約束條件和過濾條件，得出最優解。過濾約束為“3x1-2x2+ 5x3≥0”的求解過程如表1所示：

當X =(0,0,0)T時，滿足所有約束條件（包括過濾約束），因此在表中對應位置添入“√”，此時目標函數值Z為“0”。當X =(0,0,1)T時，滿足所有約束條件，因此在表中對應位置添入“√”，此時目標函數值Z為“5”。當X =(0,1,0)T、(0,1,1)T和(1,0,0)T時，Z值分別為“－2”、“3”和“3”，均小于“5”，由于目標函數求最大值，因此無須再去考慮 X是否滿足約束條件。當X =(1,0,1)T時，滿足所有約束條件，因此在表中對應位置添入“√”，此時目標函數值Z為“8”。當X=(1,1,0)T和(1,1,1)T時，Z值分別為“1”和“6”，均小于“8”，因此可求得該問題的最優解為：X*=(1,0,1)T，Z*=8。

可見，添加過濾約束可以加快篩選過程，“隱”去不可能成為最優解的解組合（見表1加粗部分，下同），以簡化求解過程。但需注意，過濾約束一定要選滿足原約束條件。同時，為保證解組合不遺漏，可參照“二進制”的表達方法，將所有解依次列出，本題因有三個變量，故解組合的數量為：23=8，詳見表1。

表1 過濾約束為“3x1 -2x2 + 5x3 ≥ 0”的求解過程

同理，可構造過濾約束“3x1-2x2+ 5x3≥3”[X =(1, 0,0)T]和“3x1-2x2+5x3≥5”[X =(0,0,1)T]，求解過程見表2。

表2 過濾約束為“3x1 -2x2 + 5x3 ≥ 3”和“3x1 -2x2 + 5x3 ≥ 5”的求解過程

當然，對于本題如果構造過濾約束“3x1-2x2+ 5x3≥ 8”[X =(1,0,1)T]，求解過程將更加快捷。因此，在求解目標函數求最大值的“0-1整數規劃問題”時，為使求解過程更加簡捷，應在多個過濾約束中選取右端常數較大的過濾約束，過濾約束右端項越大求解越方便。

常見求解錯誤舉例：

[例2] 求以下0-1整數規劃問題的最優解？[3]

許多學生首先構造過濾約束“4x1+3x2+2x3≥0”[X=(0,0,0)T]，然后按步驟求解，過程如表 3所示，求解結果為：X* =(1,1,1)T，Z*=9。雖然求解結果正確，但卻犯了一個概念性錯誤，即 X =(0,0,0)T并不滿足原模型約束條件（“4x1+x2+3x3≥3”和“x2+x3≥1”），不能作為過濾約束。同時，求解順序是從 Z值最小開始依次判斷，過程較為復雜。說明，學生并沒有掌握隱枚舉法的解題技巧。更好的解法是：構造過濾約束“4x1+3x2+2x3≥9”[X =(1,1,1)T]，按Z值從大到小的順序進行求解，即優先考查 Z值較大的解組合，則很快得到最優，過程見表4所示。

表3 過濾約束為“4x1 + 3x2 + 2x3 ≥ 0”的求解過程

表4 過濾約束為“4x1 + 3x2 + 2x3 ≥ 9”的求解過程

3 目標函數求min的“0-1整數規劃問題”

對于目標函數求最小值的“0-1整數規劃問題”，求解步驟與求最大值時有所區別，應首先尋找目標函數值上界，其它步驟則與求最大值相同。主要技巧是：在可能構造的多個過濾約束中選取右端常數較小的過濾約束，過濾約束右端項越小求解越方便。

[例3] 求以下0-1整數規劃問題的最優解？[4]

對于本題（解組合數量為24= 16），可構造過濾約束“2x1+5x2+3x3+4x4≤4”[ X =( 0,0,0,1)T]，求解過程如表5所示，求解結果：X*=(0,0,0,1)T，Z*=4。

表5 過濾約束為“2x1 + 5x2 + 3x3 +4x4 ≤4”的求解過程

4 教學體會

對于決策變量較少（如不超過4個）的“0-1整數規劃問題”來說，隱枚舉法是比較有效的求解方法，其中“隱”字的含義是通過構造過濾約束排除不可能成為最優解的解組合，減少求解過程，快速得到最優解。在使用該方法的時候，需要注意以下三點：首先，判斷目標函數“求最大值”還是“求最小值”，以此確定求解順序是從Z值“最大”還是“最小”開始；其次，辨別所構造的過濾約束是否滿足原模型的約束條件；最后，應按“二進制”順序寫出所有解組合，避免遺漏。在初學時，學生可選擇兩道典型習題（目標函數求“最大和最小”）進行反復練習，以掌握隱枚舉法的求解思路和技巧。

[1] 王耀輝,陳超,孫鵬.0-1整數規劃及隱枚舉法在學生面試問題中的應用[J].中國科教創新導刊,2011,(22):89.

[2] 常大勇.運籌學[M].北京:中國物資出版社,2010.

[3] 謝家平.管理運籌學[M].北京:中國人民大學出版社, 2010.

[4] 熊偉.運籌學[M].機械工業出版社,2005.