單純形法的靈敏度分析與對偶課件

第六章*單純形法的靈敏度分析與對偶單純形表的靈敏度分析線性規(guī)劃的對偶問題對偶單純形法整理課件第六章*單純形法的靈敏度分析與對偶單純形表的靈敏度分析整1第六章*單純形法的靈敏度分析與對偶如何利用最優(yōu)單純形表進(jìn)行靈敏度分析。。整理課件第六章*單純形法的靈敏度分析與對偶如何利用最優(yōu)單純形表進(jìn)2單純形表--求解結(jié)果：迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件單純形表--求解結(jié)果：迭代次數(shù)基變量CBx1X2s1s2S33第1節(jié)單純形表的靈敏度分析一.目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析現(xiàn)要利用單純形表法來進(jìn)行Ck的靈敏度分析。由于目標(biāo)函數(shù)變量分為基與非基變量，故討論時(shí),分兩類來討論。1.在最終的單純形表里,xK非基變量.2.在最終的單純形表里,xK基變量.整理課件第1節(jié)單純形表的靈敏度分析一.目標(biāo)函數(shù)中變量系數(shù)C4第1節(jié)單純形表的靈敏度分析1.在最終的單純形表里,xK非基變量。

由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK沒有任何關(guān)系，所以當(dāng)CK變?yōu)镃K

+△CK時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閤K

是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB

不變，可知ZK

也不變，只是CK變?yōu)镃K

+△CK

。這時(shí)σK=CK－ZK

變成了CK

+△CK－ZK=σK+△CK

.要使得原來的最優(yōu)解仍為最優(yōu)解，只要σK+△CK≤0即可，也就是

△CK≤－σK

即可。整理課件第1節(jié)單純形表的靈敏度分析1.在最終的單純形表里,xK5第1節(jié)單純形表的靈敏度分析２.在最終的單純形表里,xK為基變量。

由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK沒有任何關(guān)系，所以當(dāng)CK變?yōu)镃K

+△CK時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，但基變量在目標(biāo)函數(shù)的系數(shù)CB變了，則Zj

也變了，相應(yīng)地，σＪ也變了。變化規(guī)律為：整理課件第1節(jié)單純形表的靈敏度分析２.在最終的單純形表里,xK6目標(biāo)函數(shù)：max z=50x1+100x2x1+x2≤3002x1+x2≤400x1≥0,x2≥0s.t.x2≤250max z=50x1+100x2x1+x2+s1=3002x1+x2+s2=400x1≥0,x2≥0,si≥0s.t.x2+s3=250整理課件目標(biāo)函數(shù)：x1+x2≤3002x1+x2≤400x1≥07一、線性規(guī)劃問題解的基本概念基及基本解:max z=50x1+100x2+0s1+0s2+0s31x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=400x1≥0,x2≥0,s1≥0，s2≥0，s3≥0s.t.0x1+1x2+0s1+0s2+1s3=250整理課件一、線性規(guī)劃問題解的基本概念基及基本解:max z=50x18表解形式的單純形法例子:整理課件表解形式的單純形法例子:整理課件9初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值5010（１）先分析非基變量s1:c3σ3

由于是非基變量，故套用公式（1）

當(dāng)△C3≤-σ3,時(shí)最優(yōu)解不變;已知σ3=-50,△C3≤－（－50）=50；c’=c+△C<=0+50=50最優(yōu)解不變。整理課件（１）先分析非基變量s1:c3σ3當(dāng)△C3≤-σ11（2）再分析基變量的系數(shù)分析：從表中獲得了:a11=1,a12=0,a13=1,a14=0,a15=-1例如對基變量X1的系數(shù)C1進(jìn)行靈敏度分析：整理課件（2）再分析基變量的系數(shù)分析：從表中獲得了:例如對基變量X112單純形表靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-500---50L--50R縮小區(qū)間整理課件單純形表靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b513故，max{-50}≤△C1≤min{50}，左半徑和右半徑[保證區(qū)間半徑最小]則當(dāng)-50≤△C1≤50時(shí)最優(yōu)解不變，即x1的目標(biāo)函數(shù)系數(shù)C’有：50-50=c1+L≤C‘=C1+△C1≤c1+R=50+50，0≤C‘≤100時(shí)，最優(yōu)解不變。整理課件故，max{-50}≤△C1≤min{50}，左半徑和右半14

**********************最優(yōu)解如下*************************目標(biāo)函數(shù)最優(yōu)值為:27500

變量最優(yōu)解相差值

-----------------------x1500x22500

約束松弛/剩余變量對偶價(jià)格

