0-1線性規(guī)劃問題的分類隱數(shù)搜尋

高培旺

（廣西財經(jīng)學(xué)院 數(shù)學(xué)與統(tǒng)計系，廣西 南寧 530003）

0-1線性規(guī)劃問題的分類隱數(shù)搜尋

高培旺

（廣西財經(jīng)學(xué)院 數(shù)學(xué)與統(tǒng)計系，廣西 南寧 530003）

針對0-1線性規(guī)劃問題，提出一種新的分類隱數(shù)搜尋方法. 該算法將所有的0-1整數(shù)點分類，并產(chǎn)生一個描述性的線性方程，由此構(gòu)造了一組非常好的隱數(shù)條件和隱數(shù)準則，這樣可以排除大量不可行解的列舉，大大加快了隱數(shù)搜尋過程，并通過幾個經(jīng)典算例的計算結(jié)果及與Balas算法的計算結(jié)果比較，證實了本算法的高效性.

線性規(guī)劃；整數(shù)規(guī)劃；0-1線性規(guī)劃；隱數(shù)搜尋

考慮如下形式的0-1線性規(guī)劃（0-1 Linear programming，0-1 LP）問題：

1 分類隱數(shù)搜尋算法

將式（2）、（3）的 m個不等式分別相加，還可得2個重要的有效不等式

令 kIL是滿足 k≥ kL的最小整數(shù)， kIU是滿足 k≤ kU的最大整數(shù)，顯然，當 kIL＞ kIU時，問題無可行解；否則，我們將在滿足條件 kIL≤ k ≤kIU的點集中進行隱數(shù)搜尋，在對的隱數(shù)搜尋過程中，如果一個變量被賦予了一個整數(shù)值，我們稱之為被指定；否則，是自由的. 不妨假設(shè)變量 xs1,xs2,…,xst被指定，變量 xst+1,xst+2,…,xsn是自由變量（ t =0意味著沒有任何變量被指定），將不等式（2）、（4）和目標函數(shù)中自由變量的系數(shù)按從小到大的順序排列如下：

綜上所述，可知參數(shù)k的取值滿足式（6）.

這里， ui1,ui2,…, ui,n-t是 st+1,st+2,…,sn的一個置換. 令向量 ui=(ui1,ui2,…,ui,n-t)，表示取值為 1的指定變量的數(shù)量. 當=k時，置所有自由變量為0，或當=k+t-n時，置所有自由變量為1，這個隱數(shù)進程產(chǎn)生中的一個0-1整數(shù)點，無論這個點是可行的，還是不可行的，該隱數(shù)進程在中的搜尋已經(jīng)結(jié)束；如果＜k ，令 r = k -O，繼續(xù)在中進行隱數(shù)搜尋，得下面的隱數(shù)條件 和隱數(shù)準則.

由于 c=(c1,c2,…,cn)T≥0，容易推出一個隱數(shù)進程在中對應(yīng)的目標函數(shù)的下界估值.

定理2 在隱數(shù)過程中，假設(shè)變量 xs1,xs2,… ,xst被指定，變量 xst+1,xst+2,…,xsn是自由的. 則對于（0-1 LP）在中的可行解，目標函數(shù) f的取值滿足

通過式（6）、（7）可以排除更多的不可行解，其效力可在下面例 3中充分體現(xiàn). 由隱數(shù)條件式（7）即可得下面的隱數(shù)準則.

根據(jù)約束條件式（2）、（4），很容易推出下面 2個隱數(shù)準則，它們是我們確定下一個指定變量的重要依據(jù).

定理3 在隱數(shù)過程中，假設(shè)變量 xs1,xs2,… ,xst被指定，變量 xst+1,xst+2,…,xsn是自由的. 如果存在至少一個 i∈ {1 ,2,… ,m+1}，使得

定理4 在隱數(shù)過程中，假設(shè)變量 xs1,xs2,… ,xst被指定，變量 xst+1,xst+2,…,xsn是自由的. 如果存在至少一個 i∈ {1 ,2,… ,m+1}，使得

根據(jù)定理3、4，若一個自由變量在式（2）、（4）中的系數(shù)滿足條件式（9）或式（10），則該自由變量可以唯一被指定；否則，需要在0和1之間交替列舉，此時，選擇指標 st+1= um+2,1，然后取 xst+1作為下一個指定變量.

根據(jù)上述隱數(shù)算法理論，（0-1 LP）的算法步驟可以描述如下：

步驟3 將自由變量在約束條件式（2）、（4）和目標函數(shù)中的系數(shù)按從小到大的順序排列如下：

