1、 運籌學運籌學（第三版）運籌學教材編寫組 編清華大學出版社 第1章 線性規(guī)劃與單純形法 第4節(jié) 單純型法的計算步驟錢頌迪 制作第1章 線性規(guī)劃與單純形法第4節(jié) 單純型法的計算步驟第4節(jié) 單純型法的計算步驟 根據(jù)以上討論的結果，將求解線性規(guī)劃問題的單純形法的計算步驟歸納如下 如利用單純型表，求解線性規(guī)劃問題。 4.1 單純型表 為了便于理解計算關系，現(xiàn)設計一種計算表，稱為單純形表，其功能與增廣矩陣相似，下面來建立這種計算表。 將(1-22)式與目標函數(shù)組成n+1個變量，m+1個方程的方程組。 線性規(guī)劃的方程組0111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcx

2、cxcxczbxaxaxbxaxaxbxaxax為了便于迭代運算，可將上述方程組寫成增廣矩陣形式01000001000010211211,21, 211, 1121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxz若將z看作不參與基變換的基變量，它與x1,x2,xm的系數(shù)構成一個基，這時可采用行初等變換將c1,c2,cm變換為零，使其對應的系數(shù)矩陣為單位矩陣。得到miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21, 211, 11210001000001000010可根據(jù)上述增廣矩陣設計計算表，

3、表1-2。 miininmimiimmiiimmnmmmmmnmnmnmmBBinmmjaccaccbczaabxcaabxcaabxcxxxxbXCccccc111,111,221, 2222111,1111111100100001表1-2的說明 XB列中填入基變量，這里是x1，x2,，xm； CB列中填入基變量的價值系數(shù)，這里是c1,c2,cm；它們是與基變量相對應的； b列中填入約束方程組右端的常數(shù)； cj行中填入基變量的價值系數(shù)c1,c2,cn； i列的數(shù)字是在確定換入變量后，按規(guī)則計算后填入； 最后一行稱為檢驗數(shù)行，對應各非基變量xj的檢驗數(shù)是miijijnjacc1, 2 , 1,

4、4.2 計算步驟 表1-2稱為初始單純形表，每迭代一步構造一個新單純形表。 計算步驟： (1) 按數(shù)學模型確定初始可行基和初始基可行解，建立初始單純形表。 (2) 計算各非基變量xj的檢驗數(shù)， 檢查檢驗數(shù)，若所有檢驗數(shù) 則已得到最優(yōu)解，可停止計算。否則轉入下一步。 miijijjacc1,njj, 2 , 1, 0 (3) 在j0,j=m+1,n中，若有某個k對應xk的系數(shù)列向量Pk0，則此問題是無界，停止計算。 否則，轉入下一步。 (4) 根據(jù)max(j0)=k，確定xk為換入變量，按規(guī)則計算lklikikiabaab0min (5) 以alk為主元素進行迭代(即用高斯消去法或稱為旋轉運算)

5、，把xk所對應的列向量 將XB列中的xl換為xk，得到新的單純形表。重復(2)(5)，直到終止。行第變換laaaaPmklkkkk010021現(xiàn)用例1的標準型來說明上述計算步驟。 (1) 取松弛變量x3,x4,x5為基變量，它對應的單位矩陣為基。這就得到初始基可行解X(0)=(0,0,8,16,12)T 將有關數(shù)字填入表中，得到初始單純形表，見表1-3。表中左上角的cj是表示目標函數(shù)中各變量的價值系數(shù)。在CB列填入初始基變量的價值系數(shù)，它們都為零。 5432100032maxxxxxxz5 , 2 , 10124164825241321jxxxxxxxxj 目標函數(shù)中各變量的價值系數(shù)。cj 2

6、 3 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 0 x 3 8 1 2 1 0 0 8/2=4 0 x 4 16 4 0 0 1 0 - 0 x 5 12 0 4 0 0 1 12/4=3 -z 0 2 3 0 0 0 1.計算檢驗數(shù)，由它確定為換人變量2.計算，由它確定為換出變量3.確定主元素表 1-3基變量計算非基變量的檢驗數(shù) 各非基變量的檢驗數(shù)為 1=c1-z1=2-(01+04+00)=2 2=c2-z2=3-(02+00+04)=3 填入表1-3的底行對應非基變量處。進行（2），（3）(2) 因檢驗數(shù)都大于零，且 P1，P2有正分量存在， 轉入下一步； (3

7、) max(1,2)=max(2,3)=3，對應的變量 x2為換入變量， 計算 341201628022,minaabminiiii 它所在行對應的x5為換出變量，x2所在列和x5所在行的交叉處4稱為主元素或樞元素(pivot element)進行（4） (4) 以4為主元素進行旋轉運算或迭代運算，即初等行變換，使P2變換為（0,0,1）T,在XB 列中將x2 替換x5 ,于是得到新表1-4. cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 2 1 0 1 0 -1/2 2 0 x4 16 4 0 0 1 0 4 3 x2 3 0 1 0 0 1/4 - -z

8、 -9 2 0 0 0 -3/4 換人變量換出變量主元素(5) 檢查表1-4的所有cj-zj,這時有c1-z1=2；說明x1應為換入變量。重復(2)(4)的計算步驟，得表1-5。 還存在檢驗數(shù)0，繼續(xù)進行。cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 2 1 0 1 0 -1/2 - 0 x4 8 0 0 -4 1 2 4 3 x2 3 0 1 0 0 1/4 12 -z -13 0 0 -2 0 1/4 換人變量換出變量主元素(6) 表1-6最后一行的所有檢驗數(shù)都已為負或零。這表示目標函數(shù)值已不可能再增大，于是得到最優(yōu)解cj 2 3 0 0 0 CB XB b x1 x2 x3 X4 x5