1、會計學1線性規(guī)劃問題的對偶與靈敏分析線性規(guī)劃問題的對偶與靈敏分析2第1頁/共52頁31.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題第2頁/共52頁4產(chǎn)品甲產(chǎn)品乙設備能力（h）設備A3 32 26565設備B2 21 14040設備C0 03 37575利潤（元/件）1500150025002500第3頁/共52頁5第4頁/共52頁6第5頁/共52頁7第6頁/共52頁8第7頁/共52頁9第8頁/共52頁10第9頁/共52頁111111111111.bxaxabxaxannnn這樣，原規(guī)劃模型可以寫成mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn, 2 , 1, 0max1111

2、1111111111第10頁/共52頁12沒有非負限制121111112211211211111111221111,0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm這里，把 y1 看作是 y1 = y1 - y1，于是 y1 沒有非負限制，關系（2）的說明完畢。第11頁/共52頁13解 先將約束條件變形為“”形式?jīng)]有非負限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ第12頁/共52頁14沒有非負限制4321443214314321,0,051030

3、422602722523xxxxxxxxxxxxxxxx 再根據(jù)非對稱形式的對應關系，直接寫出對偶規(guī)劃第13頁/共52頁150,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒有非負限制第14頁/共52頁16 定理3-1 (弱對偶定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx bTy。 推論 若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。第15頁/共52頁17 定理3-3 (主對偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最

4、優(yōu)值相等。 以上定理、推論對任意形式的相應性規(guī)劃的對偶均有效第16頁/共52頁18第17頁/共52頁19生產(chǎn)能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。第18頁/共52頁20*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*第19頁/共52頁21第20頁/共52頁22節(jié)中討論。第21頁/共52頁23第22頁/共52頁2450100000CBXBx1x2x3x4x5i0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175

5、100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價格影子價格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1對應的檢驗數(shù)對應的檢驗數(shù) T T = = c cB BT TB B-1-1 。第23頁/共52頁25 對偶單純形法

6、的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個基本解基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶可行解對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數(shù)非正）。第24頁/共52頁26 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校斖瑫r得到對偶規(guī)劃與原 規(guī)劃的可行解時，便 得到原規(guī)劃的最優(yōu)解。第25頁/共52頁27 對偶單純

7、形法在什么情況下使用 ： 應用前提：有一個基，其對應的基滿足: 單純形表的檢驗數(shù)行全部非正（對偶可行）； 變量取值可有負數(shù)（非可行解）。 注：通過矩陣行變換運算，使所有相應變量取值均為非負數(shù)即得到最優(yōu)單純形表。第26頁/共52頁28 對偶單純形法求解線性規(guī)劃問題對偶單純形法求解線性規(guī)劃問題過程：過程：第27頁/共52頁29 標準化：標準化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3

8、 2x1 - x2 + x3 4 x1 , x2 , x3 0 第28頁/共52頁30CI-2-3-400CBXBbX1X2X3X4X50X4-3-1-2-1100X5-4-21-301j-2-3-4000X4-10-5/21/21-1/2-2X121-1/23/20-1/2j0-4-10-1-3X22/501-1/5 -2/5 1/5-2X111/5107/5 -1/5 -2/5j00-9/5 -8/5 -1/5第29頁/共52頁31是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應原規(guī)劃的基本解是可行的典式對應原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停

9、沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0 第40頁/共52頁42s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4 , , x x5 5 0 0 第41頁/共52頁43Ci23000CBXBBX1X2

10、X3X4X52X141001/400X5400-21/213X22011/2-1/80j00-1.5-1/80Ci23+C2000CBXBBX1X2X3X4X52X141001/400X5400-21/213+C2X22011/2-1/80j00-1.5-C2/2-1/8+C2/80從表中看到j=cj-(c1a1j+c5 a5j+(c2+c2) a2j)j=3,4可得到 -3c21時，原最優(yōu)解不變。第42頁/共52頁44第43頁/共52頁45Min-bi/airair0第44頁/共52頁46Ci23000CBXBBX1X2X3X4X52X141001/400X5400-21/213X22011

11、/2-1/80j00-1.5-1/80第45頁/共52頁47各列分別對應 b1、b2、b3 的單一變化因此，設 b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用對偶單純形法進一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 17第46頁/共52頁48第47頁/共52頁49Ci230005CBXBbX1X2X3X4X5X62X141001/401.50X5400-21/2123X22011/2-1/800.25j00-1.5-1/801.25用單純形法進一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5第48頁/共52頁50工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。?9頁/共52頁51