運籌學對偶理論與敏感性分析PPT學習教案

1、會計學1 運籌學對偶理論與敏感性分析運籌學對偶理論與敏感性分析 2 第1頁/共85頁 3 產品甲產品乙設備能力（ h） 設備A3265 設備B2140 設備C0375 利潤（元/件）15002500 設變量xi為第i種（甲、乙）產品的生產 件數(shù)（i1,2） 第2頁/共85頁 4 若該工廠的設備都用于出租，工廠收取出租 費。試問：設備A、B、C每工時各如何收 費才最有競爭力？ 第3頁/共85頁 5 minw=65y1+40y2+75y3 s.t.3y1+2y21500（不少于甲產品的利 潤） 2y1+y2+3y32500（不少于乙產品的利潤 ） y1,y2,y30 第4頁/共85頁 6 y1,

2、y2, y3 0 第5頁/共85頁 7 第6頁/共85頁 8 s.t. Ax b s.t. Ax + Ixs = b x 0 x, xs 0 第7頁/共85頁 9 cB cN 0 cB xB b xB xN xS 0 xS b B N I 檢驗數(shù)行 cB cN 0 cB cN 0 cB xB b xB xN xS cB xB B-1b I B-1N B-1 檢驗數(shù)行 0 cN -cBB-1N - cBB-1 經過若干次迭代 （標準化）原問題的初始單純形表 第8頁/共85頁 10 當單純形表為最優(yōu)表時，檢驗數(shù)行為： (cB,cN,0)-cBB-1(B,N,I)= (0,cN-cBB-1N,-cB

3、B-1)0 令y=cBB-1,易看出 yAc y0 又因為 w =yb =cBB-1b =z 根據(jù)后面的強對偶理論知cBB-1為對偶問題的 最優(yōu)解。而cBB-1就是最優(yōu)單純形表中對應于松弛 變量的檢驗數(shù)的負值。 第9頁/共85頁 11 例2.2： maxz=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1,x20 加松弛變量得標準形式： maxz=50 x1+100 x2 s.t.x1+x2+x3=300 2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x50 第10頁/共85頁 12 50 100 0 0 0 CB XB x1

4、x2 x3 x4 x5 i 0 x3 300 1 1 1 0 0 300 0 x4 400 2 1 0 1 0 400 0 x5 250 0 (1) 0 0 1 250 z 0 50 100* 0 0 0 0 x3 50 (1) 0 1 0 -1 50 0 x4 150 2 0 0 1 -1 75 100 x2 250 0 1 0 0 1 z -25000 50* 0 0 0 -100 50 x1 50 1 0 1 0 -1 0 x4 50 0 0 -2 1 1 100 x2 250 0 1 0 0 1 z -27500 0 0 50 0 50 cBB-1 I B=(P1,P4, P2) B-

5、1 最優(yōu)解：x1=50,x2=250,x4=50 對偶最優(yōu)解：y1=50,y2=0,y3=50 B-1對應的檢驗數(shù) T = cBB-1。 第11頁/共85頁 13 原問題（對偶問題）原問題（對偶問題）對偶問題（原問題）對偶問題（原問題） max z = cxmin w = yb n 個變量n 個約束 xj 0a1jy1 + a2jy2 + + a2jym cj xj 0a1jy1 + a2jy2 + + a2jym cj xj 無約束a1jy1 + a2jy2 + + a2jym = cj m 個約束m 個變量 ai1x1 + ai2x2 + + ainxn biyi 0 ai1x1 + ai

6、2x2 + + ainxn biyi 0 ai1x1 + ai2x2 + + ainxn = bi yi 無約束 非對稱形式的對偶規(guī)劃 第12頁/共85頁 14 第13頁/共85頁 15 這樣，原規(guī)劃模型可以寫成 mjx bxaxa bxaxa bxaxa ts xcxcz j mnmnm nn nn nn , 2 , 1, 0 . max 11 11111 11111 11 第14頁/共85頁 16 111122 11111121211 12112122222 111122 112 min . . ,0 mm mm mm nnnmnmn m wb yb yb yb y a ya yayayc

7、 ayayayayc s t ayayayayc yyyy 這里，把y1看作是 y1=y1-y1，于是 y1沒有非負限制。 第15頁/共85頁 17 例例2.12.1 寫出右寫出右 邊線性規(guī)劃問邊線性規(guī)劃問 題的對偶問題題的對偶問題 。 0, 3 22 252 min 21 321 321 321 321 xx xxx xxx xxx xxxz 0, 12 12 1 3225 max 21 321 321 321 321 yy yyy yyy yyy yyyw 最小化問題：最小化問題： 最小化問題的對偶問題：最小化問題的對偶問題： 變成目標函變成目標函 數(shù)的系數(shù)數(shù)的系數(shù) 系數(shù)變成約束系數(shù)變成約

