高太平,劉桂枝,劉宏英

(1.山西大學(xué)計算機與信息技術(shù)學(xué)院,山西太原 030006;2.計算智能與中文信息處理省部共建教育部重點實驗室,山西太原 030006;3.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同 037009;4.山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,山西大同 037009)

＊關(guān)于整數(shù)線性規(guī)劃全部最優(yōu)解的一個注記

高太平1,2,劉桂枝1,3,劉宏英1,4

(1.山西大學(xué)計算機與信息技術(shù)學(xué)院,山西太原 030006;2.計算智能與中文信息處理省部共建教育部重點實驗室,山西太原 030006;3.山西大同大學(xué)物理與電子科學(xué)學(xué)院,山西大同 037009;4.山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,山西大同 037009)

研究在整數(shù)線性規(guī)劃基最優(yōu)解已經(jīng)求出且不唯一的條件下,如何求整數(shù)線性規(guī)劃的全部最優(yōu)解問題.當整數(shù)線性規(guī)劃具有兩個基最優(yōu)解時,文章給出其全部最優(yōu)解的個數(shù)公式及求全部最優(yōu)解的一個有效算法.

整數(shù)線性規(guī)劃;單純形法;最優(yōu)解;算法

0 引言

整數(shù)線性規(guī)劃在許多研究和應(yīng)用領(lǐng)域都起著重要作用,如Job-shop調(diào)度問題[1]、物流最優(yōu)調(diào)度問題[2-3]、指派問題[4-5]、裝載問題[6]等.現(xiàn)實生活中的許多決策問題,往往可以歸結(jié)成整數(shù)線性規(guī)劃問題.因此,整數(shù)線性規(guī)劃求解問題引起了數(shù)學(xué)科學(xué)、管理科學(xué)、決策科學(xué)、系統(tǒng)科學(xué)等領(lǐng)域?qū)＜覍W(xué)者的廣泛興趣.然而由于整數(shù)線性規(guī)劃問題固有的復(fù)雜性和難解性,使其求解不像線性規(guī)劃那么容易.人們已經(jīng)證明整數(shù)線性規(guī)劃的求解問題是NP-難的[7].目前實用可行的方法如分支定界法、割平面法等在大多數(shù)情況下只能求出整數(shù)線性規(guī)劃的一個或很少幾個整數(shù)最優(yōu)解.當整數(shù)線性規(guī)劃的最優(yōu)解不唯一時,如何求其全部最優(yōu)解或更多最優(yōu)解,至今仍沒有一個通用而有效的算法.鑒于此,本文主要針對整數(shù)線性規(guī)劃具有兩個基最優(yōu)解的情況進行研究,給出了其全部最優(yōu)解的個數(shù)公式以及求全部最優(yōu)解的一個有效算法.

1 預(yù)備知識

1.1 基本概念

設(shè)線性規(guī)劃的標準型為

其中,x,c∈Rn,b∈Rm,A為m×n矩陣,A的秩為m(m＜n).滿足約束條件(2)、(3)式的解X=(x1,x2,…,xn)T稱為線性規(guī)劃問題(LP)的可行解,全體可行解組成的集合稱為(LP)的可行域,其中使目標函數(shù)達到最小值的可行解稱為(LP)的最優(yōu)解.若B=(Aj1,A j2,…,A jm)是矩陣A中m×m階非奇異子陣(|B|≠0),則稱B是線性規(guī)劃(LP)的一個基,xj1,xj2,…,xjm稱為關(guān)于基B的基變量,其余變量稱為關(guān)于基B的非基變量.非基變量全取0時,(2)式的解稱為(LP)的基解,滿足非負條件(3)的基解稱為(LP)的基可行解,使目標函數(shù)取得最小值的基可行解稱為基最優(yōu)解.

設(shè)K是n維歐氏空間的一個點集,若任意兩點X(1)∈K,X(2)∈K的連線上的所有點λX(1)+(1-λ)X(2)∈K(0≤λ≤1),則稱K為凸集.

文中未定義的記號和術(shù)語請參見文獻[8].

1.2 幾個引理

為了討論整數(shù)線性規(guī)劃的全部最優(yōu)解,我們需要下面幾個定理.

引理1[8]若線性規(guī)劃問題存在可行解,則其可行域D={X|A X=b,X≥0}是凸集.

引理2[8]X為(LP)的基可行解的充分必要條件為:X為(LP)的可行域D的頂點.

引理3[8]若(LP)的可行域D有界,則(LP)的目標函數(shù)一定在D的某些頂點上達到最優(yōu).

引理4[8]若(LP)的可行域有界,且全部基最優(yōu)解為X(1),X(2),…,X(k),則(LP)的任一最優(yōu)解可表示為

引理5[9]設(shè)B=(A j1,Aj2,…,Ajm)是(LP)的一個最優(yōu)基,對應(yīng)的基最優(yōu)解為X.若存在k∈{1,2,…n}{j1,j2,…,jm},使得判別數(shù)σk=cBB-1Ak-ck=0,則取xk為進基變量進行換基迭代,可得另一基最優(yōu)解￣X.

2 具有兩個基最優(yōu)解的整數(shù)線性規(guī)劃全部最優(yōu)解的個數(shù)

設(shè)整數(shù)線性規(guī)劃的標準型為

①取rl=0時,由歸納假設(shè)2)知,λ有f(k1,k2,…,kl-1)-2種取法;

②取ri=0,i=1,2,…,l-1時,λ有kl種取法;

