對偶理論與靈敏度分析

對偶理論與靈敏度分析第一頁，共九十四頁，2022年，8月28日第三章

對偶理論與靈敏度分析第二頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出例：常山機(jī)械廠生產(chǎn)Ⅰ和Ⅱ兩種產(chǎn)品。生產(chǎn)中需使用A、B、C三種設(shè)備進(jìn)行加工，加工每件Ⅰ產(chǎn)品或Ⅱ產(chǎn)品所需的設(shè)備機(jī)時(shí)數(shù)、利潤值及每種設(shè)備可利用機(jī)時(shí)數(shù)列于下表，請問：充分利用設(shè)備機(jī)臺時(shí)，工廠應(yīng)生產(chǎn)Ⅰ和Ⅱ產(chǎn)品各多少件才能獲得最大利潤？試列出相應(yīng)的線性規(guī)劃數(shù)學(xué)模型。ABC產(chǎn)品利潤（元／件）Ⅰ2402Ⅱ2053設(shè)備可用機(jī)時(shí)數(shù)（工時(shí)）121615第三頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出解：設(shè)Ⅰ、Ⅱ產(chǎn)品的生產(chǎn)數(shù)量分別為x1和x2，建立問題數(shù)學(xué)模型如下：maxz=2x1+3x22x1+2x2≤124x1≤165x2≤15xj≥0，j=1，2現(xiàn)假設(shè)有另一家四海機(jī)器廠，為了擴(kuò)大生產(chǎn)想租借常山機(jī)器廠擁有的設(shè)備資源，問常山廠分別以每小時(shí)什么樣的價(jià)格才愿意出租自己的設(shè)備呢？第四頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出設(shè)A、B、C設(shè)備的機(jī)時(shí)單價(jià)分別為y1、y2、y3，新的線性規(guī)劃數(shù)學(xué)模型為minw=12y1+16y2+15y32y1+4y2≥22y1+5y3≥3yj≥0，j=1，2，3A（y1）B（y2）C（y3）產(chǎn)品利潤（元／件）Ⅰ（x1）2402Ⅱ（x2）2053設(shè)備可用機(jī)時(shí)數(shù)（工時(shí)）121615maxz=2x1+3x22x1+2x2≤124x1≤165x2≤15xj≥0，j=1，2第五頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出23x1

x2

原問題12y1

22≤1216y2

40≤1615y305≤15對偶問題23第六頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出X1,X2,…,Xnxjyi對偶問題原問題

…MinwMaxZMaxZ=Minw原問題與對偶問題的形式關(guān)系第七頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出原始問題maxz=CXs.t. AX≥b X≥0對偶問題minw=bTYs.t.ATY≤CTY≥0≥maxbACCTATbT≤minmnmn第八頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出原問題與對偶問題maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

……am1x1+am2x2+…+amnxn≤bmxj≥0（j=1,2,…,n）minw=b1y1+b2y2+…+bmym

s.t.a11y1+

a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2

……a1ny1+a2ny2+…+amnym≥cnyi≥0（i=1,2,…,m）

設(shè)原LP問題為則稱下列LP問題第九頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出例：寫出下列線性規(guī)劃問題的對偶問題minw=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

22x1+2x2+4x43x1，x2，

x3，x40解：該問題的對偶問題：

maxz=2y1+3y2s.t.2y1+2y212y1+2y284y1164y212y1，y20y1y2第十頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出例：寫出下列線性規(guī)劃問題的對偶問題maxz=10x1+x2+2x3s.t.x1+x2+2x3

10y14x1+2x2-x320y2

x1，x2，

x30解：該問題的對偶問題：

minw=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y2

0第十一頁，共九十四頁，2022年，8月28日例：寫出下列線性規(guī)劃問題的對偶問題

minw=x1+2x2+3x3s.t.2x1+3x2+5x3

2

3x1+x2+7x33x1，x2，

