第二章 對(duì)偶理論

對(duì)偶理論(DualityTheory)線性規(guī)劃的對(duì)偶問(wèn)題對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋----影子價(jià)格

對(duì)偶單純形法靈敏度分析

對(duì)偶性是線性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（LP

）必然有與之相伴而生的另一個(gè)線性規(guī)劃問(wèn)題，即任何一個(gè)求maxZ

的LP都有一個(gè)求minZ的LP。其中的一個(gè)問(wèn)題叫“原問(wèn)題”，記為“P”，另一個(gè)稱為“對(duì)偶問(wèn)題”，記為“D”。一、線性規(guī)劃的對(duì)偶問(wèn)題（一）對(duì)偶問(wèn)題的提出

例一、資源的合理利用問(wèn)題1810單件利潤(rùn)150（設(shè)備）51C100（煤炭）32B170（鋼材）25A資源限制乙甲單件產(chǎn)消耗品資源

已知資料如表所示，問(wèn)應(yīng)如何安排生產(chǎn)計(jì)劃使得既能充分利用現(xiàn)有資源又使總利潤(rùn)最大？下面從另一個(gè)角度來(lái)討論這個(gè)問(wèn)題：假定：該廠的決策者不是考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來(lái)加工任務(wù)，只收取加工費(fèi)。試問(wèn)該決策者應(yīng)制定怎樣的收費(fèi)標(biāo)準(zhǔn)（合理的）？分析問(wèn)題：

1、每種資源收回的費(fèi)用不能低于自己生產(chǎn)時(shí)的可獲利潤(rùn)；

2、定價(jià)又不能太高，要使對(duì)方能夠接受。生產(chǎn)產(chǎn)品甲需資源5(A),2(B),1(C),盈利10元；生產(chǎn)產(chǎn)品乙需資源2(A),3(B),5(C),盈利18元；租賃公司又希望用最小的費(fèi)用將三種資源全部買過(guò)來(lái)

一般而言，W越小越好，但因需雙方滿意，故為最好。該問(wèn)題的數(shù)學(xué)模型為：模型對(duì)比：例二、合理配料問(wèn)題，其數(shù)學(xué)模型為：假設(shè)工廠想把這m

種營(yíng)養(yǎng)成分分別制成一種營(yíng)養(yǎng)丸銷售，問(wèn)如何定價(jià)（以保證總收入為最多）？原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)maxmin約束條件≤≥變量數(shù)量約束條件個(gè)數(shù)約束條件個(gè)數(shù)變量數(shù)量例三、23x1

x2

原問(wèn)題12y1

22≤128y2

12≤816y340≤1612y404≤12對(duì)偶問(wèn)題23（原問(wèn)題）（對(duì)偶問(wèn)題）模型對(duì)比：已知P，寫出D。

（二）對(duì)稱形式下對(duì)偶問(wèn)題的一般形式例一：寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：首先將原式變形

注意：以后不強(qiáng)調(diào)等式右段項(xiàng)b≥0，原因在對(duì)偶單純型表中只保證而不保證，故b可以是負(fù)數(shù)。（三）非對(duì)稱形式的原-對(duì)偶問(wèn)題關(guān)系例二：原問(wèn)題混合型對(duì)偶問(wèn)題例三：原問(wèn)題對(duì)偶問(wèn)題綜上所述，其變換形式歸納如下：原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無(wú)約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無(wú)約束=b約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)C目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)例四、線性規(guī)劃問(wèn)題如下：練習(xí)：235317146224Maxw=2y1+3y2+5y3y10y20y30≥≤≤≤≤≤y3y3y3y2+y2+y2+y1+y1+y1+正反無(wú)約束1-23401342-3-7-432-34Min

W=0y1-5y2+2y3y1

y3

y2

反正≥0≤0無(wú)約束≥0≤0=0=0單純形法計(jì)算的矩陣描述項(xiàng)目非基變量基變量XBXN