③取r1r2…rl-1rl≠0時,對每個rl∈{1,2,…,kl},λ有f(k1,k2,…,kl-1)-2種取法.所以,在這種情況下,λ共有(f(k1,k2,…,kl-1)-2)kl種取法.

綜合①-③,我們有

命題得證.

3 具有兩個基最優(yōu)解的(IL P)全部最優(yōu)解的求解算法

設(shè)(ILP)具有兩個基最優(yōu)解X(1),X(2),由上面的討論,結(jié)合定理1和定理2,我們給出求解(ILP)的全部整數(shù)最優(yōu)解的算法如下:

4 實例

求解下列(ILP1)的全部最優(yōu)解

解 利用單純形法,可得到(ILP1)的最優(yōu)單純形表如下(見表1,P8):

表1 (ILP1)的最優(yōu)單純形表Table 1 Optimal Simple Table of(ILP1)

根據(jù)最優(yōu)單純形表1,我們可求得第一個基最優(yōu)解為X(1)=(30,10,0,50,0).由于表1中非基變量x3對應(yīng)的判別數(shù)σ3也為0,所以由引理5可知,(ILP1)還存在另外一個基最優(yōu)解.這時,只要取x3為進基變量,x1為離基變量,再做一次換基迭代,便可以求出另一個基最優(yōu)解為X(2)=(0,40,30,20,0).此時d=30=21×31×51,所以原問題(ILP)的全部整數(shù)最優(yōu)解個數(shù)為f(1,1,1)=(1+1)×(1+1)×(1+1)+1=9.

下面求除X(1),X(2)以外的其余9-2=7個最優(yōu)解.為此,依次取

5 結(jié)束語

本文基于單純形法,在整數(shù)線性規(guī)劃恰有兩個基最優(yōu)解的條件下,給出了求整數(shù)線性規(guī)劃全部最優(yōu)解的一種有效算法.從而可為此類實際問題提供更多的最優(yōu)方案,使得決策者在某些最優(yōu)方案因一些突發(fā)事件不能使用時,可更多地選擇其它最優(yōu)方案.盡管算法是在已知兩個基最優(yōu)解的條件下給出的,但是在整數(shù)線性規(guī)劃具有兩個以上已知(基)最優(yōu)解的情況下(不管得到這些最優(yōu)解是基于單純形法或者分枝定界法,還是其他方法),欲求更多其它最優(yōu)解時,該算法也是有效的.這時,盡管我們不一定能求出全部最優(yōu)解,但只要從這些已知的最優(yōu)解中任意選取兩個,按照上述算法便可求出更多的最優(yōu)解.從實用角度來講,這已經(jīng)足夠了.從理論分析來看,當整數(shù)線性規(guī)劃具有三個或更多基最優(yōu)解時,求其全部最優(yōu)解將變得異常復(fù)雜,甚至是不可能的.因此,本文給出的算法具有一定的理論意義和實用價值.

[1] 李琳,霍佳震.鋼管生產(chǎn)計劃中的多目標柔性Job-shop調(diào)度問題[J].系統(tǒng)工程理論與實踐,2009,29(8):117-126.

[2] 劉蘇慶,曹成鉉,鄭輝文.集裝箱多式聯(lián)運中運貨排程問題的建模研究[J].科學(xué)技術(shù)與工程,2010,10(9):2247-2250.

[3] 陳鋒,邢文訓(xùn).超尺寸物品裝箱問題[J].運籌學(xué)學(xué)報,2002,6(1):85-90.

[4] Bihr R A.A Conceptual Solution to the Aircraft Gate Assignment Problem Using 0-1 Linear Programming[J].Computers and Industry Engineering,1990,19(3):280-284.

[5] Aissi Hassene,Bazgan Cristina,Vanderpooten Daniel.Complexity of the min-max and min-max Regret Assignment Problem s[J].Operations Research Letters,2005,33:634-640.

[6] 唐國春.現(xiàn)代物流技術(shù)中裝卸工問題的擬多項式時間可解情況[J].運籌與管理,2005,14(4):15-18.

[7] Papadimitriou C H,Steiglitz K.Combinato rial Optimization Algorithm s and Complexity[M].Printice-Hall Inc,1982.

[8] 魏國華,王芬.線性規(guī)劃[M].北京:高等教育出版社,1990.

[9] 陳開周.最優(yōu)化計算方法[M].陜西:西北電訊工程學(xué)院出版社,1986.

A Note on All Optimal Solutions of Integer Linear Programming

GAO Tai-ping1,2,L IU Gui-zhi1,3,LIU Hong-ying1,4

(1.School of Computer&Information Technology,Shanxi University,Taiyuan030006,China;2.Key Lab of the Com putation Intelligence and Chinese Information Processing Province Department Altogether Constructs the M inistry of Education,Taiyuan030006,China;3.School of Physics and Electronic Science,Shanxi Datong University,Datong037009,China;4.School of Mathematics and Computer Science,Shanxi Datong University,Datong037009,China)

How to get all optimal solutions of ILP(integer linear programming)was studied if its basic optimal solution is not unique.When the two basics solutions of ILP is gotten,the formula on the number of all optimal solutions and the effective algorithm getting all the optimal solutions for ILP were got.

integer linear programming;simple method;optimal solution;algorithm

O221

A

0253-2395(2011)01-0005-05＊

2010-06-07;

2010-09-23

國家自然科學(xué)基金(60803034);山西省自然科學(xué)基金(2007011043)

高太平(1956-),男,教授,主要研究方向:組合優(yōu)化、算法設(shè)計與分析.E-mail:tpgao@sxu.edu.cn