x30解：用（-1）乘以第二個(gè)約束方程兩邊

minw=x1+2x2+3x3s.t.2x1+3x2+5x3

2y1

-3x1-x2-7x3-3y2x1，x2，

x30該問題的對偶問題：

maxz=2y1-3y2s.t.2y1-3y213y1-y225y1-

7y23y1，y20第一節(jié)對偶問題的提出第十二頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出解：化為對稱形式。max

x1≥0,x2≤0,x3無約束s.t.a11x1+a12x2+a13x3≤

b1z=c1x1+c2x2

+c3x3

a31x1+a32x2+a33x3≥

b3a21x1+a22x2+a23x3=b2令maxs.t.例：寫出下述線性規(guī)劃問題的對偶問題第十三頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出maxs.t.對偶變量mins.t.對偶問題：第十四頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出maxs.t.對偶變量mins.t.對偶問題：第十五頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出原問題（對偶問題）對偶問題（原問題）A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)秩b約束條件右端項(xiàng)向量目標(biāo)函數(shù)中價(jià)格系數(shù)向量c目標(biāo)函數(shù)中價(jià)格系數(shù)向量約束條件右端項(xiàng)向量目標(biāo)函數(shù)變量xj(j=1,···,n)約束條件有n個(gè)xj≥0≥cjxj≤0≤cjxj無約束=cj約束條件有m個(gè)變量有m個(gè)yi(i=1,···,m)≤biyi≥0≥biyi≤0=biyi無約束第十六頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出例：寫出原問題的對偶問題minz=7x1+4x2-3x3-4x1+2x2-6x3≤24-3x1-6x2-4x3≥155x2+3x3=30x1≤

0x2無符號限制

x3≥0maxw=24y1+15y2+30y3y1≤0y2≥0y3無符號限制

-4y1-3y2≥722y1-6y2+5y3=4-6y1-4y2+3y3≤

-3第十七頁，共九十四頁，2022年，8月28日第一節(jié)對偶問題的提出例：寫出(P)問題的(D)問題maxz=2x1+3x2-5x3+x4s.t.4x1+x2-3x3+2x4≥53x1-2x2+7x4≤4-2x1+3x2+4x3+x4=6x1≤

0,x2,x3≥0,x4無符號限制minw=5y1+4y2+6y3s.t.4y1+3y2-2y3≤

2y1-2y2+3y3≥

3-3y1+4y3≥-52y1+7y2+y3=1y1≤

0,y2≥0,y3無符號限制第十八頁，共九十四頁，2022年，8月28日第二節(jié)對偶問題的基本性質(zhì)minZ’=-CXs.t.-AX≤-b X≥01、對稱性：對偶問題的對偶是原問題。

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥b X≥0對偶的定義對偶的定義maxW’=-Ybs.t.YA≥CY≤0第十九頁，共九十四頁，2022年，8月28日2、弱對偶性：設(shè)和分別是問題（P）和（D）的可行解，則必有第二節(jié)對偶問題的基本性質(zhì)第二十頁，共九十四頁，2022年，8月28日ZYX在Y=0的平面上鞍點(diǎn)是z=f(0,y)的極大值點(diǎn)第二節(jié)對偶問題的基本性質(zhì)第二十一頁，共九十四頁，2022年，8月28日XYZ在X=0的平面上鞍點(diǎn)是z=f(0,y)的極小值點(diǎn)第二節(jié)對偶問題的基本性質(zhì)第二十二頁，共九十四頁，2022年，8月28日3、無界性：在一對對偶問題（P）和（D）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問題不可行；反之不成立。原問題對偶問題問題無界無可行解無可行解問題無界第二節(jié)對偶問題的基本性質(zhì)第二十三頁，共九十四頁，2022年，8月28日4、互補(bǔ)松弛性：設(shè)和分別是原問題和其對偶問題的最優(yōu)解，若對偶變量，則原問題相應(yīng)的約束條件若約束條件，則相應(yīng)的對偶變量第二節(jié)對偶問題的基本性質(zhì)第二十四頁，共九十四頁，2022年，8月28日例：給定線性規(guī)劃問題minz=2x1+3x2+x33x1-x2+x3≧1x1+2x2-3x3≧2x1,x2,x3≧0已知對偶問題的最優(yōu)解為y=（y1,y2）T=（1/7,11/7）試用互補(bǔ)松弛性質(zhì)，求原問題的最優(yōu)解。第二節(jié)對偶問題的基本性質(zhì)第二十五頁，共九十四頁，2022年，8月28日解：先寫出它的對偶問題maxw=y1+2y23y1+y2≦2-y1+2y2≦3y1-3y2≦1y1,y2≧0將最優(yōu)解y=（y1,y2）T=（1/7,11/7）代入上面的線性規(guī)劃中，第三個(gè)約束條件嚴(yán)格不等，說明x3=0,第一、二個(gè)約束條件嚴(yán)格取等，說明，x1=4/7,x2=5/7第二節(jié)對偶問題的基本性質(zhì)第二十六頁，共九十四頁，2022年，8月28日例:已知線性規(guī)劃問題

