對(duì)改進(jìn)隱枚舉法的思考

程紅萍，趙銀鋒

(1. 西安歐亞學(xué)院 數(shù)學(xué)教研室，陜西 西安 710065；2. 西門子信號(hào)有限公司，陜西 西安 710016)

對(duì)改進(jìn)隱枚舉法的思考

程紅萍1，趙銀鋒2

(1. 西安歐亞學(xué)院 數(shù)學(xué)教研室，陜西 西安 710065；2. 西門子信號(hào)有限公司，陜西 西安 710016)

運(yùn)用對(duì)比分析的研究方法，論證了隱枚舉法在線性規(guī)劃的 0-1整數(shù)規(guī)劃解題的傳統(tǒng)思路上可作改進(jìn)，通過(guò)實(shí)例說(shuō)明改進(jìn)后的方法快捷可行．

0-1整數(shù)規(guī)劃；隱枚舉法；改進(jìn)的隱枚舉法

對(duì)于0-1型整數(shù)規(guī)劃問(wèn)題的一種求解方法，人們最容易想到的是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量(n個(gè))取值的 2n個(gè)組合．對(duì)于變量個(gè)數(shù) n較大(例如 n＞10)時(shí)，這幾乎是不可能的．因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問(wèn)題的最優(yōu)解．這樣的方法稱為隱枚舉法．隱枚舉法作為一種求解 0-1型整數(shù)規(guī)劃問(wèn)題的方法，它的產(chǎn)生極大地推動(dòng)了經(jīng)濟(jì)管理、科學(xué)研究、工程技術(shù)等諸多領(lǐng)域的理論研究和實(shí)踐運(yùn)用發(fā)展．隱枚舉法的基本思路是從所有變量等于零出發(fā)，依次指定一些變量為 1，直到得到一個(gè)可行解，并將它作為目前最好的可行解．此后，依次檢查變量等于0或1的某些組合，以便使目前最好的可行解不斷加以改進(jìn)，最終獲得最優(yōu)解．隱枚舉法不同于窮舉法，它不需要將所有可行的變量組合一一列表．它通過(guò)分析、判斷排除了許多變量組合作為最優(yōu)解的可能性．

但在實(shí)際的運(yùn)用中也常常會(huì)遇到這樣的問(wèn)題，所有變量從零出發(fā)，依次指定一些變量為 1，那么哪些變量取1呢？關(guān)于這方面，曾經(jīng)有人改進(jìn)過(guò)：如果目標(biāo)函數(shù)為最大化，那么先試探讓系數(shù)最大的變量 xj取1，其余變量都取 0；如果目標(biāo)函數(shù)為最小化，那么先試探讓系數(shù)最小的變量 xj取 1，其余變量都取 0；這樣就可以減少運(yùn)算次數(shù)．在教學(xué)與實(shí)踐中本人也做了這方面的嘗試，在嘗試過(guò)程中發(fā)現(xiàn)雖然運(yùn)算次數(shù)比以前少了，但相對(duì)來(lái)說(shuō)，運(yùn)算次數(shù)還是較多．因此，有必要對(duì)隱枚舉法做進(jìn)一步的改進(jìn)．這既是一個(gè)解決實(shí)踐運(yùn)用問(wèn)題的需要，也是一個(gè)急需解決的理論問(wèn)題．本文擬就如何改進(jìn)隱枚舉法做以粗淺的探討．

改進(jìn)隱枚舉法的觀點(diǎn)或設(shè)想：正是因?yàn)殡[枚舉法的第一步是先通過(guò)試探的方法找到一個(gè)可行解的，那么根據(jù)它的這個(gè)特點(diǎn)，對(duì)于目標(biāo)函數(shù)為最大化的，我們?nèi)魪哪繕?biāo)函數(shù)中 xj的系數(shù)為正的變量都取 1而其他變量都取0開(kāi)始試探，就會(huì)發(fā)現(xiàn)下面的運(yùn)算次數(shù)會(huì)大大減少；并且一般只需要幾步就能找到最優(yōu)解；而對(duì)于目標(biāo)函數(shù)為最小化的，我們?nèi)魪哪繕?biāo)函數(shù)中 xj的系數(shù)為負(fù)的變量都取 1而其他變量都取 0開(kāi)始試探，也會(huì)發(fā)現(xiàn)下面的運(yùn)算次數(shù)會(huì)大大減少．

對(duì)于隱枚舉法和改進(jìn)隱枚舉法異同即改進(jìn)隱枚舉法的優(yōu)越性，我們可以通過(guò)對(duì)同一模型的求解來(lái)比較分析論證：

解 1) 運(yùn)用隱枚舉法來(lái)求解

第一步：先通過(guò)試探的方法找一個(gè)可行解，易看出X(0)=(x1,x2,x3)=(1,0,0)滿足約束條件，故為一個(gè)可行解，且相應(yīng)的目標(biāo)函數(shù)值為z0=3．