8、束 條件右側值條件右側值 變成第一個變成第一個 約束條件的約束條件的 系數(shù)系數(shù) 反過來，由下反過來，由下 往上也是一樣往上也是一樣 的。的。 第16頁/共85頁 18 (LP)Maxz=j=1,2,n cj xj s.t.j=1,2,n aij xjbi,i =1,2,m xj 0,j =1,2,n (DP)Minw=i=1,2,m bi yi s.t.i=1,2,m aij yicj,j =1,2,n yi0,i =1,2,m 第17頁/共85頁 19 對偶規(guī)劃的性質和原理對偶規(guī)劃的性質和原理 定理2.0(對稱性） 對偶規(guī)劃的對偶規(guī)劃是原規(guī)劃 定理2.1(弱對偶定理） 若x,y分別為(LP)

9、和(DP)的可行解，則 cxyb 第18頁/共85頁 20 第19頁/共85頁 21 定理2.3(強對偶定理) 若(LP)和(DP)均可行，那么(LP)和(DP)均有最優(yōu)解，且最優(yōu)值相等。 定理2.4(互補松弛定理) 若X*,Y*為最優(yōu)解，Xs,Ys為原問題和對偶問題的松弛變量，則有YsX*=0,Y*Xs=0 也即，在(LP)和(DP)的最優(yōu)解中： (1)如果對應某一約束的對偶變量取值非零，則該約束取嚴格等式； (2)如果某一約束取嚴格不等式，則其對應的對偶變量必取零。 第20頁/共85頁 22 定理2.5 原問題單純型表的檢驗數(shù)行對應對偶問題的一個基解 cB cN 0 cB xB b xB

10、xN xS cB xB B-1b I B-1N B-1 檢驗數(shù)行 0 cN -cBB-1N - cBB-1 第21頁/共85頁 23 例2.3：已知線性規(guī)劃 maxz=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1,x20 的最優(yōu)解為x1*=50,x2*=250，求出 該線性規(guī)劃對偶問題的最優(yōu)解。 第22頁/共85頁 24 解：x1*+x2*=300y1*0, 2x1*+x2*0y1*+2y2*=50, x2*0y1*+y2*+y3*= 100. 所以， y1*=50,y2*=0,y3*=50. 第23頁/共85頁 25 例：已知線性規(guī)劃 maxz=x

11、1+x2 s.t.-x1+x2+x32 -2x1+x2-x31 x1,x2x30 試用對偶理論證明該線性規(guī)劃無最優(yōu) 解。 第24頁/共85頁 26 解：minw=2y1+y2 s.t.-y1-2y22 y1+y21 y1-y20 y1,y20 對偶問題無可行解 第25頁/共85頁 27 課堂練習： 已知原問題最優(yōu)解為（2,2,4,0），根據(jù)對偶理論，寫出對偶問題的最優(yōu)解 第26頁/共85頁 28 4. 對偶單純形法對偶單純形法 w 基本思想 w 算法過程 w 算例 第27頁/共85頁 29 cB cN 0 cB xB b xB xN xS cB xB B-1b I B-1N B-1 檢驗數(shù)行

12、0 cN -cBB-1N -cBB-1 第28頁/共85頁 30 cB cN 0 cB xB b xB xN xS cB xB B-1b0 I B-1N B-1 檢驗數(shù)行 0 cN - cBB-1N - cBB-1 0 第29頁/共85頁 31 cB cN 0 cB xB b xB xN xS cB xB B-1b0 I B-1N B-1 檢驗數(shù)行 0 cN - cBB-1N - cBB-1 0 第30頁/共85頁 32 對偶單純形法在什么情況下使用？ 應用前提：有一個基，其對應的基滿足: 單純形表的檢驗數(shù)行全部為負（即 對偶可行）； 基變量取值有負數(shù)（非可行解）。 注：通過矩陣行變換運算，使

13、所有相應 基變量取值均為非負數(shù)即得到最優(yōu) 單純形表。 第31頁/共85頁 33 對偶單純形法求解線性規(guī)劃問題過程：對偶單純形法求解線性規(guī)劃問題過程： 第32頁/共85頁 34 標準化：標準化： maxz=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x50 minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+x34 x1,x2,x30 第33頁/共85頁 35 cj -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 -3 -1 -2 -1 1 0 0 x5

14、 -4 -2 1 -3 0 1 j 0 -2 -3 -4 0 0 0 x4 -1 0 -5/2 1/2 1 -1/2 -2 x1 2 1 -1/2 3/2 0 -1/2 j 4 0 -4 -1 0 -1 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5 -8/5 -1/5 第34頁/共85頁 36 是 是 是是 否否 否否 所有所有 得到 最優(yōu)解 計算計算 原規(guī)劃的基解是 可行的 對偶問題的基解是 可行的 所有所有 計算計算 以旋轉元素進行迭代以旋轉元素進行迭代 停 無 界 解 無 可 行 解 單純

15、形法對偶單純形法 0 j 0 i b max0 kjj 0min iie bbb 0 ik a0 lj a ek e ik ik i a b a a b 0min min0 ik ej ejek a aa 第35頁/共85頁 37 第36頁/共85頁 3. 對偶變量的經濟解釋對偶變量的經濟解釋 影子價格影子價格 Shadow price 第37頁/共85頁 39 maxz=2x1+x2 s.t.5x215 6x1+2x225 x1+x25 x1 , x2 0 b2：2425 z* ：8.58.75 z/b2=0.25 第38頁/共85頁 40 若B是最優(yōu)基，y*T = cBB-1 為影子價格向

16、量。 第39頁/共85頁 擴大生產；否則不宜買進。 第40頁/共85頁 * 22 * 11 * mmy bybybwz 第41頁/共85頁 43 miy b z i i ,2,1, * * miy i ,2,1, * 第42頁/共85頁 第43頁/共85頁 45 變化。 3 x1+x25 3 x1+x26 b2：2425 z/b20.25 第44頁/共85頁 第45頁/共85頁 47 0,1818,3030,+) x1*(b2-6)/6(b2-10)/45 x2*3(30-b2)/40 z*1+b2/35/2+b2/410 y2*=z/b21/31/4 b2 0 第46頁/共85頁 48 5.

17、 靈敏度分析靈敏度分析 Sensitivity Analysis 第47頁/共85頁 49 第48頁/共85頁 50 原問題對偶問題結論或繼續(xù)計算的 步驟 可行解可行解最優(yōu)基不變 可行解非可行解用單純形法繼續(xù)迭 代 非可行解可行解用對偶單純形法繼 續(xù)迭代 非可行解非可行解引入人工變量，編 制新的單純形表重 新計算 第49頁/共85頁 問題問題1 1：ci,bi,aij發(fā)生變化，問題的最 優(yōu)解如何變化？或者這些參數(shù)在多大 的范圍內變化，最優(yōu)解仍然不變？ 問題2：增加一約束或變量，最優(yōu)解如 何變化？ 第50頁/共85頁 52 1.c是非基變量的系數(shù)： 2. c是基變量的系數(shù)：是基變量的系數(shù)： 第5

18、1頁/共85頁 1.若ck是非基變量的系數(shù)： 設 ck 變化為 ck + ck k=ck +ck-ci aik=k+ck 只要k0,即 ck-k， 則最優(yōu)解不變； 否則，將最優(yōu)單純形表中的檢驗數(shù)k 用k取代，繼續(xù)單純形法的表格計算 。 第52頁/共85頁 第53頁/共85頁 c -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5 -8/5 -1/5 c -2 -3 -4+c3 0 0 cB xB b x1 x2 x3 x4 x5

19、-3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5+c3 -8/5 -1/5 從表中看到3=c3+c3-(c2a13+c1a23) 可得到c39/5 時，原最優(yōu)解不變。 第54頁/共85頁 2. 若若 cs 是基變量的系數(shù)：是基變量的系數(shù)： 設cs變化為cs +cs，那么 j=cj-i sciaij-(cs+cs)asj =j-csasj， 只要對所有非基變量，有j0，即 jcsasj， 則最優(yōu)解不變；否則，將最優(yōu)單純形 表中的檢驗數(shù)j用j取代，繼續(xù)單純 形法的表格計算。 第55頁/共85頁 57 I

20、II可用資源 設備128臺時 原材料A4016kg 原材料B0412kg 已知生產1件I可以獲利2元，生產1件II可獲利3元， 問應當如何安排計劃使該工廠獲利最多？ 第56頁/共85頁 例2.6：線性規(guī)劃 maxz=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,x3,x4,x50 有最優(yōu)解的單純形表： 考慮基變量系數(shù)c2發(fā)生變化 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/

21、8 0 j -14 0 0 -1.5 -1/8 0 第57頁/共85頁 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j -14 0 0 -1.5 -1/8 0 c 2 3+c2 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3+c2 x2 2 0 1 1/2 -1/8 0 j -14-2c2 0 0 -1.5 -c2/2 -1/8+c2/8 0 第58頁/共8

22、5頁 111 00 0 00 rr B bBbbBb 第59頁/共85頁 1 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j -14 0 0 -1.5 -1/8 0 第60頁/共85頁 各列分別對應 b1,b2,b3的單一變化。 因此，設b1增加4，則x1,x5,x2分別變 為： 4+04=4,4+(-2)4=-418時表時表2-17(1)仍然是最優(yōu)表仍然是最優(yōu)表,最優(yōu)解是參數(shù)的函數(shù) 最優(yōu)解是參數(shù)的函數(shù) X（8，9+0.5，0）,目標值目標值Z 67+1.5