----------------------------10

5025003050

目標(biāo)函數(shù)系數(shù)范圍:

變量下限當(dāng)前值上限

-------------------------------x1050100x250100無上限常數(shù)項(xiàng)數(shù)范圍:

約束下限當(dāng)前值上限

-------------------------------12503003252350400無上限

3200250300整理課件**********************最優(yōu)解如下**15LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)27500.00VARIABLEVALUEREDUCEDCOSTX150.0000000.000000X2250.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000050.0000003)50.0000000.0000004)0.00000050.000000NO.ITERATIONS=2RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLE

COEFINCREASEDECREASE

X150.00000050.00000050.000000X2100.000000INFINITY50.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.00000025.00000050.0000003400.000000INFINITY50.0000004250.00000050.00000050.000000整理課件LPOPTIMUMFOUNDATSTEP16二、基于單純形法的約束方程右邊常數(shù)靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150臺時(shí)S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件二、基于單純形法的約束方程右邊常數(shù)靈敏度分析迭代次數(shù)基變量C17二、約束方程右邊常數(shù)靈敏度分析從上頁表中我們,知道了右邊系數(shù)bj的靈敏度,對偶價(jià)格不變與bj變化范圍.現(xiàn)要從單純形表的數(shù)據(jù)進(jìn)行分析：

Zj的值剛好是對偶價(jià)格.那么，當(dāng)bj變?yōu)閎j+△b時(shí),非基變量的檢驗(yàn)數(shù)不變,但基變量的檢驗(yàn)數(shù)會變。bk允許范圍為:整理課件二、約束方程右邊常數(shù)靈敏度分析從上頁表中我們,知道了右邊系數(shù)18二、約束方程右邊常數(shù)靈敏度分析那么，當(dāng)br變?yōu)閎r+△br時(shí),非基變量的檢驗(yàn)數(shù)不變,但基變量的檢驗(yàn)數(shù)會變.△br允許范圍為:整理課件二、約束方程右邊常數(shù)靈敏度分析那么，當(dāng)br變?yōu)閎r+△br時(shí)19初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值5020現(xiàn)對b1進(jìn)行靈敏度分析,先要找出b1的列元素:它就是S1.因?yàn)榭赡婢仃嘊的第一列為S1=(1,-2,0)TMax{-50/1}=-50≤△b1≤min{-50/-2}=25-50≤△b1≤+25那么,300-50≤b’=b+△b1≤300+25250≤b’=b+△b1≤325練習(xí)：分析B3整理課件現(xiàn)對b1進(jìn)行靈敏度分析,先要找出b1的列元素:它就是S1.因21三、約束方程系數(shù)矩陣A靈敏度分析技術(shù)系數(shù)aij發(fā)生變化時(shí)對線性規(guī)劃最優(yōu)解結(jié)構(gòu)的影響比較復(fù)雜。從下式中可知，非基變量的檢驗(yàn)數(shù)和基變量XB的值都與技術(shù)系數(shù)有關(guān)。通常把技術(shù)系數(shù)aij的靈敏度分析分為如下三類：（1）對應(yīng)基變量的AIJ，且資源BI已全部用完；（2）對應(yīng)基變量的AIJ，但資源BI未用完；（3）對應(yīng)非基變量的AIJ，且資源BI全部用完或未用完；整理課件三、約束方程系數(shù)矩陣A靈敏度分析技術(shù)系數(shù)ai22三、約束方程系數(shù)矩陣A靈敏度分析線性規(guī)劃最優(yōu)解結(jié)構(gòu)不變的條件是（1）對應(yīng)基變量的aij，且資源Bi已全部用完，則技術(shù)系數(shù)變化范圍為：△aij=0;（2）對應(yīng)基變量的aij，但資源bi未用完,則技術(shù)系數(shù)變化范圍為：－∞≤△aij≤Xn+i/xj（3）對應(yīng)非基變量的aij，且資源bi全部用完或未用完,我們要分以下兩種情況討論：（A）△aij>0,不會破壞最優(yōu)解。（B）△aij<0，要使原線性規(guī)劃最優(yōu)解不變條件：必須保證該非基變量的檢驗(yàn)數(shù)仍小于0，即cj-Zj≤0整理課件三、約束方程系數(shù)矩陣A靈敏度分析線性規(guī)劃最優(yōu)解結(jié)構(gòu)不變的條件23第2節(jié)線性規(guī)劃的對偶問題某工廠在計(jì)劃安排I,II兩種產(chǎn)品,III資源限制設(shè)備A11300臺時(shí)設(shè)備B21400設(shè)備C01250生產(chǎn)I可獲得50元,II可獲得100元,如何安排生產(chǎn),獲得MAX?整理課件第2節(jié)線性規(guī)劃的對偶問題某工廠在計(jì)劃安排I,II兩種產(chǎn)品,24模型目標(biāo):maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250x1,x2>=0整理課件模型目標(biāo):maxz=50x1+100x2整理課件25假設(shè)現(xiàn)在有一個(gè)公司要租用工廠設(shè)備，那么工廠獲取利潤有兩種方法，一是自己生產(chǎn)，二是出租設(shè)備資源。自己生產(chǎn)已有模型。那么，如果出租，那么如何構(gòu)建模型？設(shè)備價(jià)格為Ay1,By2,Cy3;

