《線性規(guī)劃》034第二章22最優(yōu)基可行解=續(xù)=第六次課

1、問題：若典式中有檢驗數(shù)問題：若典式中有檢驗數(shù) ，但對應的系數(shù)，但對應的系數(shù)中卻有正數(shù)，那么又有什么結論呢？中卻有正數(shù)，那么又有什么結論呢？0r (1,2,)irbim 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法定理定理2.4 (P28)對于對于LP的一個基的一個基B，若，若 且且 ，則對應基則對應基B的基解的基解 x(0)便是便是LP的最優(yōu)解。的最優(yōu)解。10B b 10NBNc B N c 檢驗數(shù)非正檢驗數(shù)非正問題：當一個基可行解的非基變量的檢驗數(shù)不全非正時問題：當一個基可行解的非基變量的檢驗數(shù)不全非正時是是 否最優(yōu)解？如何判別？否最優(yōu)解？如何判別？情形一：情形一：定理定理2.5 (

2、P30)若基可行解若基可行解 x(0) 對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，且相應地且相應地 ，則，則LP無最優(yōu)解無最優(yōu)解(此時此時目標函數(shù)在可行域上無界目標函數(shù)在可行域上無界)。0 (1,2,)r ibim 0r 情形二：情形二：T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，而而 中至少有一個大于零，并且中至少有一個大于零，并且 ，則必存在另一基可行解，則必存在另一基可行解，其對應的目標其對應的目標函數(shù)值比函數(shù)值比 小。小。定理定理2.6 (P31)T12(

3、,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，而而 中至少有一個大于零，并且中至少有一個大于零，并且 ，則必存在另一基可行解，則必存在另一基可行解，其對應的目標其對應的目標函數(shù)值比函數(shù)值比 小。小。情形二：情形二：定理定理2.6 (P31)2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法注：注：(1)、定理定理2.6說明，對于一個說明，對于一個非退化非退化的基可行解，當有某的基可行解，當有某 個檢驗數(shù)個檢驗數(shù) ，而對應系數(shù)，而對應系數(shù) 不全非正時不全非正時此基可行解必不是最優(yōu)解此基可

4、行解必不是最優(yōu)解，此時必，此時必存在改進的存在改進的基可行解?；尚薪?。0r (1,2,)irbim 問題：如何改進基可行解？問題：如何改進基可行解？定理定理2.6也說明，滿足定理也說明，滿足定理2.6的問題必有最優(yōu)解！的問題必有最優(yōu)解！ 對應基解中基變量值部分。對應基解中基變量值部分。 T110200,mbbbB b 對于對于LP的一個基可行解，如果其基分量值都是正的一個基可行解，如果其基分量值都是正的，就稱它是一個的，就稱它是一個；否則；否則(即基分量值有等即基分量值有等于零的于零的)，就稱它為，就稱它為。非退化非退化2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法s.t. 12345

5、12123412335min321532340(1,2,5)ifxxxxxxxxxxxxxxxxix B2對應的基解為對應的基解為 ，且為基可行解。，且為基可行解。(2)T(0,0,1,4,3)x 符合定理符合定理2.6，需改進基可行解。，需改進基可行解。非基變量非基變量x1的檢驗數(shù)的檢驗數(shù)1, 03 以例以例1(P28)為例來考慮：如何改進基為例來考慮：如何改進基(基可行解基可行解)？由由f=6-3x1+3x2可知，若將非基變量可知，若將非基變量x1變成基變量變成基變量(取值從取值從0變成變成正數(shù)，即正數(shù)，即x1逐漸增加逐漸增加)，可以使目標函數(shù)值減小。所以只要目標，可以使目標函數(shù)值減小。所

6、以只要目標函數(shù)的表達式中還存在有負系數(shù)的非基變量，就表明目標函數(shù)函數(shù)的表達式中還存在有負系數(shù)的非基變量，就表明目標函數(shù)值還有減小的可能，從而需要將非基變量與基變量進行對換。值還有減小的可能，從而需要將非基變量與基變量進行對換。把非基變量轉換為基變量，稱為進基。把非基變量轉換為基變量，稱為進基。此處此處x1作為進基變量作為進基變量基基B2對應的典式為：對應的典式為：s.t. 12121213425min633321834530 (1,2,5)ixxxfxxxxxxxxxi (2)對于基對于基B2=( p3，p4，p5 )2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法基基B2對應的典式為：對

7、應的典式為：s.t. 12121213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)對于基對于基B2=( p3，p4，p5 )把非基變量轉換為基變量，稱為進基。把非基變量轉換為基變量，稱為進基。此處此處x1作為進基變量作為進基變量因為基變量總數(shù)是因為基變量總數(shù)是m , 所以換入一個之所以換入一個之后還必須換出一個。后還必須換出一個。把基變量轉換為非基變量，稱為離基。把基變量轉換為非基變量，稱為離基。x1為進基變量，但為進基變量，但x2仍為非基變量，故仍為非基變量，故x2=0。代入。代入、 、 式可得：式可得：怎樣確定離基變量？怎樣確定離基變量？由于

