高太平,劉桂枝,劉宏英

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

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

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

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

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

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

0 引言

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

1 預(yù)備知識(shí)

1.1 基本概念

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為

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

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

文中未定義的記號(hào)和術(shù)語(yǔ)請(qǐng)參見(jiàn)文獻(xiàn)[8].

1.2 幾個(gè)引理

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

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

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

引理3[8]若(LP)的可行域D有界,則(LP)的目標(biāo)函數(shù)一定在D的某些頂點(diǎn)上達(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)的一個(gè)最優(yōu)基,對(duì)應(yīng)的基最優(yōu)解為X.若存在k∈{1,2,…n}{j1,j2,…,jm},使得判別數(shù)σk=cBB-1Ak-ck=0,則取xk為進(jìn)基變量進(jìn)行換基迭代,可得另一基最優(yōu)解￣X.

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

設(shè)整數(shù)線性規(guī)劃的標(biāo)準(zhǔn)型為

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

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

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

綜合①-③,我們有

命題得證.

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

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

4 實(shí)例

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

[3] 陳鋒,邢文訓(xùn).超尺寸物品裝箱問(wèn)題[J].運(yùn)籌學(xué)學(xué)報(bào),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] 唐國(guó)春.現(xiàn)代物流技術(shù)中裝卸工問(wèn)題的擬多項(xiàng)式時(shí)間可解情況[J].運(yùn)籌與管理,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ó)華,王芬.線性規(guī)劃[M].北京:高等教育出版社,1990.

[9] 陳開(kāi)周.最優(yōu)化計(jì)算方法[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

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

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