Min.Z=2x1+3x2+5x3+2x4+3x5

S.t.x1+x2+2x3+x4+3x5≥4

2x1–x2+3x3+x4+x5≥3xi≥0(i=1,2,3,4,5)已知對偶問題的最優(yōu)解為y1=4/5,y2=3/5,試應(yīng)用對偶理論解原問題。

第二節(jié)對偶問題的基本性質(zhì)第二十七頁，共九十四頁，2022年，8月28日2＝21/5＜317/5＜57/5＜23=3將y1、y2的值代入，得知②、③、④為嚴(yán)格不等式，于是由互補(bǔ)松弛定理知，必有x2=x3=x4=0；又因y1,y2

＞0，故原問題的兩個(gè)約束必為緊約束，于是有：

x1+3x5=42x1+x5=3解之，x1=x5=1。Z(1,0,0,0,1)=5

解：寫出對偶問題為：

Max.S=4y1+3y2S.t.y1+2y2≤2①y1–y2≤3②

2y1+3y2≤5③

y1+y2≤2④

3y1+y2≤3⑤

y1,y2≥0第二節(jié)對偶問題的基本性質(zhì)第二十八頁，共九十四頁，2022年，8月28日例:已知線性規(guī)劃問題試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。第二節(jié)對偶問題的基本性質(zhì)第二十九頁，共九十四頁，2022年，8月28日用圖解法求出：Y*=（1.3），W=11。將y*1=1，y*2=3代入對偶約束條件，（1）（2）（5）式為緊約束，（3）（4）為松約束。令原問題的最優(yōu)解為X*=（x1.x2.x3.x4.x5），則根據(jù)互補(bǔ)松弛條件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）解：對偶問題為第二節(jié)對偶問題的基本性質(zhì)第三十頁，共九十四頁，2022年，8月28日

又由于y*1＞0，y*2

＞0，原問題的約束必為等式，即化簡為此方程組為無窮多解令x5=0,得到x1=1，x2=2即X*1=（）為原問題的一個(gè)最優(yōu)解，Z=11。再令x5=2/3，得到x1=5/3，x2=0即X*2

（）也是原問題的一個(gè)最優(yōu)解，Z=11。第二節(jié)對偶問題的基本性質(zhì)第三十一頁，共九十四頁，2022年，8月28日例:已知線性規(guī)劃問題及其對偶問題maxz=2x1+3x2+0x3+0x4+0x52x1+2x2+x3=12y14x1+x4=16y25x2+x5=15y3xj≥0minw=-12y1-16y2-15y3+0y4+0y5-2y1-4y2+y4=-2x1-2y1-5y3+y5=-3x2yi≥0分別求解，得到如下兩個(gè)最優(yōu)單純形表。第二節(jié)對偶問題的基本性質(zhì)第三十二頁，共九十四頁，2022年，8月28日