由于本算法搜尋的點集數(shù)是有限的（最多 n +1個），且每個點集中包含的0-1整數(shù)點的數(shù)量（個）也是有限的，因此，在執(zhí)行上述算法步驟有限次之后，我們或者得到（0-1 LP）的一個最優(yōu)解，或者得到?jīng)]有可行解的事實.

2 數(shù)值計算實例

利用MATLAB V7.1對本文的算法進行編程，在HΛSEE S262C計算機上對Balas的4個經(jīng)典算例[2]進行求解計算，并與Balas的方法進行比較，其中，例1詳細演示了本算法的計算過程.

例1

具體計算過程如表1所示.

表1 例1的隱數(shù)搜尋過程

由表1可見：本算法經(jīng)過8次檢查，就獲得了問題的一個最優(yōu)解 )0,0,1,1,0(=x ，且變量取值都是通過本算法的隱數(shù)準則唯一指定，而Balas算法得到這個最優(yōu)解需花費3次迭代和12次檢查.

例2

由定理1確定參數(shù)k的取值范圍 1 ≤k ≤9，本算法經(jīng)過29次檢查和指定，在 k =4的點集中獲得了該問題的一個最優(yōu)解： x3=x9=1，其它變量為0；而用Balas的算法求解這個問題需要5次迭代和29次檢查.

例3

例4

由定理1確定參數(shù)k的取值范圍 1 ≤k ≤6，經(jīng)過118次檢查和指定，本算法在點集的第9個隱數(shù)搜尋進程中，產(chǎn)生了問題的一個最優(yōu)解： x3=x4=x8=x10=x12=1，其它變量為 0，而用 Balas的算法求解這個問題需要39次迭代和210多次檢查.

3 結(jié)語

本算法通過對所有的0-1整數(shù)點分類，產(chǎn)生了非常好的隱數(shù)條件和隱數(shù)準則，再加上列舉實例是選取具有最小系數(shù)的自由變量，由此可以排除大量不可行解的搜尋，說明本算法是優(yōu)越的；另外，通過對4個經(jīng)典算例的計算求解，并與Balas算法的比較，也證實了本算法的高效和實用價值；更有意義的是：本算法可以在某些分類點集中求問題的局部最優(yōu)解或可行解，然后作為其他方法的一種預(yù)處理程序來使用；當然本算法還需要更多算例的進一步檢驗.

[1] 柴山. 一類0-1規(guī)劃問題的定界組合算法及其在離散變量結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J]. 工程力學(xué)，1995, 12(1): 81-90.

[2] BALAS E. An addition algorithm for solving linear programs with zero-one variables[J]. Operations Research, 1965, 13(4): 517-546.

[3] BOWMAN V J, STARR J H. Partial orderings in implicit enumeration[J]. Annals of Discrete Mathematics, 1977, 1(1): 99-116.

[4] CROWDER H, JOHNSON E L. Solving large-scale zero-one linear programming problems [J]. Operations Research, 1983, 31(5): 803-834.

[5] DANTCHEV S. Improved sorting-based procedure for integer programming[J]. Mathematical Programming (A), 2002, 92(2): 297-300.

[6] PARIJA G, GADIDOV R, WILHELM W. A facet generation procedure for solving 0-1 integer programming[J]. Operations Research, 1999, 47 (5): 789-791.

[7] BLAIR C. Two rules for deducing valid inequalities for 0-1 problems[J]. SIAM Journal on Applied Mathematics, 1976, 31(4): 614-617.

Sorting-based Implicit Enumerative Search for Zero-one Linear Problems

GAO Pei-wang
（Department of Mathematics and Statistics, Guangxi University of Finance and Economics,
Nanning 530003, China）

This paper presents a new sorting-based implicit enumeration search approach for 0-1 linear programming problems. In the approach, a descriptive linear equation with the sorting of all 0-1 integral points is used to make a series of excellent implicit enumerative conditions and rules. So a large number of 0-1 infeasible points can be excluded from further consideration by the conditions and rules so as to quicken the enumeration search process. The computational test on some classical numerical examples shows that, compared with the Balas’ method, the algorithm is efficient.

linear programming; integer programming; 0-1 linear programming; implicit enumerative search

1006-7302（2010）04-0017-07

O221.4

A

2010-04-07

廣西自然科學(xué)基金資助項目（桂科自0728260）

高培旺（1964—），男，教授，博士，研究方向：最優(yōu)化理論及其應(yīng)用，E-mail: pwgao@yahoo.cn.

孫建平]