則目標(biāo):minf=300y1+400y2+250y3s.t.y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0整理課件假設(shè)現(xiàn)在有一個(gè)公司要租用工廠設(shè)備，那么工廠獲取利潤有兩種方法26目標(biāo):minf=300y1+400y2+250y3s.t.Y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0目標(biāo):maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250

x1,x2>=0原問題對偶問題整理課件目標(biāo):minf=300y1+400y2+250y3目標(biāo):271.求目標(biāo)函數(shù)最大問題中有n個(gè)變量,m個(gè)約束條件,它的約束條件都是小于等于不等式;其對偶則是m個(gè)變量,n個(gè)約束條件,并且是大于等于不等式;2.原問題的目標(biāo)函數(shù)系數(shù)C是對偶問題中的約束條件B

ci=bi3.原問題右邊系數(shù)B成為對偶問題的目標(biāo)系數(shù)C,bi=ci4.對偶問題的約束條件系數(shù)矩陣A是原問題的AT整理課件1.求目標(biāo)函數(shù)最大問題中有n個(gè)變量,m個(gè)約束條件,它的約束條28整理課件整理課件29整理課件整理課件30原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)系數(shù)矩陣AT價(jià)值系數(shù)C右端項(xiàng)b右端項(xiàng)b價(jià)值系數(shù)C第i行約束條件為≤型對偶變量yi≥0第i行約束條件為≥型對偶變量yi≤0第i行約束條件為=型對偶變量yi正負(fù)不限決策量xj≥0第j行約束條件為≥型決策量xj≤0第j行約束條件為≤型決策量xj正負(fù)不限第j行約束條件為=型整理課件原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)31轉(zhuǎn)化例子：Maxf=3x1+4x2+6x3+4x4x1+4x2+2x3-3x4≤353x1+x2+5x3+6x4≤45x1,x2,x3,x4≥0Ming(y)=35y1+45y2Y1+3y2≥34y1+y2≥42y1+5y2≥6-3y1+6y2≥4Y1,y2≥0整理課件轉(zhuǎn)化例子：Ming(y)=35y1+45y2整理課件32目標(biāo):minf=300y1+400y2+250y3s.t.Y1+2y2≥50y1+y2+y3≥100y1,y2,y3≥0目標(biāo):maxz=50x1+100x2S.t.x1+x2≤3002x1+x2≤400x2≤250

x1,x2≥0原問題對偶問題整理課件目標(biāo):目標(biāo):原問題對偶問題整理課件33Max-f=-300y1-400y2-250y3-Ma1y1+2y2-s1+a1=50y1+y2+y3-s2=100y1,y2,y3,s1,s2,a1>0對偶單純形法求解：整理課件Max-f=-300y1-400y2-250y3-Ma1對34初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0a1-M120-10150y3-2501110-10100Zj-M-250-2M-250-250M250-M-50M-2500Cj-ZjM-502M-1500-M-2500②整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-335初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0y2-4001/210-1/201/225y3-2501/2011/2-1-1/275Zj-325-400-25075250-75-28750Cj-Zj2500-75-250-M+75(1/2)整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-336初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0y1-300120-10150y3-2500-111-1-150Zj-300-350-25050250-50-27500Cj-Zj0-500-50-250-M+50(1/2)最優(yōu)解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值為-27500,即目標(biāo)f的最小值為:27500A設(shè)備租金為50元,B設(shè)備租金為0元,C設(shè)備租金為50元;整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-337二.任意形式的對偶問題

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤4406x1-4x2-x3≥1005x1-3x2+x3=200x1,x2,x3≥0整理課件二.任意形式的對偶問題整理課件38二.任意形式的對偶問題

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≥200