基b原問題變量原問題松弛變量x1x2x3x4x5x13101/20-1/5x4400-214/5x2301001/500101/5變量對偶問題的剩余變量對偶問題變量y4y5y1y2y3

基b對偶問題變量對偶問題的剩余變量y1y2y3

y4y5y11120-1/20y21/50-4/511/5-1/504033變量原問題松弛變量原問題變量x3x4x5

x1x2第二節(jié)對偶問題的基本性質(zhì)第三十三頁，共九十四頁，2022年，8月28日w1wiwmwm+1wm+jwn+m

x1xjxnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量

原始問題的變量原始問題的松弛變量xjwm+j=0，wixn+i=0(i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個(gè)大于0，另一個(gè)一定等于0第二節(jié)對偶問題的基本性質(zhì)第三十四頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法

我們前面介紹的一般單純形法，是從“可行”(右端項(xiàng)非負(fù)）開始，逐步地迭代運(yùn)算，直到得出最優(yōu)解。而應(yīng)用對偶規(guī)劃的性質(zhì)，可以找到一種求解線性規(guī)劃的新方法——對偶單純形法。對偶單純形法則是從“不可行”(右端項(xiàng)含負(fù)）開始，在保持最優(yōu)性之下逐步迭代，直到不可行變?yōu)榭尚?，即得到可行最?yōu)解為止。當(dāng)對偶問題的約束條件的數(shù)目較原問題為少時(shí)，應(yīng)用對偶單純形法求解較為方便。第三十五頁，共九十四頁，2022年，8月28日例：用對偶單純形法解下列線性規(guī)劃問題

minw=12y1+16y2+15y3s.t.2y1+4y222y1+5y3

3y1，y2，

y30解：此題可用人工變量方法求，但也可用對偶單純形法。

maxw’=-12y1-16y2–15y3s.t.-2y1-4y2+y4=-2-2y1-5y3+y5=-3y1，y2，

y3，y4，y5

0第三節(jié)對偶單純形法第三十六頁，共九十四頁，2022年，8月28日列初始單純形表Cj－12－16－1500CBXBby1y2y3y4y500y4y5-2-3-2-2-400[-5]1001-12-16-1500第三節(jié)對偶單純形法第三十七頁，共九十四頁，2022年，8月28日Cj－12－16－1500CBXBby1y2y3y4y500y4y5-2-3-2-2-400[-5]1001-12-16-15000-15y4y3-23/5[-2]2/5-4001100-1/5-6-1600-3第三節(jié)對偶單純形法第三十八頁，共九十四頁，2022年，8月28日Cj－12－16－1500CBXBby1y2y3y4y500y4y5-2-3-2-2-400[-5]1001-12-16-15000-15y4y3-23/5[-2]2/5-4001100-1/5-6-1600-3-12-15y1y311/5102-4/501-1/21/50-1/50-40-3-3Y*=(1,0,1/5,0,0)第三節(jié)對偶單純形法第三十九頁，共九十四頁，2022年，8月28日例：用對偶單純形法求解：解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因?yàn)閷ε紗栴}可行，即全部檢驗(yàn)數(shù)≤0（求max問題）。第三節(jié)對偶單純形法第四十頁，共九十四頁，2022年，8月28日cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14(-9/-1.-12/-1.

-15/-5)λj-9-12-150000第三節(jié)對偶單純形法第四十一頁，共九十四頁，2022年，8月28日cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14第三節(jié)對偶單純形法第四十二頁，共九十四頁，2022年，8月28日cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原問題的最優(yōu)解為：X*=（2,2,2,0,0,0），Z*=72其對偶問題的最優(yōu)解為：Y*=（1/3,3,7/3），W*=72第三節(jié)對偶單純形法第四十三頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法例:用對偶單純形法解下列線性規(guī)劃問題

minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x4

2x1，x2，

x3，x40解：用對偶單純形法。

maxS’=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=-2x1，x2，

x3，x4，x5

，x6

0第四十四頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法計(jì)算檢驗(yàn)數(shù)全為非正，稱為對偶可行；而常數(shù)項(xiàng)全是負(fù)數(shù)，稱為原始不可行。常數(shù)項(xiàng)是負(fù)數(shù)且最小，確定出基變量x5。第四十五頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法用出基變量x5行的所有負(fù)數(shù)分別去除對應(yīng)的檢驗(yàn)數(shù)，最小值對應(yīng)的為進(jìn)基變量x1，交叉元素為主元（-1）主元運(yùn)算：第一行乘（-1）第四十六頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法主元運(yùn)算：第二行加上第一行（-2）計(jì)算檢驗(yàn)數(shù)第四十七頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法確定出基變量X6確定進(jìn)基變量X3，主元（-2）第四十八頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法主元運(yùn)算：第二行乘（-1/2）主元運(yùn)算：第一行加第二行第四十九頁，共九十四頁，2022年，8月28日第三節(jié)對偶單純形法計(jì)算檢驗(yàn)數(shù)：全為非正。但此時(shí)常數(shù)b已全大于零，最優(yōu)解=（7，0，4，0）最優(yōu)值S’=-7S=7第五十頁，共九十四頁，2022年，8月28日例:用對偶單純形法解下列線性規(guī)劃問題

minS=x1+2x2s.t.-x1+2x2-x3

1-x1-2x2+x36x1，x2，

x30解：將原問題化成

maxS’=-x1-2x2s.t.x1-2x2+x3+x4=-1x1+2x2-x3+x5=-6x1，x2，

x3，x4，x5

0第三節(jié)對偶單純形法第五十一頁，共九十四頁，2022年，8月28日常數(shù)項(xiàng)最小出基變量X5，按比值無法比較。常數(shù)項(xiàng)次小出基變量X4，按比值X2為進(jìn)基變量。主元（-2）第三節(jié)對偶單純形法第五十二頁，共九十四頁，2022年，8月28日主元運(yùn)算：第一行乘（-1/2）主元運(yùn)算：第二行加第一行（-2）第三節(jié)對偶單純形法第五十三頁，共九十四頁，2022年，8月28日計(jì)算檢驗(yàn)數(shù)：全小于零。但常數(shù)項(xiàng)為負(fù)數(shù)的行元素全大于零，原問題無可行解。第三節(jié)對偶單純形法第五十四頁，共九十四頁，2022年，8月28日例:用對偶單純形法解下列線性規(guī)劃問題解：先化為標(biāo)準(zhǔn)型

約束條件兩邊同乘(-1)第三節(jié)對偶單純形法第五十五頁，共九十四頁，2022年，8月28日Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[-6]-2-1-11001-15-24-500第三節(jié)對偶單純形法第五十六頁，共九十四頁，2022年，8月28日Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[-6]-2-1-11001-15-24-500---45-240x2x51/3-1/30-5101/6[-2/3]-1/6-1/301-150-1-40第三節(jié)對偶單純形法第五十七頁，共九十四頁，2022年，8月28日Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[-6]-2-1-11001-15-24-500---45-240x2x51/3-1/30-5101/6[-2/3]-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)’Y*=(7/2,3/2)第三節(jié)對偶單純形法第五十八頁，共九十四頁，2022年，8月28日①單純形表檢驗(yàn)數(shù)行全部非正（對偶可行）②變量取值可有負(fù)數(shù)（非可行解）注：通過矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。應(yīng)用前提：有一個(gè)基，其對應(yīng)的基滿足:第三節(jié)對偶單純形法第五十九頁，共九十四頁，2022年，8月28日對偶單純形法與原始單純形法的對應(yīng)關(guān)系原始單純形法對偶單純形法前提條件所有bi≥0所有bi≥0?最優(yōu)性檢驗(yàn)所有所有換入、出基變量的確定先確定換入基變量后確定換出基變量先確定換出基變量后確定換入基變量原始基本解的進(jìn)化可行最優(yōu)非可行可行(最優(yōu))第三節(jié)對偶單純形法第六十頁，共九十四頁，2022年，8月28日靈敏度分析一詞的含義是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。在前面所講的線性規(guī)劃問題都假定了各系數(shù)cj,