8、隨著由于隨著x1的增加，目標函數(shù)值在減小的增加，目標函數(shù)值在減小 ，當，當x1增加到最大增加到最大1/3時，時，目標函數(shù)會減到最小。目標函數(shù)會減到最小。34511113,48,3xxxxxx 為了保證解的可行性，需要為了保證解的可行性，需要3411511 3,4 8,3000 xxxxxx 解得解得11114,338xxx (舍去舍去)113x 即即而當而當x1 =1/3時，時， x3=0，故用非基變量，故用非基變量x1替換基變量替換基變量x3 ( x3離基離基)。1 4min,3 8 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法基基B2對應的典式為：對應的典式為：s.t. 12121

9、213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)對于基對于基B2=( p3，p4，p5 )把非基變量轉換為基變量，稱為進基。把非基變量轉換為基變量，稱為進基。此處此處x1作為進基變量作為進基變量因為基變量總數(shù)是因為基變量總數(shù)是m , 所以換入一個之所以換入一個之后還必須換出一個。后還必須換出一個。把基變量轉換為非基變量，稱為離基。把基變量轉換為非基變量，稱為離基。怎樣確定離基變量？怎樣確定離基變量？為了保證解的可行性，需要為了保證解的可行性，需要3411511 3,4 8,3000 xxxxxx 11 41min,3 83x 即即而當而當x1

10、=1/3時，時， x3=0，故用非基變量，故用非基變量x1替換基變量替換基變量x3 ( x3離基離基)。得到改進基為得到改進基為基基B1=( p1，p4，p5 ) B1恰為最優(yōu)基恰為最優(yōu)基=011m in0,1, 2, 3iiibbib bi0為典式為典式中約束方中約束方程的右端程的右端常數(shù)常數(shù)00min0,1,2,iriirrrsbbbimbb 若基可行解若基可行解 x(0)對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，而而 中至少有一個大于零，并且中至少有一個大于零，并且 ，則必存在另一基可行解，則必存在另一基可行解，其對應的目標其對應的目標函數(shù)值比函數(shù)值比 小。小。T12(,)

11、rrmrbbb0r 00ib (1,2,)im (0)()f x2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法情形二：情形二：定理定理2.6 (P31) (2)、改進基可行解的求法、改進基可行解的求法(P32)注：注：、把對應于正檢驗數(shù)、把對應于正檢驗數(shù)r 的非基變量的非基變量xr 轉變?yōu)榛兞哭D變?yōu)榛兞?，稱稱 它為它為進基變量進基變量(或換入變量或換入變量)；或基可行解的轉移或基可行解的轉移、從原基變量中選取一個成為非基變量，稱此變量為、從原基變量中選取一個成為非基變量，稱此變量為離離 基變量基變量(或換出變量或換出變量)，此離基變量的下標，此離基變量的下標js由下列最小由下列最小

12、值出現(xiàn)在哪一行取得所確定：值出現(xiàn)在哪一行取得所確定：從而新的基陣與原基陣的差異在于：原基陣的列向量從而新的基陣與原基陣的差異在于：原基陣的列向量 被列向量被列向量pr所代替。所代替。sjpbir為為xr在典式中的正系數(shù)在典式中的正系數(shù)若基可行解若基可行解 x(0)對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，而而 中至少有一個大于零，并且中至少有一個大于零，并且 ，則必存在另一基可行解，則必存在另一基可行解，其對應的目標其對應的目標函數(shù)值比函數(shù)值比 小。小。T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法

13、情形二：情形二：定理定理2.6 (P31) (3)、從原基解的典式導出新基解的典式的方法、從原基解的典式導出新基解的典式的方法(P34)注：注：、若使用計算機編程求解、若使用計算機編程求解LP，可按照，可按照(2.33)(2.37)的的 公式編制程序，以實現(xiàn)舊典式向新典式的轉換；公式編制程序，以實現(xiàn)舊典式向新典式的轉換；、對簡單問題用手工計算時，可以直接對原典式使用、對簡單問題用手工計算時，可以直接對原典式使用 消去法消去法獲得新典式。獲得新典式。2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法為得出為得出B0對應的典式，作如下步驟：對應的典式，作如下步驟：例例4(P35) 求解下列線性規(guī)