5x1-3x2+x3≤200x1,x2,x3≥05x1-3x2+x3=200整理課件二.任意形式的對偶問題5x1-3x2+x3=20039maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≤200-5x1+3x2-x3≤-200

x1,x2,x3≥0s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0minf=440y1-100y2+200y3-200y4二.任意形式的對偶問題對偶問題整理課件maxZ=3x1+4x2+6x3s.t.minf=440原問題的對偶問題為

minf=440y1-100y2+200y3-200y4s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0整理課件原問題的對偶問題為整理課件41原問題的對偶問題為

minf=440y1-100y2+200(y3-y4)s.t.2y1-6y2+5(y3-y4)≥33y1+4y2+3(y3-y4)≥4

6y1+y2+(y3-y4)≥6y1,y2,y3,y4≥0整理課件原問題的對偶問題為整理課件42原問題的對偶問題為

minf=440y1-100y2+200s3s.t.2y1-6y2+5s3≥33y1+4y2+3s3≥4

6y1+y2+s3≥6y1,y2≥0,S3無非負(fù)限制整理課件原問題的對偶問題為整理課件43練習(xí)：Maxf(x)=4x1+5x2s.t.3x1+2x2≤204x1-3x2≥10

x1+x2=5x2≥0,x1正負(fù)不限整理課件練習(xí)：整理課件44練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2=5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件45練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2≥5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件46練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-(4x11-4x12-3x2)≤-10

-(x11-x12+x2)≤-5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件47練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-4x11+4x12+3x2≤-10

-x11+x12-x2≤-5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件48練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理課件練習(xí)轉(zhuǎn)換：整理課件49練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5(y3-y4)s.t.

3y1-4y2-(y3-y4)>=4-3y1+4y2+(y3-y4)>=-42y1+3y2-(y3-y4)>=5y1,y2,y3,y4>=0整理課件練習(xí)轉(zhuǎn)換：整理課件50練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5y3s.t.

3y1-4y2-y3>=4-3y1+4y2+y3>=-42y1+3y2-y3>=5y1,y2>=0，y3無限制整理課件練習(xí)轉(zhuǎn)換：整理課件51練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5y3s.t.

3y1-4y2-y3=42y1+3y2-y3>=5y1,y2>=0，y3無限制整理課件練習(xí)轉(zhuǎn)換：整理課件52練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理課件練習(xí)轉(zhuǎn)換：整理課件53練習(xí)答案：Minh(y)=20y1+10y2+5y3s.t.3y1+4y2+y3=42y1-3y2+y3≥5y1≥0,y2≤0,y3不限整理課件練習(xí)答案：整理課件54原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)系數(shù)矩陣AT價(jià)值系數(shù)C右端項(xiàng)b右端項(xiàng)b價(jià)值系數(shù)C第i行約束條件為≤型對偶變量yi≥0第i行約束條件為≥型對偶變量yi≤0第i行約束條件為=型對偶變量yi正負(fù)不限決策量xj≥0第j行約束條件為≥型決策量xj≤0第j行約束條件為≤型決策量xj正負(fù)不限第j行約束條件為=型整理課件原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)55第3節(jié)對偶單純形法對偶單純法和單純形法一樣都是求解原線性規(guī)劃問題的一種方法.單純形法是在保持原問題的所有約束條件的bj都大于0的情況下,通過迭代,使得所有檢驗(yàn)數(shù)都小于等于0,最后求得最優(yōu)解;而對偶單純形法則是在保持原問題的所有檢驗(yàn)數(shù)都小于等于0的情況下,通過迭代,使得所有約束條件的常數(shù)都大于等于0,最后求得最優(yōu)解。整理課件第3節(jié)對偶單純形法對偶單純法和單純形法一樣都是求解原線性規(guī)56第3節(jié)對偶單純形法例，用對偶單純形法求解如下線性規(guī)劃問題：Minf=x1+5x2+3x4s.t.X1+2x2-x3+x4≥6-2x1-x2+4x3+x4≥4x1,x2,x3,x4>=0整理課件第3節(jié)對偶單純形法例，用對偶單純形法求解如下線性規(guī)劃問題：57第3節(jié)對偶單純形法例，用對偶單純形法求解如下線性規(guī)劃問題：將上述線性規(guī)劃問題變換為如下適合對偶單純形法的形式：Maxz=-f=-x1-5x2-3x4s.t.-X1-2x2+x3-x4+x5=-62x1+x2-4x3-x4+x6=-4x1,x2,x3,x4,x5,x6>=0x5,x6為剩余變量整理課件第3節(jié)對偶單純形法例，用對偶單純形法求解如下線性規(guī)劃問題：58初始單純形表迭代次數(shù)基變量CBx1x2x3x4x5x6b比值-1-50-3000x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300②X=(0,0,0,0,-6,-4)是基本解，但不是基本可行解，不可行。整理課件初始單純形表迭代次數(shù)基變量CBx1x2x3x4x5x6b-159（1）確定出基變量：min{bi|bi<0}=min{-6,-4}=-6

