[企業(yè)管理]第6章 單純形法的靈敏度分析與對偶2008

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

2、k 非非基變量.2.在最終的單純形表里, xk 基變量基變量.第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 即可。kkc第1節(jié) 單純形表的靈敏度分析.在最終的單

3、純形表里, xk 為基變量。 由于約束條件（方程）系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與ck 沒有任何關(guān)系，所以當(dāng)ck 變?yōu)閏k +ck 時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，但基變量在目標(biāo)函數(shù)的系數(shù)cb變了，則zj 也變了， 相應(yīng)地，也變了。變化規(guī)律為：0min0maxkjkjjkkjkjjaacaa一、線性規(guī)劃問題解的基本概念基及基本解:表解形式的單純形法v例子:03, 2, 1,250400230000010050max213222112132121sssxxsxsxxsxxsssxxz初始單純形表迭代次數(shù)基變量cbx1x2s1s2s3b比值501000002x1501010

4、-150s2000-21150 x210001001250zj5010050050z=2750000-500-50ijiabjjjzc （）先分析非基變量s1: c3 3 由于是非基變量，故套用公式（1） kkc當(dāng)c3 -3, 時(shí)最優(yōu)解不變;已知3=-50,c3 （50）=50；c=c+c0, 不會破壞最優(yōu)解。 （b）aij0，要使原線性規(guī)劃最優(yōu)解不變條件：必須保證該非基變量的檢驗(yàn)數(shù)仍小于0，即cj-zj0第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

5、?模型v目標(biāo):max z=50 x1+100 x2vs.t. x1+x2=300v 2x1+x2=400v x2=0假設(shè)現(xiàn)在有一個公司要租用工廠設(shè)備，那么工廠獲取利潤有兩種方法，一是自己生產(chǎn)，二是出租設(shè)備資源。自己生產(chǎn)已有模型。那么，如果出租，那么如何構(gòu)建模型？設(shè)備價(jià)格為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 =0v目標(biāo):max z=50 x1+100 x

6、2vs.t.v x1+x2=300v 2x1+x2=400v x2=0原問題對偶問題1.求目標(biāo)函數(shù)最大問題中有n個變量,m個約束條件,它的約束條件都是小于等于不等式;其對偶則是m個變量,n個約束條件,并且是大于等于不等式;2.原問題的目標(biāo)函數(shù)系數(shù)c是對偶問題中的約束條件b ci=bi3.原問題右邊系數(shù)b成為對偶問題的目標(biāo)系數(shù)c,bi=ci4. 對偶問題的約束條件系數(shù)矩陣a是原問題的atmnmnmmnnnnnnbxaxaxabxaxaxabxaxaxatsxcxcxcz221122222121112121112211.max0,3,2, 1.min221122222112112211112211

7、mmmnmnnmmmmmmyyyycyayayacyayayacyayayatsybybybg0maxxbaxcxz0minycyaybg原問題（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行約束條件為=型轉(zhuǎn)化例子：max f=3x1+4x2+6x3+4x4 x1+4x2+2x3-3x435 3x1+x2+5x3+6x445 x1,x2,x3,x40

8、 min g(y)= 35y1+45y2y1+3y2 34y1+y2 42y1+5y2 6-3y1+6y2 4y1,y2 0目標(biāo):min f=300y1+400y2+250y3 s.t. y1+2y250 y1+y2+y3100 y1,y2,y3 0v目標(biāo):vmax z=50 x1+100 x2vs.t.v x1+x2300v 2x1+x2400v x2250v v x1,x20原問題對偶問題vmax -f=-300y1-400y2-250y3-ma1v y1+2y2-s1+a1=50v y1+y2+y3-s2=100v y1,y2,y3,s1,s2,a10 對偶單純形法求解：初始單純形表迭代

