單純形法的靈敏度分析與對偶.ppt

1、第六章* 單純形法的靈敏度分析與對偶,單純形表的靈敏度分析 線性規(guī)劃的對偶問題 對偶單純形法,第六章* 單純形法的靈敏度分析與對偶,如何利用最優(yōu)單純形表進行靈敏度分析。,單純形表-求解結(jié)果：,第1節(jié) 單純形表的靈敏度分析,一. 目標(biāo)函數(shù)中變量系數(shù) Ck靈敏度分析 現(xiàn)要利用單純形表法來進行Ck 的靈敏度分析。由于目標(biāo)函數(shù)變量分為基與非基變量，故討論時,分兩類來討論。 1.在最終的單純形表里, xK 非基變量. 2.在最終的單純形表里, xK 基變量.,第1節(jié) 單純形表的靈敏度分析,1.在最終的單純形表里, xK 非基變量。 由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK

2、沒有任何關(guān)系，所以當(dāng)CK 變?yōu)镃K +CK 時，在最終單純形表中其系數(shù)的增廣矩陣不變，又因為xK 是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB 不變，可知ZK 也不變，只是CK 變?yōu)镃K +CK 。這時K= CK ZK 變成了CK +CK ZK= K+ CK .要使得原來的最優(yōu)解仍為最優(yōu)解，只要K+ CK 0 即可，也就是 CK K 即可。,第1節(jié) 單純形表的靈敏度分析,.在最終的單純形表里, xK 為基變量。 由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與CK 沒有任何關(guān)系，所以當(dāng)CK 變?yōu)镃K +CK 時，在最終單純形表中其系數(shù)的增廣矩陣不變，但基變量在目標(biāo)函數(shù)的

3、系數(shù)CB變了，則Zj 也變了， 相應(yīng)地，也變了。變化規(guī)律為：,目標(biāo)函數(shù)： maxz=50 x1+100 x2,x1+ x2300,2x1+x2400,x1 0, x20,s.t.,x2250,maxz=50 x1+100 x2,x1+ x2+s1=300,2x1+x2+s2=400,x1 0, x20, si0,s.t.,x2+s3 =250,一、線性規(guī)劃問題解的基本概念,基及基本解:,maxz=50 x1+100 x2+0s1+0s2+0s3,1x1+1 x2+1s1+0s2+0s3 =300,2x1+1 x2+0s1+1s2+0s3 =400,x1 0, x20, s10， s20， s3

4、0,s.t.,0 x1+1x2+0s1+0s2+1s3 =250,表解形式的單純形法,例子:,初始單純形表,（）先分析非基變量s1: c3 3 由于是非基變量，故套用公式（1）,當(dāng)C3 -3, 時最優(yōu)解不變;已知3=-50, C3 （50）=50；c=c+C=0+50=50 最優(yōu)解不變。,（2）再分析基變量的系數(shù)分析：,從表中獲得了: a11=1, a12=0, a13=1, a14=0, a15=-1,例如對基變量X1的系數(shù)C1進行靈敏度分析：,單純形表靈敏度分析,故，max-50C1 min50，左半徑和右半徑 保證區(qū)間半徑最小 則當(dāng)-50C1 50時最優(yōu)解不變，即x1的目標(biāo)函數(shù)系數(shù)C有：

5、 50-50=c1+ L C=C1+C1 c1+R=50+50， 0C100時，最優(yōu)解不變。,*最優(yōu)解如下* 目標(biāo)函數(shù)最優(yōu)值為 : 27500 變量 最優(yōu)解 相差值 - - - x1 50 0 x2 250 0 約束 松弛/剩余變量 對偶價格 - - - 1 0 50 2 50 0 3 0 50 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - x1 0 50 100 x2 50 100 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 250 300 325 2 350 400 無上限 3 200 250 300,LP OPTIMUM FOUND AT S

6、TEP 2 OBJECTIVE FUNCTION VALUE 1) 27500.00 VARIABLE VALUE REDUCED COST X1 50.000000 0.000000 X2 250.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 50.000000 3) 50.000000 0.000000 4) 0.000000 50.000000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARI

7、ABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 50.000000 50.000000 50.000000 X2 100.000000 INFINITY 50.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 300.000000 25.000000 50.000000 3 400.000000 INFINITY 50.000000 4 250.000000 50.000000 50.000000,二、基于