=b1,所以第L=1行為主行，x5出基變量。

（2）入基變量:所以第K=1列為主列，第1列的變量X1為入基變量。整理課件（1）確定出基變量：min{bi|bi<0}=min{-6,60迭代次數(shù)基變量CBx1x2x3x4x5x6b比值-1-50-3000x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300(-1)整理課件迭代次數(shù)基變量CBx1x2x3x4x5x6b-1-50-3061迭代次數(shù)基變量CBx1x2x3x4x5x6b比值-1-50-3000x1-112-11-106x600-3-2-321-16Zj-1-21-110-6Cj-Zj0-3-1-2-10(-2)整理課件迭代次數(shù)基變量CBx1x2x3x4x5x6b-1-50-3062迭代次數(shù)基變量CBx1x2x3x4x5x6b比值-1-50-3000x1-117/205/2-2-1/214x3003/213/2-1-1/28Zj-1-7/20-5/221/2Z=-14Cj-Zj0-3/20-1/2-2-1/2(-2)X=(x1,x2,x3,x4,x5,x6)=(14,0,8,0,0,0)滿足可行性檢驗(yàn)，所以上述X是原線性規(guī)劃的最優(yōu)解。最優(yōu)值：f=-g(X0=-(-14)=14整理課件迭代次數(shù)基變量CBx1x2x3x4x5x6b-1-50-3063對偶單純形法的步驟：1。求一個(gè)滿足最優(yōu)檢驗(yàn)條件的初始基本解，列出初始單純形表；2?？尚行詸z驗(yàn)，若所有的右系數(shù)均大于0，則已得最優(yōu)解，停止運(yùn)算，否則，轉(zhuǎn)33。求另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解；（1）確定出變量：找出bi中的最小者，確定行號及變量；（2）確定入變量：最小比原則min(σj/aij}定出列號；若找不到，則原規(guī)劃問題的解無界解，停止運(yùn)算，否則轉(zhuǎn)步驟（3）（3）以主元alk為中心，迭代，單位化，得到新的基本解，讓其接近基本可行解。再轉(zhuǎn)2；整理課件對偶單純形法的步驟：整理課件64第六章*單純形法的靈敏度分析與對偶單純形表的靈敏度分析線性規(guī)劃的對偶問題對偶單純形法整理課件第六章*單純形法的靈敏度分析與對偶單純形表的靈敏度分析整65第六章*單純形法的靈敏度分析與對偶如何利用最優(yōu)單純形表進(jìn)行靈敏度分析。。整理課件第六章*單純形法的靈敏度分析與對偶如何利用最優(yōu)單純形表進(jìn)66單純形表--求解結(jié)果：迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件單純形表--求解結(jié)果：迭代次數(shù)基變量CBx1X2s1s2S367第1節(jié)單純形表的靈敏度分析一.目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析現(xiàn)要利用單純形表法來進(jìn)行Ck的靈敏度分析。由于目標(biāo)函數(shù)變量分為基與非基變量，故討論時(shí),分兩類來討論。1.在最終的單純形表里,xK非基變量.2.在最終的單純形表里,xK基變量.整理課件第1節(jié)單純形表的靈敏度分析一.目標(biāo)函數(shù)中變量系數(shù)C68第1節(jié)單純形表的靈敏度分析1.在最終的單純形表里,xK非基變量。

由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK沒有任何關(guān)系，所以當(dāng)CK變?yōu)镃K

+△CK時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閤K

是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB

不變，可知ZK

也不變，只是CK變?yōu)镃K

+△CK

。這時(shí)σK=CK－ZK

變成了CK

+△CK－ZK=σK+△CK

.要使得原來的最優(yōu)解仍為最優(yōu)解，只要σK+△CK≤0即可，也就是

△CK≤－σK

即可。整理課件第1節(jié)單純形表的靈敏度分析1.在最終的單純形表里,xK69第1節(jié)單純形表的靈敏度分析２.在最終的單純形表里,xK為基變量。

由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK沒有任何關(guān)系，所以當(dāng)CK變?yōu)镃K

+△CK時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，但基變量在目標(biāo)函數(shù)的系數(shù)CB變了，則Zj

