單純形法的矩陣計算PPT學(xué)習(xí)教案

1、會計學(xué)1單純形法的矩陣計算單純形法的矩陣計算3.1 單純形法的矩陣描述單純形法的矩陣描述3.2 單純形法的矩陣計算單純形法的矩陣計算3.3 對偶問題的提出對偶問題的提出3.4 線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論3.5 影子價格影子價格3.6 對偶單純形法對偶單純形法3.7 靈敏度分析靈敏度分析第1頁/共27頁第2頁/共27頁第3頁/共27頁()()ljljlkljijijiklkaailaaaaaila ,2ijljijljlkaaaaa 設(shè)設(shè)是是本本次次表表中中的的數(shù)數(shù)字字，是是迭迭代代后后表表中中數(shù)數(shù)字字，是是主主元元素素，由由第第 章章知知111211212mlllmmmmmaaaaa

2、aaaa1111211212/0101/00/1klkmlllmlkmklkmmmmaaaaaaaaaaaaaa 第4頁/共27頁11111(, ,)newllmBEBEeeee , , 其其中中111/1/kklklklkmklkmkaaaPaaaaa 主主元元素素這樣就求得新基的逆矩陣。這樣就求得新基的逆矩陣。 第5頁/共27頁.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出結(jié)果重復(fù)的求出此得到新的出基行對應(yīng)的則若入基則若基變換否則轉(zhuǎn)下一步則得最優(yōu)解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllk

3、likikiikkNjNjBNN第6頁/共27頁n 改進單純形法的步驟：改進單純形法的步驟：（1 1）據(jù)）據(jù)LPLP問題的標(biāo)準(zhǔn)型，確定初始基變量和初始可行問題的標(biāo)準(zhǔn)型，確定初始基變量和初始可行基。求逆矩陣基。求逆矩陣-1-1，得初始基本可行解，得初始基本可行解 （2 2）計算單純形乘子）計算單純形乘子 和目標(biāo)函數(shù)值和目標(biāo)函數(shù)值（3 3）計算非基變量檢驗數(shù)）計算非基變量檢驗數(shù), ,若若，則已得最優(yōu)解，停止計算；否則轉(zhuǎn)下一步。，則已得最優(yōu)解，停止計算；否則轉(zhuǎn)下一步。（4 4）據(jù)，確定為換入變量，計算）據(jù)，確定為換入變量，計算, ,若若 00，則問題沒有有限最優(yōu)解，停止計算，否則，則問題沒有有限最優(yōu)

4、解，停止計算，否則轉(zhuǎn)下一步。轉(zhuǎn)下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB PN0第7頁/共27頁（5 5）據(jù)）據(jù) ，確定，確定 為換出變量。為換出變量。 （6 6）用替代）用替代 得新基得新基1 1，由變換公式，由變換公式 計算計算1 1-1-1，求出新的基本可行解。，求出新的基本可行解。 其中為變換矩陣，構(gòu)造方法：其中為變換矩陣，構(gòu)造方法：將換入變量將換入變量 對應(yīng)的系數(shù)列向量對應(yīng)的系數(shù)列向量 做如下變形，主元素做如下變形，主元素 （應(yīng)在主對角線上）取倒數(shù)，其他元素除以主元素

5、（應(yīng)在主對角線上）取倒數(shù)，其他元素除以主元素 并并取相反數(shù)。然后用它替換單位矩陣出發(fā)，把換出變量取相反數(shù)。然后用它替換單位矩陣出發(fā)，把換出變量 在在基基B B中的對應(yīng)列的單位向量。中的對應(yīng)列的單位向量。重復(fù)（重復(fù)（2 2）（）（6 6）直至求得最優(yōu)解。）直至求得最優(yōu)解。 -1-1-1iki-1-1kik(B b)(B b)min/(B P ) 0 =(B P )(B P )llxlPlkP-1-11k BE Blk Elkal-1kB Pxlkxkal第8頁/共27頁123451231425max2300028416412zxxxxxxxxxxxx 第9頁/共27頁034503451( ,)