aij,

bi等始終保持不變，是已知常數(shù)。而實(shí)際當(dāng)中，這些系數(shù)通常是一些估計(jì)或預(yù)測數(shù)字。如果外界條件發(fā)生了變化，這些系數(shù)也會發(fā)生相應(yīng)變化，這樣以來，就會引出一些問題：——這些系數(shù)中，如果有一些發(fā)生變化，問題的最優(yōu)解會發(fā)生怎樣的變化？——如果發(fā)生變化，又將使用何種簡便方法求出新的最優(yōu)解？第四節(jié)靈敏度分析第六十一頁，共九十四頁，2022年，8月28日例：線性規(guī)劃及最優(yōu)單純形表如下maxw=2x1+3x2+x31/3x1+1/3x2+1/3x3≤

11/3x1+4/3x2+7/3x3≤3

x1,x2,x3≥0價(jià)值系數(shù)c發(fā)生變化第四節(jié)靈敏度分析第六十二頁，共九十四頁，2022年，8月28日可得到Δc3≤3時(shí)，原最優(yōu)解不變。當(dāng)-3+Δc3≤0最優(yōu)解不變第四節(jié)靈敏度分析第六十三頁，共九十四頁，2022年，8月28日例：

線性規(guī)劃及最優(yōu)單純形表如下試求c3

在多大范圍內(nèi)變動時(shí)，原最優(yōu)解保持不變。cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5-8/5-1/5-28/5第四節(jié)靈敏度分析第六十四頁，共九十四頁，2022年，8月28日可得到Δc3≤9/5時(shí)，原最優(yōu)解不變。cj-2-3-4Δc300B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5+Δc3-8/5-1/5-28/5第四節(jié)靈敏度分析第六十五頁，共九十四頁，2022年，8月28日下表為最優(yōu)單純形表（考慮基變量系數(shù)c1發(fā)生變化）-3+Δc1

≤0-5-4Δc1≤0-1+Δc1≤0最優(yōu)解不變可得到-5/4≤ΔC1≤1時(shí)，原最優(yōu)解不變。最優(yōu)值將會出現(xiàn)相應(yīng)的變化。第四節(jié)靈敏度分析第六十六頁，共九十四頁，2022年，8月28日MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5≥0例第四節(jié)靈敏度分析第六十七頁，共九十四頁，2022年，8月28日下表為最優(yōu)單純形表（考慮基變量系數(shù)c2發(fā)生變化）可得到-3≤Δc2≤1時(shí)，原最優(yōu)解不變。第四節(jié)靈敏度分析第六十八頁，共九十四頁，2022年，8月28日例:已知線性規(guī)劃的標(biāo)準(zhǔn)形式為其最優(yōu)單純形表如下Cj－12100CBXBbX1x2x3x4x520x2x56101310111101-Z-12-30-1-20問：(1)當(dāng)C1由－1變?yōu)?時(shí)，求新問題的最優(yōu)解。

(2)討論C2在什么范圍內(nèi)變化時(shí)，原有的最優(yōu)解仍是最優(yōu)解。第四節(jié)靈敏度分析第六十九頁，共九十四頁，2022年，8月28日解：由表可知，C1是非基變量的價(jià)值系數(shù)，因此C1的改變只影響σ1，可見最優(yōu)性準(zhǔn)則已不滿足，繼續(xù)迭代Cj42100CBXBbx1x2x3x4x520x2x56101[3]10111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/3第四節(jié)靈敏度分析第七十頁，共九十四頁，2022年，8月28日（2）要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下滿足σ≤0成立，因?yàn)閤2是基變量，所以所有的σ值都將發(fā)生變化，即