XS0XBb

BN

I

cj

-zj

CBCN

0項(xiàng)目基變量非基變量XBXN

XSCB

XB

B-1bI（B-1B）B-1NB-1

cj

-zj0CN-CBB-1N-CBB-1二、對(duì)偶問(wèn)題的基本性質(zhì)CBB-1：?jiǎn)渭冃纬俗訂渭冃畏ㄓ?jì)算的矩陣描述原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系

設(shè)原問(wèn)題是maxz=CX;AX+IXS=b;X,XS≥0它的對(duì)偶問(wèn)題是minω=Yb;YA-IYS=C;Y,YS≥0則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解，其對(duì)應(yīng)關(guān)系如表所示。YS1是對(duì)應(yīng)原問(wèn)題中基變量XB的剩余變量，YS2是對(duì)應(yīng)原問(wèn)題中非基變量XN的剩余變量

‖‖YS=(YS1,YS2)T

證:設(shè)B是原問(wèn)題的一個(gè)可行基，于是A=(B,N)；原問(wèn)題可以改寫為

maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS≥0相應(yīng)地對(duì)偶問(wèn)題可表示為

minω=YbYB-YS1=CB(1)YN-YS2=CN(2)Y，YS1,YS2≥0這里YS=(YS1，YS2)T。當(dāng)求得原問(wèn)題的一個(gè)解：XB=B-1b其相應(yīng)的檢驗(yàn)數(shù)為CN-CBB-1N與-CBB-1現(xiàn)分析這些檢驗(yàn)數(shù)與對(duì)偶問(wèn)題的解之間的關(guān)系：令Y=CBB-1，將它代入(1)式，(2)式得YS1=0,-YS2=CN-CBB-1NminZ’=-CXs.t.-AX≤-b X≥01、對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥b X≥0對(duì)偶的定義對(duì)偶的定義maxW’=-Ybs.t.YA≥CY≤0對(duì)偶問(wèn)題的基本性質(zhì)弱對(duì)偶定理定理對(duì)偶問(wèn)題(min)的任何可行解Y0，其目標(biāo)函數(shù)值總是不小于原問(wèn)題(max)任何可行解X0的目標(biāo)函數(shù)值

為了便于討論，下面不妨總是假設(shè)

推論⑴

若和分別是問(wèn)題（P）和（D）的可行解，則是（D）的目標(biāo)函數(shù)最小值的一個(gè)下界；是（P）的目標(biāo)函數(shù)最大值的一個(gè)上界。2、弱對(duì)偶性（弱對(duì)偶原理）：設(shè)和分別是問(wèn)題（P）和（D）的可行解，則必有

推論⑵.在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題不可行；反之不成立。這也是對(duì)偶問(wèn)題的無(wú)界性。關(guān)于無(wú)界性有如下結(jié)論：?jiǎn)栴}無(wú)界無(wú)可行解無(wú)可行解問(wèn)題無(wú)界對(duì)偶問(wèn)題原問(wèn)題無(wú)界如：（P）無(wú)可行解（D）

推論⑶.在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行，（如D），則該可行的問(wèn)題無(wú)界。例1、試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。（P）解：（D）由觀察可知：=（1,1,1,1）T，=（1,1），分別是（P）和（D）的可行解。Z=10，W=40，故有，弱對(duì)偶定理成立。由推論⑴可知，W

的最小值不能小于10，Z

的最大值不能超過(guò)40。＜例2、已知試用對(duì)偶理論證明原問(wèn)題無(wú)界。解：=(0,0,0)T是P的一個(gè)可行解，而D的第一個(gè)約束條件不能成立（因?yàn)閥1,

y2≥0)。因此，對(duì)偶問(wèn)題不可行，由推論⑶可知，原問(wèn)題無(wú)界。

3、最優(yōu)性

若X*

和Y*分別是P和D

