孟香惠,施保昌,胡新生

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

1.引言

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

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

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

考慮如下標準線性規(guī)劃問題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證(i) 顯然.

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

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

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

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

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

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

圖3.1 問題3.1的松弛問題的可行域、頂點及目標函數(shù)等值線

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

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

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

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

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

圖3.2 問題3.3的松弛問題的可行域、頂點及目標函數(shù)等值線

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

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