楊大勇

（隴東學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 慶陽 745000）

線性規(guī)劃模型如下

現(xiàn)在對(duì)線性規(guī)劃問題(LP)化成標(biāo)準(zhǔn)型(LP')可運(yùn)用單純形法得到最優(yōu)表,設(shè)T(B)為對(duì)應(yīng)的最終單純形表,簡(jiǎn)記為：

對(duì)線性規(guī)劃模型(LP)在增加約束條件的情況[1]中做了詳細(xì)的說明.而對(duì)線性規(guī)劃模型(LP)在減少約束條件時(shí)進(jìn)行靈敏度分析,教材中提的較少.因?yàn)榈^程已將要去掉的約束條件經(jīng)過行初等變換作用于其它約束條件以及目標(biāo)函數(shù)中,對(duì)整個(gè)迭代過程都產(chǎn)生了影響.

在前面的最終表T(B)中,最優(yōu)基B的逆矩陣為B-1,線性規(guī)劃模型(LP)的原m×n階系數(shù)矩陣為A,在最終表T(B)中為即.要將第i個(gè)方程去掉,就須使第i個(gè)約束條件失靈.處理方法可在第i個(gè)約束條件左邊添加兩個(gè)非負(fù)虛擬變量的差xn+m+1-xn+m+2.[4]

因此,現(xiàn)將去掉第i個(gè)約束條件的靈敏度分析的基本思路及步驟歸納如下：

1）確定B-1的第i列向量B-1Pi;

2）在最優(yōu)表中系數(shù)矩陣的最后添加B-1Pi和-B-1Pi;

3）計(jì)算相應(yīng)的檢驗(yàn)數(shù)-CBB-1Pi和CBB-1Pi,并添加到T(B)相應(yīng)檢驗(yàn)數(shù)行中;

4）判斷最優(yōu)性：若CBB-1Pi=0,刪掉xn+m+1或xn+m+2對(duì)應(yīng)的系數(shù)行（第i行）得到所求最優(yōu)解;若CBB-1Pi≠0,則轉(zhuǎn)入第5步;

5）刪掉xn+m+1和xn+m+2對(duì)應(yīng)的系數(shù)列,則得到新的單純形表，采用單純形法繼續(xù)迭代.

例1 如下線性規(guī)劃模型：maxz=-5x1+5x2+13x3

用單純形法求解并回答：若在原問題中減少第三個(gè)約束條件,這對(duì)于最優(yōu)解有何影響？

解 先將原問題化為標(biāo)準(zhǔn)型，則可列出初始單純形表,運(yùn)用單純形法進(jìn)行迭代求解,可得最終單純形表.于是知道原問題的最優(yōu)解為.現(xiàn)在要將第三個(gè)設(shè)備約束條件去掉,需要經(jīng)過以下步驟來實(shí)現(xiàn)：

由于要將第三個(gè)設(shè)備約束條件去掉,從最終單純形表中可以得出,從而有.則修改原問題的最終單純形表,得表

Cj→-5 5 13 0 0 0 0 0 CB基b x1 x2 x3 x4 x5 x6 x7 x813 x3 5/2-5/4 0 1 3/4 0-1/4 [1/4]-1/40 x5 15 27/2 0 0 1/2 1-1/2 1/2-1/25 x2 25/2 11/4 1 0-5/4 0 3/4-3/4 3/4 σj→-5/2 0 0-34/6 0-1/2 1/2-1/2

判別最優(yōu)性,不符合條件,則x7進(jìn)基,x3出基,主元素為，采用單純形法繼續(xù)迭代,得

Cj→-5 5 13 0 0 0 0 0 CB基b x1 x2 x3 x4 x5 x6 x7 x80 x7 10-5 0 4 3 0-1 1-10 x5 10 16 0-2-1 1 0 0 05 x2 20-1 1 3 1 0 0 0 0 σj→ 0 0-2-43/6 0 0 0 0

刪去表中基變量x7對(duì)應(yīng)的系數(shù)行及x7和x8對(duì)應(yīng)的系數(shù)列,顯然,松弛變量x6對(duì)應(yīng)的系數(shù)列也可被同時(shí)刪去了,再判別最優(yōu)性,已經(jīng)符合條件,迭代停止.最優(yōu)解為:X*=(0,20,0,0,10)T,z*=100.

本文主要針對(duì)減少約束條件的情形來對(duì)如何求最優(yōu)解進(jìn)行了討論,最后給出了實(shí)例,將方法討論中的理論付諸于實(shí)踐,更有效地說明了理論的可行性和實(shí)用性.

〔1〕胡運(yùn)權(quán).運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社,2003.5.

〔2〕楊桂元.影子價(jià)格及其靈敏度分析[J].運(yùn)籌與管理,2002,11（6）:12-13.

〔3〕李蘇北.運(yùn)籌學(xué)基礎(chǔ)[M].成都：四川大學(xué)出版社,2003.1.

〔4〕解心江.線性規(guī)劃模型減少約束時(shí)的靈敏度分析[J].農(nóng)業(yè)系統(tǒng)科學(xué)與綜合研究.2002,18（3）：178-179.

〔5〕徐渝,賈濤.運(yùn)籌學(xué)（上冊(cè)）[M].北京：清華大學(xué)出版社,2005.2.

〔6〕劉滿鳳,傅波,聶高輝.運(yùn)籌學(xué)模型與方法教程例題分析與題解[M].北京：清華大學(xué)出版社,2001.2.

〔7〕傅家良.運(yùn)籌學(xué)方法與模型[M].上海：復(fù)旦大學(xué)出版社,2006.1.