純形法的計(jì)算公式

1、單純形法的矩陣描述單純形法的矩陣描述單純形法的矩陣表示單純形法的矩陣表示標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型maxz=cx ax=b x 0已知：已知：a、b、c a=(b n) mnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaa212122212222211211111211mmmmmmaaaaaaaaab212222111211mnmmmmnmmnmmaaaaaaaaan212221212111基陣基陣非基陣非基陣tmbxxxx21tnmmnxxxx21基基向向量量非非基基向向量量基變量基變量非基變量非基變量nbanbxxxbax bxxnbnbbnxbxnbnbnxbbxnbnxbbbx

2、11nbxxxnnxnxbbbx11令令0nx則則01bbx定義定義 在約束方程組在約束方程組(2) 中，對(duì)于中，對(duì)于一個(gè)選定的基一個(gè)選定的基b，令所有的非基變，令所有的非基變量為零得到的解，稱為相應(yīng)于基量為零得到的解，稱為相應(yīng)于基b的基本解。的基本解。定義定義 在基本解中，若該基本解滿足非負(fù)約束，在基本解中，若該基本解滿足非負(fù)約束，即即 ，則稱此基本解為，則稱此基本解為基本可行解基本可行解，簡(jiǎn)稱簡(jiǎn)稱基可行解基可行解；對(duì)應(yīng)的基；對(duì)應(yīng)的基b稱為稱為可行基可行基。01bbxb基本解中最多有基本解中最多有m個(gè)非零分量。個(gè)非零分量。基本解的數(shù)目不超過基本解的數(shù)目不超過 個(gè)。個(gè)。!mnmncmnnbnb

3、nnnbnnbbnbnbxnbccbbcxcnxbbbcxcxcxxcccxz)()(),(111101bbxb01nbccbnnbx若若b滿足下列條件，稱為滿足下列條件，稱為最優(yōu)基最優(yōu)基 稱為稱為最優(yōu)解最優(yōu)解等式右邊等式右邊b基變量基變量xb非基變量非基變量xnxbb1beb1n檢驗(yàn)數(shù)檢驗(yàn)數(shù)cb b1b(即即z) 0cn - cbb-1 n等式右邊等式右邊b變量變量xxbb1bb1a檢驗(yàn)數(shù)檢驗(yàn)數(shù)cb b1b(即即z)c - cbb-1 a單純形表矩陣形式（單純形表矩陣形式（p26p26）等式右邊等式右邊b基變量基變量xb非基變量非基變量xnxbbbn檢驗(yàn)數(shù)檢驗(yàn)數(shù)0cbcn 或者或者c - c

4、bb-1a= (cn cb )- cbb-1 (nb ) = (cn - cbb-1n, cb -cbb-1b)b-1a= b-1(n b )= (b-1n, b-1b)單個(gè)檢驗(yàn)數(shù)：?jiǎn)蝹€(gè)檢驗(yàn)數(shù)：j = cj - cbb-1 pj 某列某列pj = b-1 pj 規(guī)范形式：規(guī)范形式：maxz=cx ax bx 0maxz=cx+0x ax+ex= bx, x 0令令a=(a e) c=(c o)c- cb b-1 a=(c o)- cb b-1 (a e) =(c-cb b-1 a o-cb b-1 ) b-1 a= b-1(a e)=(b-1 a b-1 e)單純形表矩陣形式（單純形表矩陣形式

5、（p43p43）cb b-1 bb-1 bc- cb b-1 a - cb b-1 b-1 a b-1cb b-1單純形算子單純形算子等式右等式右邊邊b變量變量x松馳變量松馳變量xsxbb1bb1ab1檢驗(yàn)數(shù)檢驗(yàn)數(shù)-cb b1b(即即-z)c- cb b1a-cb b1-ys-y例：例：maxz=40x1 +50x2 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 xj 0 ( j=15)p1 p2 p3 p4 p5 1 2 1 0 03 2 0 1 00 2 0 0 1a=(1)、已知、已知b= (p3 p4 p2) 驗(yàn)證：驗(yàn)證：1 0 -10 1