14、劃問題：求解下列線性規(guī)劃問題：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi (1)對于對于B0=( p1，p4，p5 )第一個方程只有基變量第一個方程只有基變量x1，其系數(shù)為，其系數(shù)為1第二個方程只有基變量第二個方程只有基變量x4，其系數(shù)為，其系數(shù)為1第三個方程只有基變量第三個方程只有基變量x5，其系數(shù)為，其系數(shù)為1(1)、將方程、將方程的的(-2)倍加到方程倍加到方程中，得中，得(2)、從方程、從方程、中解出中解出x1、 x4，代入目標函數(shù)的表達式。代入目標函數(shù)的表達式。21322xxx 解題步驟：解題步驟：1、首先將原問題化為典

15、式、首先將原問題化為典式(消去法消去法)103020121001101A 解：該問題的解：該問題的系數(shù)矩陣為系數(shù)矩陣為12345(,)p p p p p 顯然，顯然，B0是一個基，因為是一個基，因為0102010001B 10 用它代替第一個約束方程；用它代替第一個約束方程；s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法所以，基陣所以，基陣B0對應的典式為：對應的典式為：解：解：在在B0對應的典式令非基變量對應的典式令非基變量x2=x3=0 , 得得21322xxx 1452,2,5xxx

16、 故故B0對應的基解為對應的基解為 ，且為基可行解。，且為基可行解。(0)T(2,0,0,2,5)x 例例4(P35) 求解下列線性規(guī)劃問題：求解下列線性規(guī)劃問題：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi 解題步驟：解題步驟：2、根據(jù)定理、根據(jù)定理2.4、2.5、2.6判別此判別此 基可行解的最優(yōu)性基可行解的最優(yōu)性(1)對于對于B0=( p1，p4，p5 )也不滿足定理也不滿足定理2.5，但符合定理，但符合定理2.6，故需要改進基可行解。，故需要改進基可行解。對于基對于基B0，不符合定理，不符合定理2.4，故，故 x (0)不是

17、最優(yōu)解。不是最優(yōu)解。s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 從基從基B0=( p1，p4，p5 )對應的典式：對應的典式：2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法解：解：可知，非基變量可知，非基變量x2對應的檢驗數(shù)對應的檢驗數(shù)2, 01 例例4(P35) 求解下列線性規(guī)劃問題：求解下列線性規(guī)劃問題：解題步驟：解題步驟：3、若非最優(yōu)解，根據(jù)定理、若非最優(yōu)解，根據(jù)定理2.6進行改進，直至最優(yōu)基可行解。進行改進，直至最優(yōu)基可行解。(2) 基基B0 改進到基改進到基B1故取故取x2為進基變量。為進基變量。此時此時122322bbb

18、 211, 120300bbb 225 于是于是0222 5min0min,1 1iiibbb 22202bb s=2，即最小值出現(xiàn)在第二，即最小值出現(xiàn)在第二行，對應第二個基變量行，對應第二個基變量x4故故s=2，js=4，則取，則取x4為離基變量。為離基變量。所以得到新基為所以得到新基為B1=( p1，p2，p5 )120011001 1102010011B 10 B1的確為基陣的確為基陣145xxx001,2,min0,irrriisrimbbbbb r=2s.t. 23123234235min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最優(yōu)基可行解的求法

19、最優(yōu)基可行解的求法為得出為得出B1對應的典式，作如下步驟：對應的典式，作如下步驟：例例4(P35)(3)對于對于B1=( p1，p2，p5 )第一個方程只有基變量第一個方程只有基變量x1，其系數(shù)為，其系數(shù)為1第二個方程只有基變量第二個方程只有基變量x2，其系數(shù)為，其系數(shù)為1第三個方程只有基變量第三個方程只有基變量x5，其系數(shù)為，其系數(shù)為1(1)、將方程、將方程的的2倍、倍、(-1)倍加到方程倍加到方程 、中去；中去；(2)、從方程、從方程中解出中解出x2，代入目標函數(shù)的表達式。代入目標函數(shù)的表達式。解：解：基基B0對應的典式：對應的典式：解題步驟：解題步驟：1、求出新基的典式、求出新基的典式(

20、消去法消去法)s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法所以，基陣所以，基陣B1對應的典式為：對應的典式為：解：解：在在B1對應的典式令非基變量對應的典式令非基變量x3=x4=0 , 得得1256,2,3xxx 故故B1對應的基解為對應的基解為 ，且為基可行解。，且為基可行解。(1)T(6,2,0,0,3)x 解題步驟：解題步驟：2、根據(jù)定理、根據(jù)定理2.4、2.5、2.6判別判別 此基可行解的最優(yōu)性此基可行解的最優(yōu)性(3)對于對于B1=( p1，p2，p5 )但符合定理但符合定理