6、,1;1TBXx x xBPPP（2）計算非基變量的檢驗數(shù)，確定換入變量）計算非基變量的檢驗數(shù)，確定換入變量。012( ,)TNXx x10111B 000100012(,)NNBCCB NNP P 121001 22,3(0,0,0) 0104 02,3,0010 4x x 第10頁/共27頁(3) 確定換出變量確定換出變量 101021025min0812min, ,324iiB bB PB Px （4）基變換）基變換新基1342,BPPP2121/ 2001/44P ；第11頁/共27頁1111011/ 21101/ 21010101/41001/4BE B115(,)TNXxx 111

7、1111/ 2111/ 241044011/4101/4NB N 第12頁/共27頁（6）計算）計算RHS1111/ 2821016161/4123B b ),(),(C,CC;x ,xX;x ,x ,xX;P,P,PBNBTNTB023001111512432431價值系數(shù)非基變量基變量基第13頁/共27頁11111111515(,)101/21 02,0(0,0,3) 0104 0001/40 1(2, 3/4),NNBCC B NNP Px x對應(yīng)換入變量注：115( , )TNXx x第14頁/共27頁 111111113min02 16 3min,2140iiB bB PB Px （

8、4）由此得到新的基。）由此得到新的基。 2142,BP P P 12011440P 主主元元素素第15頁/共27頁11221100101/ 2101/ 2410010412001001/4001/4BE B （4）計算）計算RHS 。 12101/ 282412168001/4123B b 第16頁/共27頁),(),(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB003022222532412412價值系數(shù)非基變量基變量基第17頁/共27頁235(,)TNXxx (3)確定換出變量確定換出變量 121251254min0283min,41/ 2 2 1/4iiB bB PB Px

9、 22212223535(,)101/ 21 00,0(2,0,3)4130 0001/40 12,1/4,NNBCC B NNP Pxx 第18頁/共27頁 3152,;BP P P 31/41/ 21/8 125101/ 201/ 24120001/411/42B P 1133211/40101/ 201/ 2041201/81001/401/4021/ 211/ 21/80BE B 5x入入量量的的系系 向向量量是是第19頁/共27頁 333133334(,)01/401 00,0(2,0,3)21/ 210 11/ 21/800 03/ 2,1/8NNBCC B NNP P 已無正的檢

10、驗數(shù)已無正的檢驗數(shù)33,4()TNXx x 第20頁/共27頁1*153201/48421/ 21641/ 21/8122xXxB bx 最優(yōu)值為 3*1342,0,34142BzC B b 第21頁/共27頁2 算例算例max z = 5x1+2x2+3x3x4+x5 x1+2x2+2x3+x4 = 8 3x1+4x2+x3+x5 = 7 x1, x2, x3, x4, x5 0 1） 101430122154321pppppA系數(shù)矩陣：系數(shù)矩陣：78b常數(shù)項：常數(shù)項：11325c價值系數(shù)：價值系數(shù)：1001540ppB7878100110540bBxxXB 403122325 143221

11、113253210N x3 入基入基41728minmin31010PBbB x4 出基出基第22頁/共27頁2） 101430122154321pppppA系數(shù)矩陣：系數(shù)矩陣：78b常數(shù)項：常數(shù)項：11325c價值系數(shù)：價值系數(shù)：1102531ppB347812/102/111531bBxxXB 241164125 04312112/102/1131254211N x1 入基入基562/532/14minmin11111PBbB x5 出基出基第23頁/共27頁3） 3112131ppB5/65/17785/25/15/15/312132bBxxXB5259526 1040125/25/15/15/3531125422N最優(yōu)解：最優(yōu)解：X* =(6/5, 0, 17/5, 0, 0 )T101430122154321pppppA系數(shù)矩陣：系