劉雁靈，李 菲

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

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

1 避免人工變量的新算法

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

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

算法步驟如下：

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

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

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

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

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

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

2 舉例

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

解 將約束條件化為等式得

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

于是得到一個(gè)不可行基(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對(duì)應(yīng)的x6換出，經(jīng)過行變換（軸心項(xià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對(duì)應(yīng)的右項(xiàng)是正值3/2，不能求比值，故選擇x5換出，經(jīng)過行變換（軸心項(xià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

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

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

解 本模型已是標(biāo)準(zhǔn)型，寫出增廣矩陣并作初等行變換，任意尋找一個(gè)單位矩陣

于是得到一個(gè)不可行基(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對(duì)應(yīng)的右項(xiàng)是正值1，不能求比值，故選擇x4換出，經(jīng)過行變換（軸心項(xià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í)檢驗(yàn)數(shù)行元素全是非負(fù)的，但右項(xiàng)有負(fù)值-1，故利用對(duì)偶單純形法求解，選x5換出，用該行負(fù)值-1除相應(yīng)的檢驗(yàn)數(shù)1/3再取絕對(duì)值得比值1/3，故選x2換入，經(jīng)過行變換（軸心項(xià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é)束語

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

〔1〕 吳振奎.線性規(guī)劃中一個(gè)避免人工變?cè)姆椒╗J].運(yùn)籌與管理，1998（2）：78-82.

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

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

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

〔5〕 周學(xué)松，趙恒.線性規(guī)劃中一個(gè)避免人工變?cè)姆椒ǖ母倪M(jìn)[J].運(yùn)籌與管理，2011（5）：31-38.

〔6〕 寧宣熙.運(yùn)籌學(xué)實(shí)用教程[M].北京：科學(xué)出版社，2013.