21、2.6，故需要改進基可行解。，故需要改進基可行解。對于基對于基B1，不符合定理，不符合定理2.4，故，故 x (1)不是最優(yōu)解。不是最優(yōu)解。s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 例例4(P35)基基B0對應的典式：對應的典式：s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 從基從基B1=( p1，p2，p5 )對應的典式：對應的典式：2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法解：解：可知，非基變量可知，非基變量x3對應的檢驗數(shù)對應的檢驗數(shù)3, 01 例例4(P35)

22、求解下列線性規(guī)劃問題：求解下列線性規(guī)劃問題：解題步驟：解題步驟：3、若非最優(yōu)解，根據(jù)定理、若非最優(yōu)解，根據(jù)定理2.6進行改進，直至最優(yōu)基可行解。進行改進，直至最優(yōu)基可行解。(4) 基基B1 改進到基改進到基B2故取故取x3為進基變量。為進基變量。此時此時123333bbb 323, 120300bbb 623 于是于是0333min0min3iiibbb 33301bb s=3，即最小值出現(xiàn)在第三，即最小值出現(xiàn)在第三行，對應第三個基變量行，對應第三個基變量x5故故s=3，js=5，則取，則取x5為離基變量。為離基變量。所以得到新基為所以得到新基為B2=( p1，p2，p3 )321100011

23、 2103012011B 30 B2的確為基陣的確為基陣125xxx001,2,min0,irrriisrimbbbbb r=3s.t. 34134234345min232622330 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法為得出為得出B2對應的典式，作如下步驟：對應的典式，作如下步驟：例例4(P35)(5)對于對于B2=( p1，p2，p3)第一個方程只有基變量第一個方程只有基變量x1，其系數(shù)為，其系數(shù)為1第二個方程只有基變量第二個方程只有基變量x2，其系數(shù)為，其系數(shù)為1第三個方程只有基變量第三個方程只有基變量x3，其系數(shù)為，其系數(shù)

24、為1(1)、將方程、將方程加到方程加到方程中去；中去；(3)、從方程、從方程中解出中解出x3，代入方程代入方程與目標函數(shù)中去。與目標函數(shù)中去。解：解：基基B1對應的典式：對應的典式：解題步驟：解題步驟：1、求出新基的典式、求出新基的典式(消去法消去法)(2)、將方程、將方程兩端同除以兩端同除以3，得，得43511133xxx2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法s.t. 4545451452321min133912433111330 (1,2,5)ifxxxxxxxxxxixx 所以，基陣所以，基陣B2對應的典式為：對應的典式為：解：解：在在B2對應的典式令非基變量對應的典式令非

25、基變量x4=x5=0 , 得得1239,4,1xxx 故故B2對應的基解為對應的基解為 ，且為基可行解。，且為基可行解。(2)T(9,4,1,0,0)x (5)對于對于B2=( p1，p2，p3 )例例4(P35) 求解下列線性規(guī)劃問題：求解下列線性規(guī)劃問題：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi 解題步驟：解題步驟：2、根據(jù)定理、根據(jù)定理2.4、2.5、2.6判判 別此基可行解的最優(yōu)性別此基可行解的最優(yōu)性檢驗數(shù)全部非正，檢驗數(shù)全部非正，符合定理符合定理2.4，故，故 x(2)是最優(yōu)解。是最優(yōu)解。由于非基變量對應的檢驗數(shù)由于非