的可行解且CX*=Y*b，則X*.Y*分別是問(wèn)題P和D

的最優(yōu)解。例如，在例1中，可找到X*=(0,0,4,4)T，

Y*=(1.2，0.2),則Z=28，W=28.故X*

、Y*分別是P和D的最優(yōu)解。

4、強(qiáng)對(duì)偶性（對(duì)偶定理）：若一對(duì)對(duì)偶問(wèn)題P和D

都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。推論⑷若P和D的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等。

綜上所述，一對(duì)對(duì)偶問(wèn)題的關(guān)系，只能有下面三種情況之一出現(xiàn)：①都有最優(yōu)解，分別設(shè)為X*

和Y*，則必有CX*=Y*b；②一個(gè)問(wèn)題無(wú)界，則另一個(gè)問(wèn)題無(wú)可行解；③兩個(gè)都無(wú)可行解。

5、互補(bǔ)松弛定理：設(shè)X*和Y*分別是問(wèn)題P和D的可行解，則它們分別是最優(yōu)解的充要條件是同時(shí)成立一般而言，我們把某一可行點(diǎn)（如X*和Y*

）處的嚴(yán)格不等式約束（包括對(duì)變量的非負(fù)約束）稱為松約束，而把嚴(yán)格等式約束稱為緊約束。所以有如下推論：設(shè)一對(duì)對(duì)偶問(wèn)題都有可行解，若原問(wèn)題的某一約束是某個(gè)最優(yōu)解的松約束，則它的對(duì)偶約束一定是其對(duì)偶問(wèn)題最優(yōu)解的緊約束。例3、已知試通過(guò)求對(duì)偶問(wèn)題的最優(yōu)解來(lái)求解原問(wèn)題的最優(yōu)解。解：對(duì)偶問(wèn)題為用圖解法求出：Y*=（1,3），W=11。將y*1=1，y*2=3代入對(duì)偶約束條件，（1）（2）（5）式為緊約束，（3）（4）為松約束。令原問(wèn)題的最優(yōu)解為X*=(x1,x2,x3,x4,x5)T，則根據(jù)互補(bǔ)松弛條件，必有x3=x4=0(1,3)（1）（2）（3）（4）（5）又由于y*1＞0，y*2

＞0，原問(wèn)題的約束必為等式，即此方程組為無(wú)窮多解令x5=0,得到x1=1，x2=2

即X*1=(1,2,0,0,0)T為原問(wèn)題的一個(gè)最優(yōu)解

Z*=11再令x5=2/3，得到x1=5/3，x2=0即X*2=(5/3,0,0,0,2/3)T也是原問(wèn)題的一個(gè)最優(yōu)解

Z*=11例4、已知原問(wèn)題的最優(yōu)解為X*=（0，0，4）T，Z=12。試求對(duì)偶問(wèn)題的最優(yōu)解。解：（1）（2）（3）將X*=（0，0，4）T代入原問(wèn)題中，有下式：所以，根據(jù)互補(bǔ)松弛條件，必有y*1=y*2=0，代入對(duì)偶問(wèn)題（3）式，y3=3。因此，對(duì)偶問(wèn)題的最優(yōu)解為

Y*=（0，0，3），W=12。6、對(duì)偶問(wèn)題的解利用原問(wèn)題的最優(yōu)單純形表和改進(jìn)單純形表求解對(duì)偶問(wèn)題的最優(yōu)解。⑴.設(shè)原問(wèn)題為：maxZ=CXAX≤

bX≥0引入xs

，構(gòu)建初始基變量，然后，用單純形法求解。當(dāng)檢驗(yàn)數(shù)滿足σj≤0，則求得最優(yōu)解。此時(shí)，xs對(duì)應(yīng)的σjs

為-Y*

，故求對(duì)偶Y*

，只要將最優(yōu)單純形表上xs