則△c2≥-1，所以當(dāng)x2的系數(shù)△c2≥-1時(shí)，原最優(yōu)解仍能保持為最優(yōu)解。－3－△c2≤0－１－△c2≤0－２－△c2≤0第四節(jié)靈敏度分析第七十一頁，共九十四頁，2022年，8月28日例：

線性規(guī)劃及最優(yōu)單純形表如下，問b3由12變?yōu)?2+Δb3最優(yōu)性不變。MaxZ=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=164x2+x5=

12+Δb3

x1,x2,x3,x4,x5≥02、右端項(xiàng)b

發(fā)生變化第四節(jié)靈敏度分析第七十二頁，共九十四頁，2022年，8月28日第四節(jié)靈敏度分析第七十三頁，共九十四頁，2022年，8月28日比如第三個(gè)式子中，由4+Δb3≥0，解得Δb3≥-4

時(shí)最優(yōu)性不變第四節(jié)靈敏度分析第七十四頁，共九十四頁，2022年，8月28日若Δb3=-8，則4+（-8）=-4<0，改變了最優(yōu)性，只要再繼續(xù)迭代即可。第四節(jié)靈敏度分析第七十五頁，共九十四頁，2022年，8月28日例：線性規(guī)劃及最優(yōu)單純形表如下。求當(dāng)b1在由8變動為12時(shí)，原最優(yōu)性是否保持不變，若變動求出新的最優(yōu)解。Ci23000B-1bCBXBx1x2x3x4x52

x1

1001/4040

x5

00-21/2143

x2

011/2-1/802σj00-3/2-1/8014第四節(jié)靈敏度分析第七十六頁，共九十四頁，2022年，8月28日第四節(jié)靈敏度分析第七十七頁，共九十四頁，2022年，8月28日將b’代入原最優(yōu)單純形表中，運(yùn)用對偶單純形法計(jì)算最優(yōu)解。Ci23000B-1bCBXBx1x2x3x4x52

x1

1001/4040

x5

00-21/21-43

x2

011/2-1/804σj00-3/2-1/8014第四節(jié)靈敏度分析第七十八頁，共九十四頁，2022年，8月28日將b’代入原最優(yōu)單純形表中，運(yùn)用對偶單純形法計(jì)算最優(yōu)解。經(jīng)一次迭代后，求得新的最優(yōu)解:(43200)TCi23000B-1bCBXBx1x2x3x4x52

x1

1001/4040

x5

00-21/21-43

x2

011/2-1/804σj00-3/2-1/8014θ3/42

x1

1001/4040

x3

001-1/4-1/223

x2

01001/43σj000-1/2-3/417第四節(jié)靈敏度分析第七十九頁，共九十四頁，2022年，8月28日例：

常山機(jī)械廠生產(chǎn)Ⅰ和Ⅱ兩種產(chǎn)品。生產(chǎn)中需使用A、B、C三種設(shè)備進(jìn)行加工，加工每件Ⅰ產(chǎn)品或Ⅱ產(chǎn)品所需的設(shè)備機(jī)時(shí)數(shù)、利潤值及每種設(shè)備可利用機(jī)時(shí)數(shù)列于下表，請問：充分利用設(shè)備機(jī)臺時(shí)，工廠應(yīng)生產(chǎn)Ⅰ和Ⅱ產(chǎn)品各多少件才能獲得最大利潤？試列出相應(yīng)的線性規(guī)劃數(shù)學(xué)模型。ABC產(chǎn)品利潤／（元／件）Ⅰ2402Ⅱ205