線性規(guī)劃中關于避免人工變量的一個注記

劉雁靈，李 菲

（1.長治醫(yī)學院 數(shù)學教研室；2.長治醫(yī)學院 衛(wèi)生信息與管理系，山西 長治 046000）

在線性規(guī)劃模型中，若約束條件出現(xiàn)“≥”或者“=”的情況，常見的方法是引入人工變量構(gòu)造人工基再使用大M法或兩階段法來求解，但引入人工變量使得變量增多，線性規(guī)劃問題顯得更加復雜.大量文獻討論了避免引入人工變量的方法，文獻[1]通過對增廣矩陣實施初等行變換來尋找m個列線性無關的向量組，若右項非負則使用單純形法計算，否則重新尋找m個列線性無關的向量組，該法計算量過大；文獻[2]對文獻[1]的方法進行了改進，在系數(shù)矩陣中只選擇m個列線性無關的向量組B，對矩陣(B,b)作初等行變換，若右項非負再把增廣矩陣其他元素考慮進去作同樣的行變換，但計算量仍大；文獻[3]是通過對單純形表做旋轉(zhuǎn)變換來計算的；文獻[4]通過對增廣矩陣實施初等行變換使得系數(shù)矩陣產(chǎn)生單位矩陣，但這一過程要求右項必須保持非負，這就對行變換的過程增加難度，有時亦很難達到；文獻[5]在對增廣矩陣作初等行變換時并不要求右項非負，在求解過程中再根據(jù)右項和檢驗數(shù)行元素的正負情況使用單純形法或者對偶單純形法來計算.本文在前面文獻的基礎上，給出了新的改進方法，一方面在迭代過程中不要求右項的非負性，另一方面也推廣了單純形法中比值θ的計算方法，并通過實例加以驗證.

1 避免人工變量的新算法

本文中的檢驗數(shù)采用σj=zj-cj[6]的計算方法，這樣原問題和其對偶問題解的可行性看得更直觀.

本文方法的思路為：對增廣矩陣實施初等行變換尋找一個初始基，對其單純形表（此時檢驗數(shù)行和右項均可有負）用單純形法或?qū)ε紗渭冃畏ㄟM行換基迭代，經(jīng)過有限次迭代最終求得最優(yōu)解（若最優(yōu)解存在）.

算法步驟如下：

（1）將線性規(guī)劃問題標準化，對增廣矩陣作初等行變換，使得系數(shù)矩陣的位置產(chǎn)生m階單位矩陣（進行列交換之后得到的），這里不要求右項非負；

（2）列出初始單純形表；

（3）若存在負的檢驗數(shù)，則采用單純形法：用負數(shù)絕對值大的那列作為主列，用主列元素去除右項（主列元素與對應的右項同號時），即負元素對應行右項為負時，正元素對應行右項為正時，才可除，產(chǎn)生比值θ，選擇θ最小的基變量為換出變量，實施換基迭代；

（4）若不存在負的檢驗數(shù)，但是右項有負值，則用對偶單純形法進行換基迭代；

（5）若存在負檢驗數(shù)時，主列元素沒有和右項同號的，則不能產(chǎn)生比值θ，故找不出換出變量，說明該線性規(guī)劃問題無最優(yōu)解.

注：步驟（3）（4）（5）不分先后，要根據(jù)不同的情況選擇步驟.

2 舉例

例1 求解線性規(guī)劃問題[2]

解 將約束條件化為等式得

寫出增廣矩陣并作初等行變換，任意尋找一個單位矩陣

于是得到一個不可行基(P5,P6)，列出初始單純形表

x1 x2 x3 x4 x5 x6 b θ-5 2 -3 6 0 0 x5 0 1 2 3 4 1 0 7 7/4 x6 0 -2 -1 -1 -2 0 1 -3 3/2→σj 5 -2 3 -6↑ 0 0

主列是x4列，用4除7得比值7/4，用-2除-3得比值3/2，選擇比值小的3/2對應的x6換出，經(jīng)過行變換（軸心項為a24=-2），得單純形表

