第二章 對偶理論

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

對偶單純形法靈敏度分析

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

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

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

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

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

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

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

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

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

x2

原問題12y1

22≤128y2

12≤816y340≤1612y404≤12對偶問題23（原問題）（對偶問題）模型對比：已知P，寫出D。

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

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

W=0y1-5y2+2y3y1

y3

y2

反正≥0≤0無約束≥0≤0=0=0單純形法計算的矩陣描述項目非基變量基變量XBXN

XS0XBb

BN

I

cj

-zj

CBCN

0項目基變量非基變量XBXN

XSCB

XB

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

cj

-zj0CN-CBB-1N-CBB-1二、對偶問題的基本性質(zhì)CBB-1：單純形乘子單純形法計算的矩陣描述原問題檢驗數(shù)與對偶問題解的關(guān)系

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

‖‖YS=(YS1,YS2)T

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

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

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

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

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

推論⑴

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

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

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

的最小值不能小于10，Z

的最大值不能超過40。＜例2、已知試用對偶理論證明原問題無界。解：=(0,0,0)T是P的一個可行解，而D的第一個約束條件不能成立（因為y1,

y2≥0)。因此，對偶問題不可行，由推論⑶可知，原問題無界。

3、最優(yōu)性

若X*

和Y*分別是P和D

的可行解且CX*=Y*b，則X*.Y*分別是問題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、強對偶性（對偶定理）：若一對對偶問題P和D

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

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

和Y*，則必有CX*=Y*b；②一個問題無界，則另一個問題無可行解；③兩個都無可行解。

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

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

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

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

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

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

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

bX≥0引入xs

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

為-Y*

，故求對偶Y*

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

對應(yīng)的檢驗數(shù)反號即可。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對偶問題的最優(yōu)解：Y*=（0,32/7,6/7），W=4100/7也就是外加工時的收費標(biāo)準(zhǔn)。⑵.設(shè)原問題：maxZ=CXAX=bX≥0此時，矩陣A中沒有現(xiàn)成的矩陣I，必須通過加入人工變量來湊一個單位矩陣，再用大M法或兩階段法求解。如何求Y*，經(jīng)分析得出如下結(jié)論：

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

σI=CI

－CBB-1

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

σD=CD

－CBB-1D非基變量檢驗數(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初始基變量的檢驗數(shù)σ4=－1/3，σ6=1/3－M,σ7=2/3－M定義：在一對P和D中，若P的某個約束條件的右端項常數(shù)bi

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

的改變量y*i

稱為第i

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

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

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

當(dāng)bi

變?yōu)閎i+1時（其余右端項不變，也不影響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)濟意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對偶變量yi

就是第i

個約束條件的影子價格。

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

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

（2）影子價格反映了資源的稀缺性，影子價格越高，則越稀缺。影子價格＞市場價格，影子價格＜市場價格，則應(yīng)買進該資源則應(yīng)賣出該資源（1）影子價格≠市場價格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)單純形表求對偶問題最優(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個單位的剩余）影子價格y1=50y2=0y3=50,B-1對應(yīng)的檢驗數(shù)cBB-1

。‖‖

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

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

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

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

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

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

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

則選

=min{j’/

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

對偶單純形法求解線性規(guī)劃問題過程：例一、用對偶單純形法求解：解：將模型轉(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，

原問題Z*=72

其對偶問題的最優(yōu)解為：

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

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

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

3．在靈敏度分析中，有時需要用對偶單純形法，這樣可使問題的處理簡化。對偶純形法的局限性主要是，對大多數(shù)線性規(guī)劃問題，很難找到一個初始可行基，因而這方法在求解線性規(guī)劃問題時很少單獨應(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單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法

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

五、靈敏度分析

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

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

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

可以分別就cj是對應(yīng)的非基變量和基變量兩種情況來討論。(1)若cj是非基變量xj的系數(shù)，這時它在計算表中所對應(yīng)的檢驗數(shù)是

σj=cj-CBB-1Pj

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

例3：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計劃問題歸結(jié)為下列線性規(guī)劃已知最優(yōu)表如下。（1）確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)；（2）若c2=6，求新的最優(yōu)計劃。一、價值系數(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ī)劃問題的其他系數(shù)都不變。這樣使最終表中原問題的解相應(yīng)地變化為XB′=B-1(b+Δb)這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB′為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。B-1

是最終計算表中的最優(yōu)基的逆例1：求下列LP問題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：對于上例中的線性規(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]時，最優(yōu)基B不變z*=5×（80－b3）+4×（－80+2b3）=80+3b3=（2）當(dāng)b3=55時

=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對偶單純形三、增加一個變量的分析例5：（續(xù)例3）設(shè)企業(yè)研制了一種新產(chǎn)品，對三種資源的消耗系數(shù)列向量以P6表示P6=。問它的價值系數(shù)c6符合什么條件才必須安排它的生產(chǎn)？設(shè)c6=3，新的最優(yōu)生產(chǎn)計劃是什么？σ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中，還要考慮一個新的資源約束：

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

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