對(duì)應(yīng)的檢驗(yàn)數(shù)反號(hào)即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN－CBB-1N－CBB-1例1、cj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7Z4100/7000-32/7-6/7初始表最終表由上表可知：X*=（50/7,200/7），Z=4100/7對(duì)偶問(wèn)題的最優(yōu)解：Y*=（0,32/7,6/7），W=4100/7也就是外加工時(shí)的收費(fèi)標(biāo)準(zhǔn)。⑵.設(shè)原問(wèn)題：maxZ=CXAX=bX≥0此時(shí)，矩陣A中沒(méi)有現(xiàn)成的矩陣I，必須通過(guò)加入人工變量來(lái)湊一個(gè)單位矩陣，再用大M法或兩階段法求解。如何求Y*，經(jīng)分析得出如下結(jié)論：

σB=0最優(yōu)基變量檢驗(yàn)數(shù)向量

σI=CI

－CBB-1

初始基變量檢驗(yàn)數(shù)向量

σD=CD

－CBB-1D非基變量檢驗(yàn)數(shù)向量所以，Y*=CI

－σI

例2、cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z3-6M-1+M-1+3M0-M00初始表最終表所以，X*=（4,1,9），Z=2∴y*1=(0－σ4)=1/3y*2=(－M－σ6)=－M－(1/3－M)=－1/3y*3=(－M－σ7)=－M－(2/3－M)=－2/3Y*=（1/3,－1/3,－2/3）W=2初始基變量的檢驗(yàn)數(shù)σ4=－1/3，σ6=1/3－M,σ7=2/3－M定義：在一對(duì)P和D中，若P的某個(gè)約束條件的右端項(xiàng)常數(shù)bi

增加一個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z*

的改變量y*i

稱為第i

個(gè)約束條件的影子價(jià)格，又稱為邊際價(jià)格。三、對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋—影子價(jià)格

設(shè)：B是問(wèn)題P的最優(yōu)基，由前式可知，

Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm

當(dāng)bi

變?yōu)閎i+1時(shí)（其余右端項(xiàng)不變，也不影響B(tài)），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN－CBB-1N－CBB-1目標(biāo)函數(shù)最優(yōu)值變?yōu)椋?/p>

Z′*=y*1b1+y*2b2+…+y*i（

bi+1）+…+y*mbm

∴△Z*=Z′*－Z*=y*i

也可以寫成：

經(jīng)濟(jì)意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對(duì)偶變量yi

就是第i

個(gè)約束條件的影子價(jià)格。

也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)（但問(wèn)題中所有其它數(shù)據(jù)都保持不變）。即y*i

表示Z*對(duì)bi的變化率。影子價(jià)格在管理決策中的作用：

（2）影子價(jià)格反映了資源的稀缺性，影子價(jià)格越高，則越稀缺。影子價(jià)格＞市場(chǎng)價(jià)格，影子價(jià)格＜市場(chǎng)價(jià)格，則應(yīng)買進(jìn)該資源則應(yīng)賣出該資源（1）影子價(jià)格≠市場(chǎng)價(jià)格01020304050601020304050x2

x1123(50/7.200/7)①②③01020304050601020304050x2

x1123(50/7.200/7)Y1=0①②③多了32/7x101020304050601020304050x2

123(55/7.199/7)Y2=

32/7①②③01020304050601020304050x2

x1123(47/7.202/7)多了6/7Y3=

6/7①②③

5.由最優(yōu)單純形表求對(duì)偶問(wèn)題最優(yōu)解

標(biāo)準(zhǔn)形式：

Max

z=50x1+100x2

s.t.x1+x2+x3=300

2x1+x2+x4=400

x2+x5=250

x1,x2,x3,x4,x5

≥0cBB-1B=(p1,p2,p4)B-1最優(yōu)解