x1 x2 x3 x4 x5 x6 b θ-5 2 -3 6 0 0 x5 0 -3 0 1 0 1 2 1 1/2→x4 6 1 1/2 1/2 1 0 -1/2 3/2 σj 11 1 6 0 0 -3↑

主列是x6列，用2除1得比值1/2，-1/2對應的右項是正值3/2，不能求比值，故選擇x5換出，經(jīng)過行變換（軸心項為a16=2），得單純形表

x1 x2 x3 x4 x5 x6 b-5 2 -3 6 0 0 x6 0 -3/2 0 1/2 0 1/2 1 1/2 x4 6 1/4 1/2 3/4 1 1/4 0 7/4 σj 13/2 1 15/2 0 3/2 0

檢驗數(shù)行和右項都非負，此表已是最終形表，最優(yōu)解為：

例2 求解線性規(guī)劃問題[4]

解 本模型已是標準型，寫出增廣矩陣并作初等行變換，任意尋找一個單位矩陣

于是得到一個不可行基(P4,P5,P3)，列出初始單純形表

x 1 x 2 x 3 x 4 x 5 b θ 3 -1 -1 0 0 x 4 0 3 -2 0 1 0 1 0 1 0/3→x 5 0 0 -1 0 0 1 -1 x 3 -1 -2 0 1 0 0 1 σ j-1↑ 1 0 0 0

主列為x1列，用3除10得比值10/3，0不能除-1，-2對應的右項是正值1，不能求比值，故選擇x4換出，經(jīng)過行變換（軸心項為a11=3），得單純形表

x1 x2 x3 x4 x5 b 3 -1 -1 0 0 x1 3 1 -2/3 0 1/3 0 10/3 x5 0 0 -1 0 0 1 -1→x3 -1 0 -4/3 1 2/3 0 23/3 σj 0 1/3 1/3↑ 0 1/3 0

此時檢驗數(shù)行元素全是非負的，但右項有負值-1，故利用對偶單純形法求解，選x5換出，用該行負值-1除相應的檢驗數(shù)1/3再取絕對值得比值1/3，故選x2換入，經(jīng)過行變換（軸心項為a22=-1），得單純形表

x1 x2 x3 x4 x5 b 3 -1 -1 0 0 x1 3 1 0 0 1/3 -2/3 4 x2 -1 0 1 0 0 -1 1 x3 -1 0 0 0 2/3 -4/3 9 σj 0 0 0 1/3 1/3

此表已是最終形表，最優(yōu)解為：

3 結(jié)束語

在文獻[1]-[5]的基礎上，本文給出了一種避免人工變量的新算法：首先對增廣矩陣實施初等行變換之后得到的右項可以有負，其次在迭代過程中將單純形法計算θ的過程加以推廣，主列不僅只有正的元素可以除正的右項，負的也可以除負的，而且同樣可以得出正確的結(jié)果（最優(yōu)解存在的情況下），若最優(yōu)解不存在，亦可判斷出.通過幾個實例的計算，可以看出該法的可行性，與大M法和兩階段法相比，計算量得到減少.

〔1〕 吳振奎.線性規(guī)劃中一個避免人工變元的方法[J].運籌與管理，1998（2）：78-82.

〔2〕 王志江.線性規(guī)劃中人工變量的作用不應忽視[J].運籌與管理，1999（3）：93-96.

〔3〕 吳延東.求線性規(guī)劃問題可行基的一種方法[J].運籌與管理，1999（1）：41-45.

〔4〕 呂林霞，茹少峰，申卯興.線性規(guī)劃中模型的單純形法初始可行基選擇研究[J].西北大學學報（自然科學版），2011（4）：589-592.

〔5〕 周學松，趙恒.線性規(guī)劃中一個避免人工變元的方法的改進[J].運籌與管理，2011（5）：31-38.

〔6〕 寧宣熙.運籌學實用教程[M].北京：科學出版社，2013.