9、次數(shù)基變量cby1y2y3s1s2a1b比值-300-400-25000-m0a1-m120-10150y3-2501110-10100zj-m-250-2m-250-250m250-m-50m-2500cj-zjm-502m-1500-m-25001100250初始單純形表迭代次數(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+752/1752/125(1/2)初始單純形表迭代次數(shù)基變量c

10、by1y2y3s1s2a1b比值-300-400-25000-m0y1-300120-10150y3-2500-111-1-150zj-300-350-25050250-50-27500cj-zj0-500-50-250-m+502/1752/125(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元;v二.任意形式的對偶問題 max z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 6x1-4x2-x3 100 5x1-3x2+x3

11、 = 200 x1,x2,x3 0v二.任意形式的對偶問題 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 = 200max z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 -6x1+4x2+x3 -100 5x1-3x2+x3 200 -5x1+3x2-x3 -200 x1,x2,x3 0s.t. 2y1-6y2 +5y3-5y4 3 3y1+4y2 +3y3-3y4 4 6y1+y2+y3-y4 6 y1,

12、y2,y3,y4 0min f=440y1-100y2+200y3-200y4v二.任意形式的對偶問題v對偶問題v原問題的對偶問題為 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 0v原問題的對偶問題為 min f=440y1-100y2+200(y3-y4) s.t. 2y1-6y2 +5(y3-y4) 3 3y1+4y2 +3(y3-y4) 4 6y1+y2 + (y3-y4) 6 y1,y2,y3,y4 0v原問題的對偶問題為 min

13、f=440y1-100y2+200s3 s.t. 2y1-6y2 +5s3 3 3y1+4y2 +3s3 4 6y1+y2 + s3 6 y1,y2 0,s3無非負(fù)限制v練習(xí)：vmax f(x)=4x1+5x2vs.t. 3x1+2x220 4x1-3x2 10 x1+x2 = 5 x20, x1正負(fù)不限v練習(xí)轉(zhuǎn)換：vmax f(x)=4x11-4x12+5x2vs.t. 3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+x2 = 5 x11,x12,x20v練習(xí)轉(zhuǎn)換：vmax f(x)=4x11-4x12+5x2vs.t. 3x11-3x12+2x220 4x

14、11-4x12-3x2 10 x11-x12+x2 5 x11-x12+x2 5 x11,x12,x20v練習(xí)轉(zhuǎn)換：vmax f(x)=4x11-4x12+5x2vs.t. 3x11-3x12+2x220 -(4x11-4x12-3x2) -10 -(x11-x12+x2) -5 x11-x12+x2 5 x11,x12,x20v練習(xí)轉(zhuǎn)換：vmax f(x)=4x11-4x12+5x2vs.t. 3x11-3x12+2x2 20 -4x11+4x12+3x2 -10 -x11+x12-x2 -5 x11-x12+x2 5 x11,x12,x20練習(xí)轉(zhuǎn)換：min f(y)=20y1-10y2-5

15、y3+5y4s.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-5y3s.t. 3y1-4y2 - y3 = 4 -3y1+4y2+y3 =-4 2y1+3y2- y3 =5 y1,y2 =0，y3無限制練習(xí)轉(zhuǎn)換：min f(y)=20

16、y1-10y2-5y3s.t. 3y1-4y2 - y3 = 4 2y1+3y2- y3 =5 y1,y2 =0，y3無限制練習(xí)轉(zhuǎn)換：min f(y)=20y1-10y2-5y3+5y4s.t. 3y1-4y2-y3+y4 =4 -3y1+4y2+y3-y4 =-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0v練習(xí)答案：vmin h(y)=20y1+10y2+5y3vs.t. 3y1+4y2+y3 =4 2y1-3y2+y3 5 y10, y20, y3不限原問題（max,)對偶問題(min,)技術(shù)系數(shù)矩陣a技術(shù)系數(shù)矩陣at價(jià)值系數(shù)c右端項(xiàng)b右端項(xiàng)b價(jià)值系數(shù)c第i行約束條件為

17、型對偶變量yi 0第i行約束條件為型對偶變量yi 0第i行約束條件為=型對偶變量yi正負(fù)不限決策量xj 0第j行約束條件為 型決策量xj 0第j行約束條件為型決策量xj正負(fù)不限第j行約束條件為=型第3節(jié) 對偶單純形法v對偶單純法和單純形法一樣都是求解原線性規(guī)劃問題的一種方法.v單純形法是在保持原問題的所有約束條件的bj都大于0的情況下,通過迭代,使得所有檢驗(yàn)數(shù)都小于等于0,最后求得最優(yōu)解;v而對偶單純形法則是在保持原問題的所有檢驗(yàn)數(shù)都小于等于0的情況下,通過迭代,使得所有約束條件的常數(shù)都大于等于0,最后求得最優(yōu)解。第3節(jié) 對偶單純形法v例，用對偶單純形法求解如下線性規(guī)劃問題：vmin f=x1

18、+5x2+3x4vs.t. v x1+2x2-x3+x46v -2x1-x2+4x3+x44v x1,x2,x3,x4 =0第3節(jié) 對偶單純形法v例，用對偶單純形法求解如下線性規(guī)劃問題：v將上述線性規(guī)劃問題變換為如下適合對偶單純形法的形式：v max z=-f=-x1-5x2-3x4v s.t. v -x1-2x2+x3-x4+x5= -6v 2x1+x2-4x3-x4+x6= -4v x1,x2,x3,x4,x5,x6 =0v x5,x6為剩余變量初始單純形表迭代次數(shù)基變量cbx1x2x3x4x5x6b比值-1-50-3000 x50-1-21-110-6x6021-4-101-4zj0000000cj-zj-1-50-3001100250x=(0,0,0,0,-6,-4)是基本解，但不是基本可行解，不可行。（1）確定出基變量：minbi|bi0=min-6,-4=-6=b1,所以第l=1行為主行，x5出基變量。（2）入基變量:111111113,25,11min0minazcaazcjjjjk所以第k=1列為主列，第1列的變量x1為入基變量。迭代