也變了，相應(yīng)地，σＪ也變了。變化規(guī)律為：整理課件第1節(jié)單純形表的靈敏度分析２.在最終的單純形表里,xK70目標(biāo)函數(shù)：max z=50x1+100x2x1+x2≤3002x1+x2≤400x1≥0,x2≥0s.t.x2≤250max z=50x1+100x2x1+x2+s1=3002x1+x2+s2=400x1≥0,x2≥0,si≥0s.t.x2+s3=250整理課件目標(biāo)函數(shù)：x1+x2≤3002x1+x2≤400x1≥071一、線性規(guī)劃問題解的基本概念基及基本解:max z=50x1+100x2+0s1+0s2+0s31x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=400x1≥0,x2≥0,s1≥0，s2≥0，s3≥0s.t.0x1+1x2+0s1+0s2+1s3=250整理課件一、線性規(guī)劃問題解的基本概念基及基本解:max z=50x172表解形式的單純形法例子:整理課件表解形式的單純形法例子:整理課件73初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值5074（１）先分析非基變量s1:c3σ3

由于是非基變量，故套用公式（1）

當(dāng)△C3≤-σ3,時(shí)最優(yōu)解不變;已知σ3=-50,△C3≤－（－50）=50；c’=c+△C<=0+50=50最優(yōu)解不變。整理課件（１）先分析非基變量s1:c3σ3當(dāng)△C3≤-σ75（2）再分析基變量的系數(shù)分析：從表中獲得了:a11=1,a12=0,a13=1,a14=0,a15=-1例如對基變量X1的系數(shù)C1進(jìn)行靈敏度分析：整理課件（2）再分析基變量的系數(shù)分析：從表中獲得了:例如對基變量X176單純形表靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-500---50L--50R縮小區(qū)間整理課件單純形表靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b577故，max{-50}≤△C1≤min{50}，左半徑和右半徑[保證區(qū)間半徑最小]則當(dāng)-50≤△C1≤50時(shí)最優(yōu)解不變，即x1的目標(biāo)函數(shù)系數(shù)C’有：50-50=c1+L≤C‘=C1+△C1≤c1+R=50+50，0≤C‘≤100時(shí)，最優(yōu)解不變。整理課件故，max{-50}≤△C1≤min{50}，左半徑和右半78

**********************最優(yōu)解如下*************************目標(biāo)函數(shù)最優(yōu)值為:27500

變量最優(yōu)解相差值

-----------------------x1500x22500

約束松弛/剩余變量對偶價(jià)格

----------------------------10

5025003050

目標(biāo)函數(shù)系數(shù)范圍:

變量下限當(dāng)前值上限

-------------------------------x1050100x250100無上限常數(shù)項(xiàng)數(shù)范圍:

約束下限當(dāng)前值上限

-------------------------------12503003252350400無上限

3200250300整理課件**********************最優(yōu)解如下**79LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)27500.00VARIABLEVALUEREDUCEDCOSTX150.0000000.000000X2250.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000050.0000003)50.0000000.0000004)0.00000050.000000NO.ITERATIONS=2RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLE

COEFINCREASEDECREASE

X150.00000050.00000050.000000X2100.000000INFINITY50.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.00000025.00000050.0000003400.000000INFINITY50.0000004250.00000050.00000050.000000整理課件LPOPTIMUMFOUNDATSTEP80二、基于單純形法的約束方程右邊常數(shù)靈敏度分析迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002x1501010-150臺時(shí)S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件二、基于單純形法的約束方程右邊常數(shù)靈敏度分析迭代次數(shù)基變量C81二、約束方程右邊常數(shù)靈敏度分析從上頁表中我們,知道了右邊系數(shù)bj的靈敏度,對偶價(jià)格不變與bj變化范圍.現(xiàn)要從單純形表的數(shù)據(jù)進(jìn)行分析：