8、單純形法的約束方程右邊常數(shù)靈敏度分析,二、約束方程右邊常數(shù)靈敏度分析,從上頁表中我們,知道了右邊系數(shù)bj的靈敏度,對偶價格不變與bj變化范圍. 現(xiàn)要從單純形表的數(shù)據(jù)進行分析： Zj的值剛好是對偶價格. 那么，當(dāng)bj變?yōu)閎j+b時,非基變量的檢驗數(shù)不變,但基變量的檢驗數(shù)會變。bk允許范圍為:,二、約束方程右邊常數(shù)靈敏度分析,那么，當(dāng)br變?yōu)閎r+br時,非基變量的檢驗數(shù)不變,但基變量的檢驗數(shù)會變. br 允許范圍為:,初始單純形表,現(xiàn)對b1進行靈敏度分析,先要找出b1的列元素:它就是S1.因為可逆矩陣B的第一列為 S1=(1,-2,0)T Max- 50/1=-50 b1 min-50/-2=2

9、5 -50 b1 +25 那么, 300-50b=b+ b1 300+25 250b=b+ b1 325 練習(xí)：分析B3,三、約束方程系數(shù)矩陣A靈敏度分析,技術(shù)系數(shù)aij發(fā)生變化時對線性規(guī)劃最優(yōu)解結(jié)構(gòu)的影響比較復(fù)雜。從下式中可知，非基變量的檢驗數(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靈敏度分析,線性規(guī)劃最優(yōu)解結(jié)構(gòu)不變的條件是 （1）對應(yīng)基變量的aij，且資源Bi已全部用完，則

10、技術(shù)系數(shù)變化范圍為：aij=0; （2）對應(yīng)基變量的aij，但資源bi未用完,則技術(shù)系數(shù)變化范圍為：aijXn+i/xj （3）對應(yīng)非基變量的aij，且資源bi全部用完或未用完,我們要分以下兩種情況討論： （A）aij0, 不會破壞最優(yōu)解。 （B）aij0，要使原線性規(guī)劃最優(yōu)解不變條件：必須保證該非基變量的檢驗數(shù)仍小于0，即cj-Zj0,第2節(jié) 線性規(guī)劃的對偶問題,某工廠在計劃安排I,II兩種產(chǎn)品,生產(chǎn)I可獲得50元,II可獲得100元,如何安排生產(chǎn),獲得MAX?,模型,目標(biāo):max z=50 x1+100 x2 S.t. x1+x2=0,假設(shè)現(xiàn)在有一個公司要租用工廠設(shè)備，那么工廠獲取利潤有兩

11、種方法，一是自己生產(chǎn)，二是出租設(shè)備資源。自己生產(chǎn)已有模型。那么，如果出租，那么如何構(gòu)建模型？設(shè)備價格為Ay1,By2,Cy3;則,目標(biāo):min f=300y1+400y2+250y3 s.t. y1+2y2=50 y1+y2+y3100 y1,y2,y3 =0,目標(biāo):min f=300y1+400y2+250y3 s.t. Y1+2y2=50 y1+y2+y3100 y1,y2,y3 =0,目標(biāo):max z=50 x1+100 x2 S.t. x1+x2=0,原問題,對偶問題,1.求目標(biāo)函數(shù)最大問題中有n個變量,m個約束條件,它的約束條件都是小于等于不等式;其對偶則是m個變量,n個約束條件,并

12、且是大于等于不等式;,2.原問題的目標(biāo)函數(shù)系數(shù)C是對偶問題中的約束條件B ci=bi 3.原問題右邊系數(shù)B成為對偶問題的目標(biāo)系數(shù)C,bi=ci 4. 對偶問題的約束條件系數(shù)矩陣A是原問題的AT,轉(zhuǎn)化例子： Max f=3x1+4x2+6x3+4x4 x1+4x2+2x3-3x435 3x1+x2+5x3+6x445 x1,x2,x3,x40,Min g(y)= 35y1+45y2 Y1+3y2 3 4y1+y2 4 2y1+5y2 6 -3y1+6y2 4 Y1,y2 0,目標(biāo): min f=300y1+400y2+250y3 s.t. Y1+2y250 y1+y2+y3100 y1,y2,y

13、3 0,目標(biāo): max z=50 x1+100 x2 S.t. x1+x2300 2x1+x2400 x2250 x1,x20,原問題,對偶問題,Max -f=-300y1-400y2-250y3-Ma1 y1+2y2-s1+a1=50 y1+y2+y3-s2=100 y1,y2,y3,s1,s2,a10,對偶單純形法求解：,初始單純形表,初始單純形表,(1/2),初始單純形表,(1/2),最優(yōu)解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值為-27500,即目標(biāo)f的最小值為:27500 A設(shè)備租金為50元,B設(shè)備租金為0元,C設(shè)備租金為50元;,二.任意形式的

14、對偶問題 max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 6x1-4x2-x3 100 5x1-3x2+x3 = 200 x1,x2,x3 0,二.任意形式的對偶問題 max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 -6x1+4x2+x3 -100 5x1-3x2+x3 200 5x1-3x2+x3 200 x1,x2,x3 0,5x1-3x2+x3 = 200,max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 -6x1+4x2+x3 -100 5x1-3x2+x3 200 -5x1+3x2-x3 -200 x1

15、,x2,x3 0,s.t. 2y1-6y2 +5y3-5y4 3 3y1+4y2 +3y3-3y4 4 6y1+y2+y3-y4 6 y1,y2,y3,y4 0,min f=440y1-100y2+200y3-200y4,二.任意形式的對偶問題,對偶問題,原問題的對偶問題為 min f=440y1-100y2+200y3-200y4 s.t. 2y1-6y2 +5y3-5y4 3 3y1+4y2 +3y3-3y4 4 6y1+y2+y3-y4 6 y1,y2,y3,y4 0,原問題的對偶問題為 min f=440y1-100y2+200(y3-y4) s.t. 2y1-6y2 +5(y3-y4

16、) 3 3y1+4y2 +3(y3-y4) 4 6y1+y2 + (y3-y4) 6 y1,y2,y3,y4 0,原問題的對偶問題為 min f=440y1-100y2+200s3 s.t. 2y1-6y2 +5s3 3 3y1+4y2 +3s3 4 6y1+y2 + s3 6 y1,y2 0,S3無非負(fù)限制,練習(xí)： Max f(x)=4x1+5x2 s.t. 3x1+2x220 4x1-3x2 10 x1+x2 = 5 x20, x1正負(fù)不限,練習(xí)轉(zhuǎn)換： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+

17、x2 = 5 x11,x12,x20,練習(xí)轉(zhuǎn)換： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+x2 5 x11-x12+x2 5 x11,x12,x20,練習(xí)轉(zhuǎn)換： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 -(4x11-4x12-3x2) -10 -(x11-x12+x2) -5 x11-x12+x2 5 x11,x12,x20,練習(xí)轉(zhuǎn)換： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x2 20 -4x11+4x12+3

18、x2 -10 -x11+x12-x2 -5 x11-x12+x2 5 x11,x12,x20,練習(xí)轉(zhuǎn)換： Min f(y)=20y1-10y2-5y3+5y4 s.t. 3y1-4y2-y3+y4 =4 -3y1+4y2+y3-y4 =-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0,練習(xí)轉(zhuǎn)換： Min f(y)=20y1-10y2-5(y3-y4) s.t. 3y1-4y2 - (y3-y4) = 4 -3y1+4y2+(y3-y4) =-4 2y1+3y2- (y3-y4) =5 y1,y2,y3,y4=0,練習(xí)轉(zhuǎn)換： Min f(y)=20y1-10y2-5y3 s.t

19、. 3y1-4y2 - y3 = 4 -3y1+4y2+y3 =-4 2y1+3y2- y3 =5 y1,y2 =0，y3無限制,練習(xí)轉(zhuǎn)換： Min f(y)=20y1-10y2-5y3 s.t. 3y1-4y2 - y3 = 4 2y1+3y2- y3 =5 y1,y2 =0，y3無限制,練習(xí)轉(zhuǎn)換： Min f(y)=20y1-10y2-5y3+5y4 s.t. 3y1-4y2-y3+y4 =4 -3y1+4y2+y3-y4 =-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0,練習(xí)答案： Min h(y)=20y1+10y2+5y3 s.t. 3y1+4y2+y3 =4 2y1-3y2+y3 5 y10, y20, y3不限,第3節(jié) 對偶單純形法,對偶單純法和單純形法一樣都是求解原線性規(guī)劃問題的一種方法. 單純形法是在保持原問題的所有約束條件的bj都大于0的情況下,通過迭代,使得所有檢驗數(shù)都小于等于0,最后求得最優(yōu)解; 而對偶單純形法則是在保持原問題的所有檢驗數(shù)都小于等于0的情況下,通過迭代,使得所有約束條件的常數(shù)都大于等于0,最后求得最優(yōu)解。,第3節(jié) 對偶單純形法,例，用對偶單純形法求解如下線性規(guī)劃問題： Min f=x1+5x2+3x4 s.t. X1+2x2-x