線性規(guī)劃標(biāo)準(zhǔn)型和整數(shù)線性規(guī)劃最優(yōu)解的兩個(gè)注記

孟香惠,施保昌,胡新生

(1.深圳廣播電視大學(xué)學(xué)習(xí)中心,廣東 深圳518001;2.華中科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖北 武漢430074;3.深圳廣播電視大學(xué)教育技術(shù)中心,廣東 深圳518001)

1.引言

線性規(guī)劃是運(yùn)籌學(xué)、決策科學(xué)和管理科學(xué)最重要的基礎(chǔ),現(xiàn)已成為人們合理利用、調(diào)配有限資源做出最佳決策的有力工具[1?3].除了生產(chǎn)計(jì)劃安排和運(yùn)輸問(wèn)題等經(jīng)典的應(yīng)用領(lǐng)域,因其算法簡(jiǎn)單、高效,適于處理大規(guī)?？茖W(xué)與工程問(wèn)題,線性規(guī)劃還在現(xiàn)今的機(jī)器學(xué)習(xí)等熱點(diǎn)研究領(lǐng)域發(fā)揮著重要作用[4?5].線性規(guī)劃的基本算法: 單純形法可以被看成是線性方程組的消去法的變形或推廣形式,它以其簡(jiǎn)單、通用及應(yīng)用廣泛等特性而著稱于世.在線性規(guī)劃的實(shí)際應(yīng)用中,如生產(chǎn)計(jì)劃安排、物資運(yùn)輸與調(diào)度、工作指派等對(duì)應(yīng)的線性規(guī)劃問(wèn)題中,其所涉及的全部或部分決策變量往往有整數(shù)性的要求,這就得到了所謂整數(shù)線性規(guī)劃問(wèn)題[6?7].整數(shù)性要求使得常用的解析方法不便用于整數(shù)規(guī)劃問(wèn)題,因而整數(shù)規(guī)劃的分析和求解更為困難[6].結(jié)合松弛法的思想,單純形法和對(duì)偶單純形法等線性規(guī)劃算法可以用于變量有整數(shù)性要求的整數(shù)線性規(guī)劃問(wèn)題,從而進(jìn)一步擴(kuò)展了線性規(guī)劃的應(yīng)用范圍.

我們知道,單純形法是基于線性規(guī)劃標(biāo)準(zhǔn)型的.通常,在有關(guān)線性規(guī)劃的教科書和參考文獻(xiàn)里介紹標(biāo)準(zhǔn)型時(shí),都會(huì)“不失一般性”地對(duì)其作些假設(shè),如“約束系數(shù)矩陣行滿秩”.另外,談到整數(shù)線性規(guī)劃時(shí),又會(huì)說(shuō),其最優(yōu)解一般不能通過(guò)對(duì)松弛問(wèn)題的最優(yōu)解進(jìn)行“圓整”而得到.仔細(xì)考量,人們會(huì)提出這樣的問(wèn)題: 無(wú)約束和僅有非負(fù)約束的線性規(guī)劃問(wèn)題分別有怎樣的性質(zhì)? 整數(shù)線性規(guī)劃的松弛問(wèn)題的最優(yōu)解與原整數(shù)線性規(guī)劃的最優(yōu)解相距遠(yuǎn)嗎? 這些問(wèn)題的解答對(duì)學(xué)習(xí)、理解和掌握線性規(guī)劃理論和方法很有意義,然而,教科書中并沒有對(duì)這些問(wèn)題給出清晰或明確的解答.本文通過(guò)線性規(guī)劃標(biāo)準(zhǔn)型的假設(shè)和整數(shù)線性規(guī)劃最優(yōu)解的兩個(gè)注記,對(duì)這些問(wèn)題給出作者的見解.文中研究了線性規(guī)劃標(biāo)準(zhǔn)型的基本假設(shè)所蘊(yùn)含的一些性質(zhì),并探討了整數(shù)線性規(guī)劃最優(yōu)解和其松弛問(wèn)題最優(yōu)解的關(guān)系,所得結(jié)果有助于理解和掌握線性規(guī)劃的基本理論和方法.

2.關(guān)于線性規(guī)劃標(biāo)準(zhǔn)型的假設(shè)的注記

考慮如下標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題：

其中A=(p1,p2,··· ,pn)∈Rm×n,b ∈Rm,c,x ∈Rn.

不失一般性，教科書里大都作如下假設(shè)：

(H1) (i) Rank(A) =m

實(shí)際上,除這一基本假設(shè)外,還有另外一些隱含假設(shè)在教科書里往往沒有提及,如：

(H2)m>0;pj≠0,?j:1≤j ≤n.

m=0 對(duì)應(yīng)于僅有非負(fù)約束的情形;而當(dāng)pj=0 時(shí),變量xj不會(huì)出現(xiàn)在等式約束中,故其僅有非負(fù)的限制.這兩種情形有一定的聯(lián)系.另外,還可考慮類似的問(wèn)題: 無(wú)約束和僅有等式約束的情形,這兩種情況有內(nèi)在聯(lián)系,文獻(xiàn)中也鮮有提及.下面就這四種情況分述之.

