吳振華 貴文龍 智國(guó)建

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

1 引言

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

2 目標(biāo)函數(shù)求max的0-1規(guī)劃問(wèn)題求解

[例1] 求以下0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解？

求解步驟[2]：

（1）尋找目標(biāo)函數(shù)值下界。可以判斷，當(dāng)可行解X = (0,1, 0)T時(shí)，該問(wèn)題的目標(biāo)函數(shù)值（－2）最小，因此可以確定目標(biāo)函數(shù)值下界，即3x1-2x2+ 5x3≥－2。

（2）構(gòu)造過(guò)濾約束，并將其加入到原約束條件中。

因函數(shù)函數(shù)值大于等于“－2”，因此可能是0[X =(0, 0,0)T）]、3[X =(1,0,0)T）]和 5[X =(0,0,1)T）]等，可先構(gòu)造過(guò)濾約束“3x1-2x2+ 5x3≥0”，則原模型變?yōu)椋?/p>

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

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

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

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

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

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

當(dāng)然，對(duì)于本題如果構(gòu)造過(guò)濾約束“3x1-2x2+ 5x3≥ 8”[X =(1,0,1)T]，求解過(guò)程將更加快捷。因此，在求解目標(biāo)函數(shù)求最大值的“0-1整數(shù)規(guī)劃問(wèn)題”時(shí)，為使求解過(guò)程更加簡(jiǎn)捷，應(yīng)在多個(gè)過(guò)濾約束中選取右端常數(shù)較大的過(guò)濾約束，過(guò)濾約束右端項(xiàng)越大求解越方便。

常見(jiàn)求解錯(cuò)誤舉例：

[例2] 求以下0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解？[3]

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

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

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

3 目標(biāo)函數(shù)求min的“0-1整數(shù)規(guī)劃問(wèn)題”

對(duì)于目標(biāo)函數(shù)求最小值的“0-1整數(shù)規(guī)劃問(wèn)題”，求解步驟與求最大值時(shí)有所區(qū)別，應(yīng)首先尋找目標(biāo)函數(shù)值上界，其它步驟則與求最大值相同。主要技巧是：在可能構(gòu)造的多個(gè)過(guò)濾約束中選取右端常數(shù)較小的過(guò)濾約束，過(guò)濾約束右端項(xiàng)越小求解越方便。

[例3] 求以下0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解？[4]

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

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

4 教學(xué)體會(huì)

對(duì)于決策變量較少（如不超過(guò)4個(gè)）的“0-1整數(shù)規(guī)劃問(wèn)題”來(lái)說(shuō)，隱枚舉法是比較有效的求解方法，其中“隱”字的含義是通過(guò)構(gòu)造過(guò)濾約束排除不可能成為最優(yōu)解的解組合，減少求解過(guò)程，快速得到最優(yōu)解。在使用該方法的時(shí)候，需要注意以下三點(diǎn)：首先，判斷目標(biāo)函數(shù)“求最大值”還是“求最小值”，以此確定求解順序是從Z值“最大”還是“最小”開(kāi)始；其次，辨別所構(gòu)造的過(guò)濾約束是否滿足原模型的約束條件；最后，應(yīng)按“二進(jìn)制”順序?qū)懗鏊薪饨M合，避免遺漏。在初學(xué)時(shí)，學(xué)生可選擇兩道典型習(xí)題（目標(biāo)函數(shù)求“最大和最小”）進(jìn)行反復(fù)練習(xí)，以掌握隱枚舉法的求解思路和技巧。

[1] 王耀輝,陳超,孫鵬.0-1整數(shù)規(guī)劃及隱枚舉法在學(xué)生面試問(wèn)題中的應(yīng)用[J].中國(guó)科教創(chuàng)新導(dǎo)刊,2011,(22):89.

[2] 常大勇.運(yùn)籌學(xué)[M].北京:中國(guó)物資出版社,2010.

[3] 謝家平.管理運(yùn)籌學(xué)[M].北京:中國(guó)人民大學(xué)出版社, 2010.

[4] 熊偉.運(yùn)籌學(xué)[M].機(jī)械工業(yè)出版社,2005.