6、-10 0 1/2b-1 =p5,求求1 , a ,(2)、b= (p1 p4 p2) 驗(yàn)證：驗(yàn)證：1 0 -1-3 1 20 0 1/2b-1 =p5,求求3 , 4,p3(1)、1 =c1 - cb b-1p1 =40 -(0 0 5 0) = 40 -(0,0,25) =401 0 -10 1 -10 0 1/21 3 01 3 0p5= b-1p5 =1 0 -10 1 -10 0 1/20 0 1=-1 -1 1/2a= c - cb b-1a=(40, 50, 0, 0, 0)- (0, 0, 50) =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50,

7、0, 0, 0) -(0, 50, 0, 0, 25) = (40, 0, 0, 0, -25)1 0 -10 1 -10 0 1/21 2 1 0 03 2 0 1 00 2 0 0 11 2 1 0 03 2 0 1 00 2 0 0 1(2)、3 = -40 ,4= 0p5 =-1 2 1/2p3 =1 -3 0 40 50 0 0 0 40 50 0 0 0 x1 x2 x3 x4 x5cb xb 0 40 50 0 0 0 0 40 50 0 0 0 0 0 x3 30 1 2 1 0 0 30 1 2 1 0 0 0 0 x4 6060 3 3 2 0 1 0 2 0 1 0 0

8、0 x5 24 0 (2) 0 0 1 24 0 (2) 0 0 1 xb 600 +40 0 0 0 -25 600 +40 0 0 0 -250 0 x3 6 (1) 0 1 0 -1 6 (1) 0 1 0 -1 0 0 x4 36 3 0 0 1 -1 36 3 0 0 1 -1 50 50 x2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 x1 6 1 0 1 0 -16 1 0 1 0 -10 0 x4 18 0 0 -3 1 2 18 0 0 -3 1 250 50 x2 12 0 1

9、0 0 1/2 12 0 1 0 0 1/2b1-1b2-1b3-1 xb 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 x1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 x5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 x2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0b4-11 0 00 1 00 0 1b1= (p3 p4 p5)= b1 -1 =1 0 00 1 00 0 11 0 20 1 20 0 2b2= (p3 p4 p2

10、)= b2 -1 =1 0 -10 1 -10 0 1/2(1)、只須存貯原始數(shù)據(jù)只須存貯原始數(shù)據(jù)a、b、c，每步需知每步需知b-1 。(2)、每步必須計(jì)算的數(shù)據(jù)每步必須計(jì)算的數(shù)據(jù) 檢驗(yàn)數(shù)檢驗(yàn)數(shù) n = cbb-1n - cn cbb-1 = 單純形乘子單純形乘子 當(dāng)某個(gè)當(dāng)某個(gè) m+k 0時(shí)時(shí)，需關(guān)鍵列：需關(guān)鍵列：pm+k = b-1pm+k =a1m+kamm+k 基變量基變量xb = b-1b =b1bm由由 、，用最小，用最小 比值法得主元比值法得主元arm+k 主元已知，新基主元已知，新基b確定。返回確定。返回(1)例例:maxz=6x1 +4x2 2x1 +3x2 1004x1 +2

11、x2 120x1 =14x2 22x1 x2 0maxz=6x1 +4x2 -mx6 -mx72x1 +3x2 +x3 = = 1004x1 +2x2 +x4 = = 120x1 +x6 =14x2 -x5+x7 =22x1 x7 0 6 4 0 0 0 - 6 4 0 0 0 - m - - m x1 x2 x3 x4 x5 x6 x7cb xb -36 -36 m m +6 +6 m +4 0 0 - +4 0 0 - m 0 0 0 00 0 x3 100 2 3 1 0 0 0 0 100 2 3 1 0 0 0 0 0 0 x4 120120 4 4 2 0 1 0 0 0 2 0

12、1 0 0 0 -m x6 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1cb xb 84 84-22m 0 0 m+4 0 0 - 0 0 -m 6-m 00 0 x3 72 0 3 1 0 0 -2 0 72 0 3 1 0 0 -2 0 0 0 x4 64 0 64 0 2 0 1 0 -4 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1cb xb 172 172 0 0 0 0 -4 0 0 -4 6- 6-m 4- 4-m0 0 x3 6 0 0 1 0 3 -2 -3 6 0 0 1 0 3 -2 -3 0 0 x4 2020 0 0 0 0 0 1 2 -4 -2 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1cb xb 180 180 0 0 0 -4/3 0 -4/3