第二步：因?yàn)槭乔髽O大值問(wèn)題，故求最優(yōu)解時(shí)，當(dāng)然希望z≥3了，于是應(yīng)增加一個(gè)約束條件(稱該條件為過(guò)濾條件)：3x1-2x2+53≥3，從而與原問(wèn)題等價(jià)的新規(guī)劃模型為：

第三步：求解新的規(guī)劃問(wèn)題

3個(gè)變量共有8種可能的組合，我們將這8種組合依次檢驗(yàn)它是否滿足條件(a)～(e)，對(duì)某個(gè)組合，若它不滿足(a )，即不滿足過(guò)濾條件，則(b)～(e)即可行性條件不必再檢驗(yàn)；若它滿足(a)～(e)且相應(yīng)的目標(biāo)值嚴(yán)格大于3，則進(jìn)行第四步．

第四步：改進(jìn)過(guò)濾條件直到找到最優(yōu)解．

按上述思路與方法，例1的求解過(guò)程可由表1來(lái)表示：

從而得最優(yōu)解X*=(x1,x2,x3)=(1,0,1)，最優(yōu)值z(mì)*=8．

2) 運(yùn)用改進(jìn)的隱枚舉法來(lái)求解

我們?nèi)砸陨鲜?-1規(guī)劃模型為例來(lái)說(shuō)明改進(jìn)的隱枚舉法求解的簡(jiǎn)便性．

第一步：因?yàn)槟繕?biāo)函數(shù)中x1、x2的系數(shù)都大于零，因此先找一個(gè)可行解X(0)=(x,x,x)=(1,0,1)，此時(shí)z0=8．

第二步：增加一個(gè)約束條件：3x1-2x2+53≥8，從而原問(wèn)題等價(jià)于

表1 改進(jìn)前的判斷過(guò)程

第三步：求解新的規(guī)劃問(wèn)題(和前面的第三步相同)

第四步：改進(jìn)過(guò)濾條件直到找到最優(yōu)解．

按上述思路與方法，例1的求解過(guò)程可由表2表示．

至此，z值已不能再改進(jìn)．即得最優(yōu)解：maxz=8,x*=（x1,x2,x3）=（1,0,1）．

比較表 1與表 2，顯然表 2的計(jì)算判斷次數(shù)明顯少于表1的計(jì)算判斷次數(shù)，表2總共只計(jì)算判斷了12次．而表1總共要計(jì)算判斷24次．

通過(guò)實(shí)例分析比較，我們可以得出這樣一個(gè)結(jié)論：隱枚舉法和改進(jìn)的隱枚舉法在對(duì)同一個(gè)問(wèn)題的求解中，解的結(jié)果是完全相同的．但是，改進(jìn)的隱枚舉法在實(shí)際運(yùn)用中卻凸現(xiàn)了比隱枚舉法更加方便快捷的優(yōu)越性，表現(xiàn)在：對(duì)隱枚舉法的第一步進(jìn)行改進(jìn)，即對(duì)于目標(biāo)函數(shù)為最大(小)化的，我們?nèi)魪哪繕?biāo)函數(shù)中xj的系數(shù)為正(負(fù))的變量都取 1而其他變量都取 0開(kāi)始試探，就會(huì)發(fā)現(xiàn)下面步驟的運(yùn)算次數(shù)會(huì)大大減少，本文例 1使用了2種方法進(jìn)行求解，大家明顯可以看到使用改進(jìn)的隱枚舉法求解時(shí)確實(shí)大大地減少了運(yùn)算次數(shù)，并且在運(yùn)算次數(shù)大大減少的同時(shí)，還提高了運(yùn)算的精確度．也體現(xiàn)了這種方法在推動(dòng)實(shí)際工作實(shí)踐中的有效性．

表2 改進(jìn)后的判斷過(guò)程

Abstract:This paper, from a perspective of contrastive analysis, has researched into the improvement of the Implicit Enumeration Method in applying the 0-1 Integer Programming in the Linear Programming. Practical examples have proved that the improved method is faster and feasible.

Key words:the 0-1 Integer Programming; the Implicit Enumeration Method; the improved enumeration

(責(zé)任編校：李建明英文校對(duì)：李玉玲)

Reflections on Improving the Implicit Enumeration Method

CHENG Hong-ping1; ZHAO Yin-feng2

(1. Teaching Office of Mathematics, Xi’an Eurasia University, Xi’an, Shaanxi 710065, China;
2. Siemens Signaling Company Ltd. Xi’an, Shaanxi 710016, China)

O22

A

1673-2065(2011)01-0014-03

2010-08-15

程紅萍(1971-),女,陜西大荔人,西安歐亞學(xué)院數(shù)學(xué)教研室講師,理學(xué)碩士;

趙銀鋒(1974-),男,陜西大荔人,西門子信號(hào)有限公司工程師.