x1=50x2=250x4=50(松弛變量，表示原料A有50個(gè)單位的剩余）影子價(jià)格y1=50y2=0y3=50,B-1對(duì)應(yīng)的檢驗(yàn)數(shù)cBB-1

。‖‖

對(duì)偶單純形法是求解線性規(guī)劃的另一基本方法。它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來(lái)的，因此稱為對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法。由對(duì)偶理論可以知道，對(duì)于一個(gè)線性規(guī)劃問(wèn)題，我們能夠通過(guò)求解它的對(duì)偶問(wèn)題來(lái)找到它的最優(yōu)解。四、對(duì)偶單純形法

對(duì)偶單純形法的基本思想對(duì)偶單純形法的基本思想是：從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正σj≤0），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。4.對(duì)偶單純形法對(duì)偶單純形法在什么情況下使用：

應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足:

①單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）；

②變量取值可有負(fù)數(shù)（非可行解）。

注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純性表。4.對(duì)偶單純形法1.建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；2.若b′≥0,則得到最優(yōu)解,停止;否則,令bk=min{bi<0}

則選k行的基變量為出基變量,轉(zhuǎn)33.若所有akj’≥0(j=1,2,…,n)，則原問(wèn)題無(wú)可行解,停止;否則,若有akj′<0

則選

=min{j’/

akj’┃akj’<0}=r’/akr’那么xr為進(jìn)基變量,轉(zhuǎn)4；4.以akr’為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。

對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程：例一、用對(duì)偶單純形法求解：解：將模型轉(zhuǎn)化為cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001Z′

0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5Z′

-42-6-9000-3(-9/-1,-12/-1,-15/-5)(-30/-9,-45/-14,-15/-1)cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14Z′

-501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9Z′

-72000-1/3-3-7/3(-3/-9,-45/-9,-33/-1)

所以，

X*=（2,2,2,0,0,0），

Z′*=－72，

原問(wèn)題Z*=72

其對(duì)偶問(wèn)題的最優(yōu)解為：

Y*=(1/3,3,7/3)，W*=72對(duì)偶單純形法的優(yōu)點(diǎn)

1．初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。

2．當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問(wèn)題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。

3．在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。對(duì)偶純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這方法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用練習(xí)：cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301Z

-2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2Z

0-4-10-1cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5Z

28/500-3/5-8/5-1/5Y=（8/5,1/5）X=（11/5,2/5,0）Z=28/5單純形法和對(duì)偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法

對(duì)偶單純形法的適用范圍對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問(wèn)題4.對(duì)偶單純形法在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便。

五、靈敏度分析

以前討論線性規(guī)劃問(wèn)題時(shí)，假定aij，bi，cj都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值。如市場(chǎng)條件一變，cj值就會(huì)變化；aij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個(gè)問(wèn)題：(1)當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化；(2)或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解或最優(yōu)基不變。后一個(gè)問(wèn)題將在第6節(jié)參數(shù)線性規(guī)劃中討論。線性規(guī)劃問(wèn)題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化?顯然，當(dāng)線性規(guī)劃問(wèn)題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來(lái)已得結(jié)果一般會(huì)發(fā)生變化。可以用單純形法從頭計(jì)算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒(méi)有必要。因在單純形法迭代時(shí)，每次運(yùn)算都和基變量的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過(guò)一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分析，可按下表中的幾種情況進(jìn)行處理。靈敏度分析步驟：

1.將參數(shù)的改變通過(guò)計(jì)算反映到

最終單純形表上2.檢查原問(wèn)題是否仍為可行解。3.檢查對(duì)偶問(wèn)題是否仍為可行解。表2-94.按表2-9所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。一、目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析

可以分別就cj是對(duì)應(yīng)的非基變量和基變量?jī)煞N情況來(lái)討論。(1)若cj是非基變量xj的系數(shù)，這時(shí)它在計(jì)算表中所對(duì)應(yīng)的檢驗(yàn)數(shù)是

σj=cj-CBB-1Pj

