對改進隱枚舉法的思考

程紅萍，趙銀鋒

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

對改進隱枚舉法的思考

程紅萍1，趙銀鋒2

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

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

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

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

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

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

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

解 1) 運用隱枚舉法來求解

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

第二步：因為是求極大值問題，故求最優(yōu)解時，當然希望z≥3了，于是應增加一個約束條件(稱該條件為過濾條件)：3x1-2x2+53≥3，從而與原問題等價的新規(guī)劃模型為：

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

3個變量共有8種可能的組合，我們將這8種組合依次檢驗它是否滿足條件(a)～(e)，對某個組合，若它不滿足(a )，即不滿足過濾條件，則(b)～(e)即可行性條件不必再檢驗；若它滿足(a)～(e)且相應的目標值嚴格大于3，則進行第四步．

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

按上述思路與方法，例1的求解過程可由表1來表示：

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

2) 運用改進的隱枚舉法來求解

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

第一步：因為目標函數(shù)中x1、x2的系數(shù)都大于零，因此先找一個可行解X(0)=(x,x,x)=(1,0,1)，此時z0=8．

第二步：增加一個約束條件：3x1-2x2+53≥8，從而原問題等價于

表1 改進前的判斷過程

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

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

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

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

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

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

表2 改進后的判斷過程

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

(責任編校：李建明英文校對：李玉玲)

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-),女,陜西大荔人,西安歐亞學院數(shù)學教研室講師,理學碩士;

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