26、基變量對應的檢驗數(shù)42,03 51,03 由定理由定理2.4知知x(2)是該問題的最優(yōu)解，最優(yōu)值為是該問題的最優(yōu)解，最優(yōu)值為f(x(2)=1 。s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法基陣基陣B1對應的典式為：對應的典式為：可見，使用定理可見，使用定理2.6，的確使得，的確使得函數(shù)值在一步步的改進函數(shù)值在一步步的改進!例例4(P35) 備注：備注：基基B0對應的典式：對應的典式：s.t. 4545451452321min133912433111330 (1,2,5)ifxxxxx

27、xxxxxixx 基基B2對應的典式為：對應的典式為：s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法定理定理2.4 (P28)對于對于LP的一個基的一個基B，若，若 且且 ，則對應基則對應基B的基解的基解 x(0)便是便是LP的最優(yōu)解。的最優(yōu)解。10B b 10NBNc B N c 檢驗數(shù)非正檢驗數(shù)非正情形一：情形一：定理定理2.5 (P30)若基可行解若基可行解 x(0) 對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，且相應地且相應地 ，則，則LP無最優(yōu)解無最優(yōu)解(此時此時目標

28、函數(shù)在可行域上無界目標函數(shù)在可行域上無界)。0 (1,2,)r ibim 0r T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)對應的典式中，有某個檢驗數(shù)對應的典式中，有某個檢驗數(shù) ，而而 中至少有一個大于零，并且中至少有一個大于零，并且 ，則必存在另一基可行解，則必存在另一基可行解，其對應的目標其對應的目標函數(shù)值比函數(shù)值比 小。小。情形二：情形二：定理定理2.6 (P31)首先看檢驗數(shù)是否全部非正首先看檢驗數(shù)是否全部非正(即是否滿足定理即是否滿足定理2.4)？若不滿足定理若不滿足定理2.4，即，即存在有正檢驗數(shù)，則用定理存在有正檢驗數(shù)

29、，則用定理2.5、定理、定理2.6來判別。來判別。2.2 2.2 最優(yōu)基可行解的求法最優(yōu)基可行解的求法單純形法的基本過程單純形法的基本過程：(P33)見書見書單純形法：綜合定理單純形法：綜合定理2.42.6，便可得出求解線性規(guī)劃問題，便可得出求解線性規(guī)劃問題LP 的一種方法，稱之為單純形法。的一種方法，稱之為單純形法。第二章第二章 單純形方法單純形方法2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表 第一步，第一步，對于一個已知的可行基對于一個已知的可行基 ，寫出對，寫出對 應的典式及應的典式及B對應的基可行解對應的基可行解x(0)，xB(0)=B-1b=(b10， b20

30、， bm0)T;12(,)mjjjBppp 0 (1,2, )jjn 第二步，第二步，檢查檢驗數(shù)。如果所有檢驗數(shù)檢查檢驗數(shù)。如果所有檢驗數(shù) ， 則則x (0)就是最優(yōu)解。計算結束，否則轉入下一步。就是最優(yōu)解。計算結束，否則轉入下一步。 第三步，第三步，若有某個檢驗數(shù)若有某個檢驗數(shù)r為正數(shù)，且其所對應的系數(shù)為正數(shù)，且其所對應的系數(shù)bi r全全 部非正部非正，則該線性規(guī)劃問題無最優(yōu)解。計算結束，否則轉入，則該線性規(guī)劃問題無最優(yōu)解。計算結束，否則轉入 下一步。下一步。 第四步第四步，若檢驗數(shù)中有些為正數(shù)，且它們所對應的系數(shù)，若檢驗數(shù)中有些為正數(shù)，且它們所對應的系數(shù)bir中有正數(shù)，則需要換基、進行迭代

31、運算。中有正數(shù)，則需要換基、進行迭代運算。 在所有大于零的檢驗數(shù)中選取最大的一個，設對應的在所有大于零的檢驗數(shù)中選取最大的一個，設對應的非基變量為非基變量為xr， 則取則取xr為進基變量，并求最小比值：為進基變量，并求最小比值：由此確定由此確定xj s為離基變量為離基變量( (若上述最小值同時在幾個比值上若上述最小值同時在幾個比值上達到，則選取其中下標最小的變量為離基變量達到，則選取其中下標最小的變量為離基變量) )。然后用然后用pr代代換換pjs，得到新基，得到新基 ，再接下一步。，再接下一步。00m in0,1, 2,iriirrrsbbbimbb B 第五步第五步，求出新基，求出新基 對

32、應的典式以及基可行解對應的典式以及基可行解x (1)，然后，然后以以 取代取代B，x (1)取代取代x (0)，返回第二步。返回第二步。 BB2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表從第二步到第五步的每一次循環(huán)，稱為一次從第二步到第五步的每一次循環(huán)，稱為一次單純形迭代。單純形迭代。2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表給定給定LP的一個基，對應一個典式，一個典式的一個基，對應一個典式，一個典式便對應一個單純形表。便對應一個單純形表。單純形表：是用非基變量表達基變量和目標函數(shù)的單純形表：是用非基變量表達基變量和目標函數(shù)的系數(shù)矩陣系數(shù)矩陣。