1) 無(wú)約束線性規(guī)劃問(wèn)題：X=Rn.

結(jié)論2.1(i) 若c=0，則任意x ∈Rn均為問(wèn)題(2.1)的最優(yōu)解；

(ii) 若c≠0，則問(wèn)題(2.1)有無(wú)界解(無(wú)最優(yōu)解).

證 (i) 結(jié)論顯然成立.(ii) 若c≠ 0，取=θc,θ >0，則有cT=θ‖c‖2→+∞(θ →+∞),故問(wèn)題(2.1) 有無(wú)界解.證畢.

注2.1若c≠ 0,取=?θc,θ >0,還可得出cT=?θ‖c‖2→?∞(θ →+∞),所以,問(wèn)題(2.1)的目標(biāo)函數(shù)亦無(wú)下界.從幾何上看,若c≠0,則目標(biāo)函數(shù)z=cTx的等值面在Rn空間中可以沿著c或?c的方向任意移動(dòng),因而函數(shù)值既無(wú)上界,也無(wú)下界.

2) 僅有非負(fù)約束的線性規(guī)劃問(wèn)題：X={x ∈Rn|x ≥0}.

結(jié)論2.2(i) 若c ≤0,則x=0 為問(wèn)題(2.1)的最優(yōu)解；

(ii) 若存在cl >0,則問(wèn)題(2.1)有無(wú)界解.

證(i) 顯然,cTx ≤cT0 = 0,?x ≥0,故x= 0 為問(wèn)題(2.1)的最優(yōu)解；(ii)不妨設(shè)c1>0,取=(θ,0,··· ,0)T,θ >0,則有cT=θc1→+∞(θ →+∞),故問(wèn)題(2.1) 有無(wú)界解.證畢.

3) 僅有等式約束的線性規(guī)劃問(wèn)題：X={x ∈Rn|Ax=b}.

不妨設(shè)Rank(A) =m

于是,由結(jié)論(2.1)有

結(jié)論2.3(i) 若σN=0，則任意xN ∈Rn?m均為問(wèn)題(2.2)的最優(yōu)解,即Ax=b的任意解均為問(wèn)題(2.1)的最優(yōu)解；

(ii) 若σN≠0，則問(wèn)題(2.2)有無(wú)界解,從而問(wèn)題(2.1)有無(wú)界解.

4) 問(wèn)題(2.1)的系數(shù)矩陣?yán)?存在j,使得pj=0(1≤j ≤n)的情形.

不妨設(shè)pn=0,則問(wèn)題(2.1)變?yōu)椋?/p>

結(jié)論2.4(i) 若=?,則問(wèn)題(2.1)無(wú)可行解；

(a) 若cn >0,則問(wèn)題(2.1)有無(wú)界解；

(b) 若cn ≤0,則問(wèn)題(2.1)化為如下降維(n ?1維)問(wèn)題：

證(i) 顯然.

因此,x?= (,0)∈X為問(wèn)題(2.1)的最優(yōu)解.若問(wèn)題(2.4)有無(wú)界解，則由從而推知問(wèn)題(2.1)亦有無(wú)界解.證畢.

3.關(guān)于整數(shù)線性規(guī)劃最優(yōu)解的注記

變量的“離散”特性使得整數(shù)(線性)規(guī)劃的分析和求解無(wú)法直接運(yùn)用解析方法.事實(shí)上,整數(shù)規(guī)劃往往還會(huì)呈現(xiàn)出高度的非線性性：假設(shè)某個(gè)變量x取值為a1,a2,··· ,am，則等價(jià)于(x ?a1)(x ?a2)···(x ?am) = 0.這是一個(gè)由m階多項(xiàng)式構(gòu)成的非線性等式約束,m越大，其非線性程度越高.

松弛方法是求解整數(shù)規(guī)劃的基本方法之一,其主要思想是通過(guò)求解移除整數(shù)性要求的“松弛”問(wèn)題,然后利用最優(yōu)解的信息,縮小松弛問(wèn)題的可行域,但又不丟失原問(wèn)題的整數(shù)可行解.逐步施行這一過(guò)程,直到某一個(gè)松弛問(wèn)題的最優(yōu)解滿足整數(shù)性要求,從而得到原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解.實(shí)際求解時(shí),一般采用數(shù)值計(jì)算.源于數(shù)值誤差的影響,或?qū)嶋H計(jì)算的需要,自然會(huì)提出這樣的問(wèn)題：是否可以通過(guò)對(duì)松弛問(wèn)題的最優(yōu)解進(jìn)行“圓整”得到整數(shù)規(guī)劃的近似最優(yōu)解? 換句話說(shuō),整數(shù)規(guī)劃的(近似)最優(yōu)解是否在松弛問(wèn)題的最優(yōu)解附近？這也是在講授整數(shù)規(guī)劃時(shí)會(huì)常常提及的問(wèn)題.

