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

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

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

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

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

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

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

7、應(yīng)的典式為：s.t. 12121213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)對(duì)于基對(duì)于基B2=( p3，p4，p5 )把非基變量轉(zhuǎn)換為基變量，稱(chēng)為進(jìn)基。把非基變量轉(zhuǎn)換為基變量，稱(chēng)為進(jìn)基。此處此處x1作為進(jìn)基變量作為進(jìn)基變量因?yàn)榛兞靠倲?shù)是因?yàn)榛兞靠倲?shù)是m , 所以換入一個(gè)之所以換入一個(gè)之后還必須換出一個(gè)。后還必須換出一個(gè)。把基變量轉(zhuǎn)換為非基變量，稱(chēng)為離基。把基變量轉(zhuǎn)換為非基變量，稱(chēng)為離基。x1為進(jìn)基變量，但為進(jìn)基變量，但x2仍為非基變量，故仍為非基變量，故x2=0。代入。代入、 、 式可得：式可得：怎樣確定離基變量？怎樣確定離基變量？由于

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

9、213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)對(duì)于基對(duì)于基B2=( p3，p4，p5 )把非基變量轉(zhuǎn)換為基變量，稱(chēng)為進(jìn)基。把非基變量轉(zhuǎn)換為基變量，稱(chēng)為進(jìn)基。此處此處x1作為進(jìn)基變量作為進(jìn)基變量因?yàn)榛兞靠倲?shù)是因?yàn)榛兞靠倲?shù)是m , 所以換入一個(gè)之所以換入一個(gè)之后還必須換出一個(gè)。后還必須換出一個(gè)。把基變量轉(zhuǎn)換為非基變量，稱(chēng)為離基。把基變量轉(zhuǎn)換為非基變量，稱(chēng)為離基。怎樣確定離基變量？怎樣確定離基變量？為了保證解的可行性，需要為了保證解的可行性，需要3411511 3,4 8,3000 xxxxxx 11 41min,3 83x 即即而當(dāng)而當(dāng)x1

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

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

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

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

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

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

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

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

18、 211, 120300bbb 225 于是于是0222 5min0min,1 1iiibbb 22202bb s=2，即最小值出現(xiàn)在第二，即最小值出現(xiàn)在第二行，對(duì)應(yīng)第二個(gè)基變量行，對(duì)應(yīng)第二個(gè)基變量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對(duì)應(yīng)的典式，作如下步驟：對(duì)應(yīng)的典式，作如下步驟：例例4(P35)(3)對(duì)于對(duì)于B1=( p1，p2，p5 )第一個(gè)方程只有基變量第一個(gè)方程只有基變量x1，其系數(shù)為，其系數(shù)為1第二個(gè)方程只有基變量第二個(gè)方程只有基變量x2，其系數(shù)為，其系數(shù)為1第三個(gè)方程只有基變量第三個(gè)方程只有基變量x5，其系數(shù)為，其系數(shù)為1(1)、將方程、將方程的的2倍、倍、(-1)倍加到方程倍加到方程 、中去；中去；(2)、從方程、從方程中解出中解出x2，代入目標(biāo)函數(shù)的表達(dá)式。代入目標(biāo)函數(shù)的表達(dá)式。解：解：基基B0對(duì)應(yīng)的典式：對(duì)應(yīng)的典式：解題步驟：解題步驟：1、求出新基的典式、求出新基的典式(

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

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

22、求解下列線性規(guī)劃問(wèn)題：求解下列線性規(guī)劃問(wèn)題：解題步驟：解題步驟：3、若非最優(yōu)解，根據(jù)定理、若非最優(yōu)解，根據(jù)定理2.6進(jìn)行改進(jìn)，直至最優(yōu)基可行解。進(jìn)行改進(jìn)，直至最優(yōu)基可行解。(4) 基基B1 改進(jìn)到基改進(jìn)到基B2故取故取x3為進(jìn)基變量。為進(jìn)基變量。此時(shí)此時(shí)123333bbb 323, 120300bbb 623 于是于是0333min0min3iiibbb 33301bb s=3，即最小值出現(xiàn)在第三，即最小值出現(xiàn)在第三行，對(duì)應(yīng)第三個(gè)基變量行，對(duì)應(yīng)第三個(gè)基變量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對(duì)應(yīng)的典式，作如下步驟：對(duì)應(yīng)的典式，作如下步驟：例例4(P35)(5)對(duì)于對(duì)于B2=( p1，p2，p3)第一個(gè)方程只有基變量第一個(gè)方程只有基變量x1，其系數(shù)為，其系數(shù)為1第二個(gè)方程只有基變量第二個(gè)方程只有基變量x2，其系數(shù)為，其系數(shù)為1第三個(gè)方程只有基變量第三個(gè)方程只有基變量x3，其系數(shù)為，其系數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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