Zj的值剛好是對偶價(jià)格.那么，當(dāng)bj變?yōu)閎j+△b時(shí),非基變量的檢驗(yàn)數(shù)不變,但基變量的檢驗(yàn)數(shù)會變。bk允許范圍為:整理課件二、約束方程右邊常數(shù)靈敏度分析從上頁表中我們,知道了右邊系數(shù)82二、約束方程右邊常數(shù)靈敏度分析那么，當(dāng)br變?yōu)閎r+△br時(shí),非基變量的檢驗(yàn)數(shù)不變,但基變量的檢驗(yàn)數(shù)會變.△br允許范圍為:整理課件二、約束方程右邊常數(shù)靈敏度分析那么，當(dāng)br變?yōu)閎r+△br時(shí)83初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理課件初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值5084現(xiàn)對b1進(jìn)行靈敏度分析,先要找出b1的列元素:它就是S1.因?yàn)榭赡婢仃嘊的第一列為S1=(1,-2,0)TMax{-50/1}=-50≤△b1≤min{-50/-2}=25-50≤△b1≤+25那么,300-50≤b’=b+△b1≤300+25250≤b’=b+△b1≤325練習(xí)：分析B3整理課件現(xiàn)對b1進(jìn)行靈敏度分析,先要找出b1的列元素:它就是S1.因85三、約束方程系數(shù)矩陣A靈敏度分析技術(shù)系數(shù)aij發(fā)生變化時(shí)對線性規(guī)劃最優(yōu)解結(jié)構(gòu)的影響比較復(fù)雜。從下式中可知，非基變量的檢驗(yàn)數(shù)和基變量XB的值都與技術(shù)系數(shù)有關(guān)。通常把技術(shù)系數(shù)aij的靈敏度分析分為如下三類：（1）對應(yīng)基變量的AIJ，且資源BI已全部用完；（2）對應(yīng)基變量的AIJ，但資源BI未用完；（3）對應(yīng)非基變量的AIJ，且資源BI全部用完或未用完；整理課件三、約束方程系數(shù)矩陣A靈敏度分析技術(shù)系數(shù)ai86三、約束方程系數(shù)矩陣A靈敏度分析線性規(guī)劃最優(yōu)解結(jié)構(gòu)不變的條件是（1）對應(yīng)基變量的aij，且資源Bi已全部用完，則技術(shù)系數(shù)變化范圍為：△aij=0;（2）對應(yīng)基變量的aij，但資源bi未用完,則技術(shù)系數(shù)變化范圍為：－∞≤△aij≤Xn+i/xj（3）對應(yīng)非基變量的aij，且資源bi全部用完或未用完,我們要分以下兩種情況討論：（A）△aij>0,不會破壞最優(yōu)解。（B）△aij<0，要使原線性規(guī)劃最優(yōu)解不變條件：必須保證該非基變量的檢驗(yàn)數(shù)仍小于0，即cj-Zj≤0整理課件三、約束方程系數(shù)矩陣A靈敏度分析線性規(guī)劃最優(yōu)解結(jié)構(gòu)不變的條件87第2節(jié)線性規(guī)劃的對偶問題某工廠在計(jì)劃安排I,II兩種產(chǎn)品,III資源限制設(shè)備A11300臺時(shí)設(shè)備B21400設(shè)備C01250生產(chǎn)I可獲得50元,II可獲得100元,如何安排生產(chǎn),獲得MAX?整理課件第2節(jié)線性規(guī)劃的對偶問題某工廠在計(jì)劃安排I,II兩種產(chǎn)品,88模型目標(biāo):maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250x1,x2>=0整理課件模型目標(biāo):maxz=50x1+100x2整理課件89假設(shè)現(xiàn)在有一個(gè)公司要租用工廠設(shè)備，那么工廠獲取利潤有兩種方法，一是自己生產(chǎn)，二是出租設(shè)備資源。自己生產(chǎn)已有模型。那么，如果出租，那么如何構(gòu)建模型？設(shè)備價(jià)格為Ay1,By2,Cy3;

則目標(biāo):minf=300y1+400y2+250y3s.t.y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0整理課件假設(shè)現(xiàn)在有一個(gè)公司要租用工廠設(shè)備，那么工廠獲取利潤有兩種方法90目標(biāo):minf=300y1+400y2+250y3s.t.Y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0目標(biāo):maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250

x1,x2>=0原問題對偶問題整理課件目標(biāo):minf=300y1+400y2+250y3目標(biāo):911.求目標(biāo)函數(shù)最大問題中有n個(gè)變量,m個(gè)約束條件,它的約束條件都是小于等于不等式;其對偶則是m個(gè)變量,n個(gè)約束條件,并且是大于等于不等式;2.原問題的目標(biāo)函數(shù)系數(shù)C是對偶問題中的約束條件B

