孫秀華

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

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

1 基變量、非基變量與線性無關性

設線性規(guī)劃問題標準型如下:［4］

在此不妨假設假設矩陣A 秩為m。

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

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

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

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

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

2 進基變量與線性無關性

由命題1.2 知正因為基變量可以由非基變量表示，每一步迭代時都可以將非基變量代入到目標函數(shù)中，同時此時目標函數(shù)中不含基變量，進而確定非基變量的檢驗數(shù)，并由檢驗數(shù)的符號確定進基變量。見下例:

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

解:引入松弛變量x4，x5將原線性規(guī)劃問題轉化為標準型:

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

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

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

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

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

再當時，x5= 0，x2=選x5作為出基變量。

而此時x2，x3作為新的基變量，得:

3 出基變量與線性無關性

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

倘若在第二步中選取x2作為進基變量，

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

4 結束語

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

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

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

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

［4］楊民助. 運籌學［M］. 西安:西安交通大學出版社，2000:10－15.

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