孫秀華

(安徽建筑大學(xué) 數(shù)理系，安徽 合肥 230022)

單純形法作為解決線性規(guī)劃問題的傳統(tǒng)方法，已形成相當(dāng)成熟的理論，并不斷改進(jìn)簡化運(yùn)算。［1，2］近年來，結(jié)合計(jì)算機(jī)并融合數(shù)學(xué)建模可更大程度應(yīng)用運(yùn)籌學(xué)，特別是線性規(guī)劃中的單純形法。［3］而單純形法的原理在于通過迭代不斷尋求新的基本可行解，從而得到最優(yōu)解和目標(biāo)函數(shù)的最優(yōu)值?；究尚薪馐侵府?dāng)非基變量全取0 值時(shí)，基變量取得非負(fù)值而形成的一個(gè)解。此時(shí)的基變量對(duì)應(yīng)的系數(shù)列向量線性無關(guān)，并構(gòu)成線性規(guī)劃標(biāo)準(zhǔn)型中約束方程組系數(shù)矩陣的最高階的非奇異方陣，即這些列向量為約束方程組系數(shù)矩陣所有列向量的最大線性無關(guān)組，稱為線性規(guī)劃問題的基。事實(shí)上，在單純形法中，正是其中的線性無關(guān)性，才可以保證在每一次迭代中都可以求出非基變量的檢驗(yàn)數(shù)并確定新的進(jìn)基變量，進(jìn)而又要保證確定出基變量后的新的基變量組合仍為基本解，即保證新的基變量對(duì)應(yīng)的系數(shù)列向量線性無關(guān)。由此可見，線性無關(guān)性在單純形法中有著非常重要的作用。

1 基變量、非基變量與線性無關(guān)性

設(shè)線性規(guī)劃問題標(biāo)準(zhǔn)型如下:［4］

在此不妨假設(shè)假設(shè)矩陣A 秩為m。

定理1.1［5］設(shè)非齊次線性方程組的系數(shù)矩陣Am×n的秩R(A)= r，則對(duì)應(yīng)的n 元齊次線性方程組AX = 0 的解集S 的秩Rs= n－r。

由上述定理易得如下命題:

命題1.2 xk1，xk2，…，xkm為第k 步迭代中基變量當(dāng)且僅當(dāng)基變量xk1，xk2，…，xkm可由非基變量xkm+1，xkm+2，…，xkn－m表示，即:對(duì)1 i m，有xki= b＇i－(a＇i，m+1xkm+1+ … + a＇i，n－mxkn－m)。

證明:“”如果xk1，xk2，…，xkm為基變量，其對(duì)應(yīng)列向量(pk1pk2… pkm)經(jīng)過初等行變換可化為單位陣，由定理1.1 知xk1，xk2，…，xkm可由自由向量，也即非基變量表示。

“”若對(duì)1 i m，有xki都可以由xkm+1，xkm+2，…，xkn－m表示，則xk1，xk2，…，xkm對(duì)應(yīng)列向量(pk1pk2… pkm)可初等行變換為單位陣，即xk1，xk2，…，xkm為基變量。

2 進(jìn)基變量與線性無關(guān)性

由命題1.2 知正因?yàn)榛兞靠梢杂煞腔兞勘硎荆恳徊降鷷r(shí)都可以將非基變量代入到目標(biāo)函數(shù)中，同時(shí)此時(shí)目標(biāo)函數(shù)中不含基變量，進(jìn)而確定非基變量的檢驗(yàn)數(shù)，并由檢驗(yàn)數(shù)的符號(hào)確定進(jìn)基變量。見下例:

例2.1 用單純形法計(jì)算線性規(guī)劃:

解:引入松弛變量x4，x5將原線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型:

第一步:由(i ≠j)的系數(shù)列向量構(gòu)成單位陣，易知選x4，x5作為基變量，同時(shí)非基變量全取0，得基本解(0 0 0 3 9)。

第二步:在約束條件中把基變量用非基變量來

第三步:x1，x5作為新的基變量，得:

第四步:x2，x5作為新的基變量，得:

代入目標(biāo)函數(shù)得:Z = 9－x1+x3－3x4，由σ1＜0σ3＞0σ4＜0 故選x3作為進(jìn)基變量。

再當(dāng)時(shí)，x5= 0，x2=選x5作為出基變量。

而此時(shí)x2，x3作為新的基變量，得:

3 出基變量與線性無關(guān)性

在確定進(jìn)基變量后，出基變量的選取便非常重要，這時(shí)需要保證兩點(diǎn):新的變量組合是否能保證對(duì)應(yīng)系數(shù)列向量線性無關(guān)，從而確能構(gòu)成新的基變量;當(dāng)非基變量全取0 值，基變量依照約束條件可取得非負(fù)值，從而得到的是基本可行解。

倘若在第二步中選取x2作為進(jìn)基變量，

此時(shí)x2只與x4有關(guān)系，而與x5無關(guān)，出基變量只能選x4，以使得x2和x5構(gòu)成新的基變量組合。但顯然x2與x4對(duì)應(yīng)的系數(shù)列向量線性相關(guān)，它們不能成為新的基變量組合。

4 結(jié)束語

事實(shí)上，在單純形法的計(jì)算中，觀察出一個(gè)初始的基本可行解后，由上述基變量的線性無關(guān)性可知所有的非基變量都可能作為進(jìn)基變量，但只有通過檢驗(yàn)數(shù)σk判斷出的進(jìn)基變量xk才可以改善目標(biāo)函數(shù)取值，從而朝最優(yōu)解方向前進(jìn)。同樣確定了進(jìn)基得變量后，由前述亦知滿足線性無關(guān)性和非負(fù)約束條件的出基變量可能也并不唯一，通過判斷xk所能取得最大值θ，使其它基變量非負(fù)，若此時(shí)某xt= 0，則xk與xt一定有關(guān)系，故可取xt作為出基變量，并且目標(biāo)函數(shù)改善程度最大，達(dá)到θσk個(gè)單位。

［1］陳利民，蘇宏業(yè)，牟盛靜，等. 基于有界變量單純形法的區(qū)間改進(jìn)牛頓法［J］. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2003，37(3):269－272.

［2］宋政芳. 單純形法中進(jìn)基變量的選擇［J］. 上海電力學(xué)院學(xué)報(bào)，2007，23(1):97－99.

［3］鄧廷勇，張姮妤. 運(yùn)籌學(xué)教學(xué)與數(shù)學(xué)建模思想的融合［J］. 宜春學(xué)院學(xué)報(bào)，2014，36(9):129－131.

［4］楊民助. 運(yùn)籌學(xué)［M］. 西安:西安交通大學(xué)出版社，2000:10－15.

［5］同濟(jì)大學(xué)數(shù)學(xué)系. 工科數(shù)學(xué)線性代數(shù)［M］. 北京:高等教育出版社，2007:94－102.