ci=bi3.原問題右邊系數(shù)B成為對偶問題的目標(biāo)系數(shù)C,bi=ci4.對偶問題的約束條件系數(shù)矩陣A是原問題的AT整理課件1.求目標(biāo)函數(shù)最大問題中有n個(gè)變量,m個(gè)約束條件,它的約束條92整理課件整理課件93整理課件整理課件94原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)系數(shù)矩陣AT價(jià)值系數(shù)C右端項(xiàng)b右端項(xiàng)b價(jià)值系數(shù)C第i行約束條件為≤型對偶變量yi≥0第i行約束條件為≥型對偶變量yi≤0第i行約束條件為=型對偶變量yi正負(fù)不限決策量xj≥0第j行約束條件為≥型決策量xj≤0第j行約束條件為≤型決策量xj正負(fù)不限第j行約束條件為=型整理課件原問題（max,≤)對偶問題(min,≥)技術(shù)系數(shù)矩陣A技術(shù)95轉(zhuǎn)化例子：Maxf=3x1+4x2+6x3+4x4x1+4x2+2x3-3x4≤353x1+x2+5x3+6x4≤45x1,x2,x3,x4≥0Ming(y)=35y1+45y2Y1+3y2≥34y1+y2≥42y1+5y2≥6-3y1+6y2≥4Y1,y2≥0整理課件轉(zhuǎn)化例子：Ming(y)=35y1+45y2整理課件96目標(biāo):minf=300y1+400y2+250y3s.t.Y1+2y2≥50y1+y2+y3≥100y1,y2,y3≥0目標(biāo):maxz=50x1+100x2S.t.x1+x2≤3002x1+x2≤400x2≤250

x1,x2≥0原問題對偶問題整理課件目標(biāo):目標(biāo):原問題對偶問題整理課件97Max-f=-300y1-400y2-250y3-Ma1y1+2y2-s1+a1=50y1+y2+y3-s2=100y1,y2,y3,s1,s2,a1>0對偶單純形法求解：整理課件Max-f=-300y1-400y2-250y3-Ma1對98初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0a1-M120-10150y3-2501110-10100Zj-M-250-2M-250-250M250-M-50M-2500Cj-ZjM-502M-1500-M-2500②整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-399初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0y2-4001/210-1/201/225y3-2501/2011/2-1-1/275Zj-325-400-25075250-75-28750Cj-Zj2500-75-250-M+75(1/2)整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-3100初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b比值-300-400-25000-M0y1-300120-10150y3-2500-111-1-150Zj-300-350-25050250-50-27500Cj-Zj0-500-50-250-M+50(1/2)最優(yōu)解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值為-27500,即目標(biāo)f的最小值為:27500A設(shè)備租金為50元,B設(shè)備租金為0元,C設(shè)備租金為50元;整理課件初始單純形表迭代次數(shù)基變量CBy1y2y3s1s2a1b-3101二.任意形式的對偶問題

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤4406x1-4x2-x3≥1005x1-3x2+x3=200x1,x2,x3≥0整理課件二.任意形式的對偶問題整理課件102二.任意形式的對偶問題

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≥200

5x1-3x2+x3≤200x1,x2,x3≥05x1-3x2+x3=200整理課件二.任意形式的對偶問題5x1-3x2+x3=200103maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≤200-5x1+3x2-x3≤-200

x1,x2,x3≥0s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0minf=440y1-100y2+200y3-200y4二.任意形式的對偶問題對偶問題整理課件maxZ=3x1+4x2+6x3s.t.minf=4104原問題的對偶問題為

minf=440y1-100y2+200y3-200y4s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0整理課件原問題的對偶問題為整理課件105原問題的對偶問題為

minf=440y1-100y2+200(y3-y4)s.t.2y1-6y2+5(y3-y4)≥33y1+4y2+3(y3-y4)≥4

6y1+y2+(y3-y4)≥6y1,y2,y3,y4≥0整理課件原問題的對偶問題為整理課件106原問題的對偶問題為

minf=440y1-100y2+200s3s.t.2y1-6y2+5s3≥33y1+4y2+3s3≥4

6y1+y2+s3≥6y1,y2≥0,S3無非負(fù)限制整理課件原問題的對偶問題為整理課件107練習(xí)：Maxf(x)=4x1+5x2s.t.3x1+2x2≤204x1-3x2≥10

x1+x2=5x2≥0,x1正負(fù)不限整理課件練習(xí)：整理課件108練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2=5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件109練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2≥5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件110練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-(4x11-4x12-3x2)≤-10

-(x11-x12+x2)≤-5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件111練習(xí)轉(zhuǎn)換：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-4x11+4x12+3x2≤-10

-x11+x12-x2≤-5

x11-x12+x2≤5x11,x12,x2≥0整理課件練習(xí)轉(zhuǎn)換：整理課件112練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理課件練習(xí)轉(zhuǎn)換：整理課件113練習(xí)轉(zhuǎn)換：Minf(y)=20y1-10y2-5(y3-y4)s.t.

3y1