第4講14表格單純形法的計算步驟ppt課件

1、1.41.4表格單純形法的計算步驟表格單純形法的計算步驟 為了便于理解計算關系，現(xiàn)設計一種計算表，稱為單純形表，其功能與增廣矩陣相似，下面來建立這種計算表。線性規(guī)劃的方程組0111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxczbxaxaxbxaxaxbxaxax1211,1112,122,112101000010000110mmnmnmnm mmnmmmnzxxxxxbaabaabaabccccc 為了便于迭代運算，可將上述方程組寫成為了便于迭代運算，可將上述方程組寫成增廣矩陣形式增廣矩陣形式1211,1112,122,11,1,i 1i 1i 1

2、0 1 000 0 100 0 011 0 00mmnmnmnmmmnmmmmmi i mni i ni izxxxxxbaabaabaabccaccacbjcnmmcccc11BCBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001ziibc 0 0 ijijjacc )min(0kjkjiaab 根據(jù)增廣矩陣設計計算表根據(jù)增廣矩陣設計計算表 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例 題：題：cj 2 3 0 0 0 0cB

3、XBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1-z0 i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 -zi3x23010001/42620100-1/210010 0-1/2cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2

4、4 0 0 0 1 0 0 1 0 0 0 1/4-z-9 i2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412-z-13 0 0 0 -2 0 1/4icj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0-z

5、-14 0 0 -1/2 -1 0 0i 0 0 0 -2 0 1/4-13-z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bXBcB 2 3 0 0 0 0cjicj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0-z-14 0 0 0 -3/2 -1/8 0i 0

6、 0 0 -2 0 1/4-13-z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cji計算步驟計算步驟對于目標函數(shù)求極大情形對于目標函數(shù)求極大情形(1) (1) 按數(shù)學模型確定初始可行基和初始基可行解，按數(shù)學模型確定初始可行基和初始基可行解，建立初始單純形表。建立初始單純形表。(2) (2) 計算各非基變量的檢驗數(shù)，計算各非基變量的檢驗數(shù)，檢查檢驗數(shù)，若所有檢驗數(shù)檢查檢驗數(shù)，若所有檢驗數(shù)則已得到最優(yōu)解，可停止計算。

7、否則轉(zhuǎn)入下一步。則已得到最優(yōu)解，可停止計算。否則轉(zhuǎn)入下一步。 miijijjacc1,njj, 2 , 1, 0(3) (3) 在在jj0,j=m+1,n0,j=m+1,n中，若有某個中，若有某個kk對應對應xkxk的系數(shù)列向量的系數(shù)列向量Pk0Pk0，則此問題是無界，停止計算。，則此問題是無界，停止計算。 否則，轉(zhuǎn)入下一步。否則，轉(zhuǎn)入下一步。(4) (4) 根據(jù)根據(jù)max(jmax(j0)=k0)=k，確定，確定xkxk為換入變量，為換入變量，按按規(guī)則計算規(guī)則計算lklikikiabaab0min(5) (5) 以以alkalk為主元素進行迭代為主元素進行迭代( (即用高斯消去法或稱為即用高斯消去法或稱為旋轉(zhuǎn)運算旋轉(zhuǎn)運算) )，把，把xkxk所對應的列向量所對應的列向量 將將XBXB列中的列中的xlxl換為換為xkxk，得到新的單純形表。反，得到新的單純形表。反復復(2)(2)(5)(5)，直到終止。，直到終止。kkklkmkaaPala120010變變換換第第 行行 練習練習 0,24261553221212121 xxxxxxxxMaxZ 0,24 261