這一問(wèn)題的答案是否定的！一般地,教科書上說(shuō)：松弛問(wèn)題的最優(yōu)解化整后不一定是整數(shù)規(guī)劃的可行解,或雖是可行解,但不一定是最優(yōu)解,并可舉例說(shuō)明[1].松弛問(wèn)題的最優(yōu)解化整后是不是可以得到整數(shù)規(guī)劃的近似最優(yōu)解? 尚未見教科書上討論過(guò)這一問(wèn)題.事實(shí)上,可以構(gòu)造出這樣的例子,松弛最優(yōu)解或化整后的解可以遠(yuǎn)離整數(shù)規(guī)劃的最優(yōu)解! 例3.1是我們構(gòu)造出來(lái)的一族二維例子.其構(gòu)造過(guò)程如下：

在第一象限,先做一個(gè)由兩個(gè)不等式約束構(gòu)成的“狹長(zhǎng)”的可行域X,目的是讓整數(shù)最優(yōu)解和松弛最優(yōu)解分別位于X中的兩側(cè),即盡量“遠(yuǎn)離”.如圖3.1所示,讓Q3(7.5,2.5)為松弛最優(yōu)解,而讓Q?(1,3)為整數(shù)最優(yōu)解.這時(shí),可以讓第一個(gè)約束通過(guò)Q3,并且在Q?和(2,3)之間穿過(guò),通過(guò)點(diǎn)Q1(0,3+ε).由Q?和Q1確定出第一個(gè)不等式約束.再由Q?可行,而(2,3)不可行,定出1/13≤ε<2/11.第二個(gè)不等式由通過(guò)Q3及x1軸正向的直線構(gòu)成,并與第一個(gè)約束在第一象限構(gòu)成凸多邊形即可,這里選擇x1+x2≤10.最后,為使Q3(7.5,2.5)和Q?(1,3)分別為松弛最優(yōu)解和整數(shù)最優(yōu)解,由圖解法,讓目標(biāo)函數(shù)的梯度c(系數(shù)向量)與第一個(gè)約束的外法矢量接近平行(見圖3.1),使得Q?(1,3)是通過(guò)Q3的目標(biāo)函數(shù)等值線沿著目標(biāo)函數(shù)的負(fù)梯度方向?c移動(dòng)時(shí)碰到的第一個(gè)整數(shù)可行點(diǎn),即所求整數(shù)規(guī)劃的最優(yōu)解.于是得到z= (2+λ)x1+25x2,并且λ>(10ε ?1)/3.最終,得到例3.1.

圖3.1 問(wèn)題3.1的松弛問(wèn)題的可行域、頂點(diǎn)及目標(biāo)函數(shù)等值線

例3.1整數(shù)規(guī)劃的最優(yōu)解與其松弛問(wèn)題的最優(yōu)解“相距甚遠(yuǎn)”的例子.

其中λ>(10ε ?1)/3,1/13≤ε<2/11.

由上述討論知,例3.1的松弛問(wèn)題(即不考慮整數(shù)性要求)的最優(yōu)解為Q3(7.5,2.5),而例3.1(整數(shù)規(guī)劃)的最優(yōu)解為Q?(1,3),它們的距離為√可謂相距甚遠(yuǎn).而對(duì)松弛最優(yōu)解為Q3(7.5,2.5)圓整得到其附近的整數(shù)點(diǎn)(7,2),(8,2),(7,3)和(8,3),前兩個(gè)是例3.1的可行解,后兩個(gè)則不可行.它們都“遠(yuǎn)離”最優(yōu)解Q?(1,3).為了能讓讀者看到具體的例子,特別地,在例3.1中取一組特定的參數(shù),得到例3.2.

例3.2例3.1的特例(λ=1,ε=0.1).

利用以上方法,我們還可以構(gòu)造出松弛最優(yōu)解與整數(shù)最優(yōu)解相距更遠(yuǎn)的例子.例3.3是例3.1的擴(kuò)展,其中d為正整數(shù).與例3.1類似,讓Q3(d+0.5,2.5)為松弛最優(yōu)解,而讓Q?(1,3)仍為整數(shù)最優(yōu)解(參見圖3.2).此時(shí),它們的距離為√由此可見,當(dāng)d充分大時(shí),Q3與Q?的距離充分遠(yuǎn)! 讀者可以在例3.3中取具體的參數(shù),得到所需的具體例子.

圖3.2 問(wèn)題3.3的松弛問(wèn)題的可行域、頂點(diǎn)及目標(biāo)函數(shù)等值線

例3.3例3.1的擴(kuò)展(d>2).

其中1/(2d ?1)≤ε<2/(2d ?3),0<ε′ ?1.