33、s.t. 1111min()0BBNNBNfc B bc B N cxxB NxB bx 典式典式(2.12)矩陣表達矩陣表達11B AxB b 檢驗數(shù)檢驗數(shù)對應單純形表對應單純形表的矩陣形式的矩陣形式1111BBc B b c B A cB bB A s.t. (0)0(1,2, )min0 (1,2, )ijjj Rjijjij Rjimffxxb xbxjn 其對應單純形表如下表其對應單純形表如下表2-2(P39)所示：所示：基基 對應對應的典式的典式(2.14) (2.16)120(,)mjjjBppp 表表2-2 基基 對應的單純形表對應的單純形表10(, , ,)smjjjBppp

34、 為該基解對應的目標函數(shù)值，即為目標函數(shù)為該基解對應的目標函數(shù)值，即為目標函數(shù)的典式表達中的常數(shù)。的典式表達中的常數(shù)。2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表1000smbbb 12rn 12rnxxxx1 11 211rnbbbb12sss rs nbbbb12mmm rm nbbbb 全部決全部決策變量策變量全部檢全部檢驗數(shù)驗數(shù)即為目即為目標函數(shù)標函數(shù)的典式的典式表達中表達中的各變的各變量的系量的系數(shù)反號數(shù)反號(基變量基變量取為取為0)即為典式中約束方程的右端常數(shù)，即為典式中約束方程的右端常數(shù)，亦即為該基解的基分量的值。亦即為該基解的基分量的值。典式中約典式中約

35、束方程的束方程的系數(shù)矩陣系數(shù)矩陣第第1行行第第0行行第第s行行第第m行行基變量基變量第第1列列第第0列列第第r列列第第n列列第第2列列1sjjjmxxx 1sjjjmxxx 2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表1000smbbb 12rn 12rnxxxx1 11 211rnbbbb12sss rs nbbbb12mmm rm nbbbb 其中，其中，12,mjjjxxx為基變量，它們所對應的列實為單位列向量。為基變量，它們所對應的列實為單位列向量。 對應的列，對應的列，例如，例如，1jx注意：在注意：在初初始始單純形表單純形表中，決策變中，決策變量行、基變量行

36、、基變量列，均是量列，均是按照下標按照下標從從小到大小到大的順的順序排列的。序排列的。表表2-2 基基 對應的單純形表對應的單純形表10(, , ,)smjjjBppp 111000jjxb =1除除 外，其余元素包括檢驗數(shù)皆為外，其余元素包括檢驗數(shù)皆為0 。111jb 2.32.3單純形法的計算步驟、單純形表單純形法的計算步驟、單純形表用單純形用單純形表表計算線性規(guī)劃問題的步驟計算線性規(guī)劃問題的步驟(P39-40)：(1)、若原線性規(guī)劃問題不是標準型，需先化成標準型，再求、若原線性規(guī)劃問題不是標準型，需先化成標準型，再求出此線性規(guī)劃問題對應于基出此線性規(guī)劃問題對應于基 的典式，并依的典式，并

37、依據(jù)這個典式列出基據(jù)這個典式列出基B0對應的單純形表對應的單純形表T(B0)。120(,)mjjjBppp (2)、在表、在表T(B0)中，除中，除f (0)外，若第外，若第0列元素都列元素都0，第，第0行元素都行元素都0，則該表對應的基解便為問題的最優(yōu)解，稱最優(yōu)基可行解，則該表對應的基解便為問題的最優(yōu)解，稱最優(yōu)基可行解對應的單純形表為對應的單純形表為最優(yōu)解表最優(yōu)解表。計算結束，否則轉入下一步。計算結束，否則轉入下一步。檢驗數(shù)檢驗數(shù)為可行解為可行解(3)、若、若r 0，且且在表在表T(B0)中中r 所在列的其他元素都所在列的其他元素都0，則該，則該問題問題無無最優(yōu)解最優(yōu)解。計算結束，否則轉入下一步。計算結束，否則轉入下一步?？疾闄z驗數(shù)，即第考查檢驗數(shù)，即第0行元素行元素用定理用定理2.4考查考查用定理用定理2.5考查考查畫