或當(dāng)cj變化Δcj后，要保證最終表中這個(gè)檢驗(yàn)數(shù)仍小于或等于零，即σj’=c’j-CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必須小于或等于YPj-cj，才可以滿足原最優(yōu)解條件。這就可以確定Δcj的范圍了。

例3：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計(jì)劃問(wèn)題歸結(jié)為下列線性規(guī)劃已知最優(yōu)表如下。（1）確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)；（2）若c2=6，求新的最優(yōu)計(jì)劃。一、價(jià)值系數(shù)cj的變化分析cj5000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最優(yōu)單純形表4c2最優(yōu)解不變？σ4=c2－5≤0σ5=5－2c2

≤05/2≤c2≤5cj5c2

000CBXBbx1x2x3x4x50x3250012-55x1351001-1c2

x2

10010-12000c2-55-2c2最優(yōu)解X*=（35，10，25，0，0）保持不變。（1）Cj56000CBXBbx1x2x3x4x50x325001[2]-55x1351001-16x2

10010-12σj

0001-70x425/2001/21-5/25x145/210-1/203/26x2

45/2011/20-1/2σj00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2（2）二、資源數(shù)量變化的分析(b)

資源數(shù)量變化是指資源中某系數(shù)br發(fā)生變化，即br′=br+Δbr。并假設(shè)規(guī)劃問(wèn)題的其他系數(shù)都不變。這樣使最終表中原問(wèn)題的解相應(yīng)地變化為XB′=B-1(b+Δb)這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗(yàn)數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB′為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。B-1

是最終計(jì)算表中的最優(yōu)基的逆例1：求下列LP問(wèn)題Cj0-130-20CBXBbx1x2x3x4x5x60x1713-10200x4120-2[4]1000x6

100-43081σj

0-130-200x1101[5/2]01/4203x330-1/211/4000x6

10-5/20-3/481σj01/20-3/4-20-1x242/5101/104/503x351/5013/102/500x6

11100-1/2101σj-1/500-4/5-12/50B3=（P2，P3，P6）=B3－1=例4：對(duì)于上例中的線性規(guī)劃作下列分析：（1）b3在什么范圍內(nèi)變化，原最優(yōu)基不變？（2）若b3=55，求出新的最優(yōu)解。

二、右端常數(shù)bi的變化分析cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最優(yōu)基：B=（P3，P1，P2）B－1=（1）B－1==≥0解得40≤b3≤50，即當(dāng)b3∈[40，50]時(shí)，最優(yōu)基B不變z*=5×（80－b3）+4×（－80+2b3）=80+3b3=（2）當(dāng)b3=55時(shí)

=x2

x1x50-11/5-3/500σj0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1[-5]x50-1000σj

-101030x2

4100125x152100-25x30x4x3x2x1bXBCB0045Cj對(duì)偶單純形三、增加一個(gè)變量的分析例5：（續(xù)例3）設(shè)企業(yè)研制了一種新產(chǎn)品，對(duì)三種資源的消耗系數(shù)列向量以P6表示P6=。問(wèn)它的價(jià)值系數(shù)c6符合什么條件才必須安排它的生產(chǎn)？設(shè)c6=3，新的最優(yōu)生產(chǎn)計(jì)劃是什么？σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/2=B－1P6==Cj540003CBXBbx1x2x3x4x5x60x3250012-5[1]5x1351001-11/26x2

10010-120σj

000-1-31/23x6250012-515x145/210-1/203/204x2

10010-120σj00-1/2-2-1/20四、增加新的約束條件的分析4x1+2x2+x6=150X*=（35，10，25，0，0）T例6:

假設(shè)在例3中，還要考慮一個(gè)新的資源約束：

4x1+2x2≤1504x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x2

10010-1200x6150420001000-1-30變化：基變量x1、x2、x3所對(duì)應(yīng)的矩陣不再是單位矩陣。Cj540000CBXBbx1x