第二章 線性規(guī)劃及單純型法

1、第二章線性規(guī)劃及單純型法 例: 生產(chǎn)計(jì)劃問題III資資源源限限量量設(shè)設(shè)備備原原材材料料 A原原材材料料 B1402048 臺(tái)臺(tái)時(shí)時(shí)16kg12kg利利潤潤23產(chǎn)品產(chǎn)品I產(chǎn)品產(chǎn)品2x1x2x1x2zIII資資源源限限量量設(shè)設(shè)備備原原材材料料A原原材材料料B1402048臺(tái)臺(tái)時(shí)時(shí)16kg12kg利利潤潤23 0,.,),(.),(.),(.)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax0,., 0,.,. 2121221122222121112121112211mnmnmnmmnnnnnn

2、bbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax目標(biāo)函數(shù)最大目標(biāo)函數(shù)最大約束條件等式約束條件等式?jīng)Q策變量非負(fù)決策變量非負(fù) njxmibxaxcZjinjjijnijj,.,2 , 1 0,.2 , 1 max11 ),.cc,(cC ,.2 , 1 0max212121n211 b.bb ba.aa Px.xxXnjxbxPCXZmmjjjjnjnijj其中： 0.000 ),.,( . 0 max 211111nmnmnPPPaaaaAXbAXCXZ決策變量向量 -X 價(jià)值向量 -C 資源向量0.000 ),.,( . 0 max 3211111bPPPaaaaAX

3、bAXCXZmnmnC C價(jià)值向量?jī)r(jià)值向量b b資源向量資源向量X X決策變量向量決策變量向量 0, kkkkkxxxxx令Max x6 x7kx ：標(biāo)準(zhǔn)形為0,7 )(232 )( 7 )( 00)( 32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0)4x1 164 x2 169 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域9 8 7 6

4、5 4 3 2 1 0 |123456789x1x2x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16x26 5 4 3 2 1 0 |123456789x16 5 4 3 2 1 0 x2|123456789x1 x2x118 16 14 12 10 8 6 4 2 0 |246810121416

5、18x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 1618 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域可行域ABCDE18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1

6、+ x2 16ABCDE (8,0)(0,6.8)x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =189 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)，目標(biāo)函數(shù)不同時(shí)，等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目標(biāo)函數(shù)等目標(biāo)函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)

7、解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)目標(biāo)函數(shù)不同時(shí)等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目標(biāo)函數(shù)等目標(biāo)函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)目標(biāo)函數(shù)不同時(shí)等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目標(biāo)函數(shù)等目標(biāo)函數(shù)等值線的斜率值線的斜

8、率最優(yōu)解最優(yōu)解目標(biāo)函數(shù)等值線的斜率目標(biāo)函數(shù)等值線的斜率最優(yōu)解最優(yōu)解v線性規(guī)劃解的概念線性規(guī)劃解的概念v線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 （單純形法原理）（單純形法原理）標(biāo)準(zhǔn)型可行解:滿足AX=b, X=0的解X稱為線性規(guī)劃問題的可行解。最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。0 max XbAXCXZ 基：若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規(guī)劃問題的一個(gè)基。不妨設(shè)：),.,(,.,.,.,11111mmmmmPPaaaaBjPjXjX , j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。 求解 nmnnmmmmmmm

9、mmmxaaxaabbxaaxaa.11111111111基解：稱上面求出的X解為基解。基可行解：非負(fù)的基解X稱為基可行解可行基：對(duì)應(yīng)基可行解的基稱為可行基TmBxxxX).,(210.21nmmxxx)0,.,0,0,.,(21mbbbX T基變量令 可求出：TmBxxxX).,(21 線性規(guī)劃解的關(guān)系圖可行解可行解 基可行解基可行解 最優(yōu)解？最優(yōu)解？ 例：求基解、基可行解、最優(yōu)解。max, ,.,zxxxxxxxxxxxii235210401251231312425x1x2x5x4x3z1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4

10、 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基是否基可行解可行解最優(yōu)解最優(yōu)解解：解： 基本概念凸集：為凸集。K），則10（，KX ）1（X連線上的一切點(diǎn)KX，KX對(duì)維歐氏空間的一點(diǎn)集，n是k設(shè)）2（）1（）2（）1（ 頂點(diǎn):若K是凸集，XK；若X不能用不同的兩點(diǎn) 的線性組合表示為： 則X為頂點(diǎn). KXKX)2()1(和) 10( )1 ()2()1 (XXX凸集凸集 凸組合： .,.,., 1,.,2 , 1, 10,.,.,)()1()()2(2111

11、1)()1的凸組合為則使且若存在個(gè)點(diǎn)維向量空間中的是設(shè)（kkkkiiikkXXXXXXXkiknXXX n=2，k=3定理1: 若線性規(guī)劃問題存在可行域, 則其可行域: 是凸集. 基本定理證明:0, , 0,)2()2()1()1()2()1()2()1(XbAXXbAXXXDXDX則有：設(shè)：)0,XbAXXD bbbAXAXXXAAXXX )1 ( )1 ( )1 (0)2()1()2()1(代入約束條件，有：將顯然，1)(0 )1 ()2()1()2()1(XXXXXX：連線上的任意一點(diǎn)，則和為令只要驗(yàn)證只要驗(yàn)證X X在在D D中即可中即可是凸集。因此，DDX, 引理：可行解X為基可行解

12、X的正分量對(duì)應(yīng)的列向量線性無關(guān) 定理3：若可行域有界，線性規(guī)劃 問題的目標(biāo)函數(shù)一定可以在 其可行域的頂點(diǎn)上達(dá)到最優(yōu)。 定理2：線性規(guī)劃問題的基可性解X 對(duì)應(yīng)于可行域D的頂點(diǎn)。 證明：反證法。分兩步。幾點(diǎn)結(jié)論： 線性規(guī)劃問題的可行域是凸集。 基可行解與可行域的頂點(diǎn)一一對(duì)應(yīng)，可行域有有限多個(gè)頂點(diǎn)。 最優(yōu)解必在頂點(diǎn)上得到。求解LP的基本思路2.3 單純形法原理 本節(jié)通過一個(gè)引例，可以了解利用本節(jié)通過一個(gè)引例，可以了解利用單純形法求解線性規(guī)劃問題的思路，并單純形法求解線性規(guī)劃問題的思路，并將每一次的結(jié)果與圖解法作一對(duì)比，其將每一次的結(jié)果與圖解法作一對(duì)比，其幾何意義更為清楚。幾何意義更為清楚。引例引例（

13、上一章例）（上一章例）0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz求解線性規(guī)劃問題的基本思路1、構(gòu)造初始可行基；2、求出一個(gè)基可行解（頂點(diǎn)）3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；4、基變化，轉(zhuǎn)2。要保證目標(biāo)函數(shù)值比 原來更優(yōu)。從線性規(guī)劃解的性質(zhì)可知求解從線性規(guī)劃解的性質(zhì)可知求解線性規(guī)劃問題的基本思路。線性規(guī)劃問題的基本思路。第1步 確定初始基可行解 1 0 00 1 00 0 1),(543PPPB令：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根據(jù)根據(jù)顯然顯然 ， 可構(gòu)成初等可行基可構(gòu)成初等可行基B

14、 。543,PPP 為基變量543,xxx 第2步 求出基可行解 )12,16, 8 , 0 , 0(, 0320 )0()0(2121XXxxxxZ得一基可行解令：代入目標(biāo)函數(shù) 4 12 416 2 8 2514213xxxxxxx基變量用非基基變量用非基變量表示，并變量表示，并令非基變量為令非基變量為 0時(shí)對(duì)應(yīng)的解時(shí)對(duì)應(yīng)的解是否是最優(yōu)解？第3步 最優(yōu)性檢驗(yàn)分析目標(biāo)函數(shù)檢驗(yàn)數(shù)檢驗(yàn)數(shù)0 時(shí)，時(shí)， 無解無解換基，繼續(xù)換基，繼續(xù)xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。換入？基變量換入？基變量換出？基變量換出？基變量考慮將考慮將 或或 換入為基變換入為基變量量21 xx第

15、4步 基變換 換入基變量：換入變量 2x（即選最大非負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量）一般選取一般選取 對(duì)應(yīng)的變量),max(2121, xx,02, 1均可均可換入。 換出變量使換入的變量越大越好同時(shí)，新的解要可行。選非負(fù) 的最小者對(duì)應(yīng)的變量換出i為換出變量52254233)4/12,2/8min( 04 12 0 16 02 8 xxxxxxx2x為換入變量，應(yīng)換出 ？ 變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx思考：當(dāng) 時(shí)會(huì)怎樣？02ka仍然為非基仍然為非基變量的變量的X1為為0X3 、X4 、X5均為均為0

16、,其中變成非基其中變成非基變量的那個(gè)為變量的那個(gè)為0保證所有保證所有原基變量原基變量0, 最小最小對(duì)應(yīng)變量對(duì)應(yīng)變量更改為更改為0因此，基由 變?yōu)锽PPP()342 轉(zhuǎn)第轉(zhuǎn)第2步：基變量用非基變量表示。步：基變量用非基變量表示。 第第3步：最優(yōu)性判斷步：最優(yōu)性判斷 檢驗(yàn)數(shù)檢驗(yàn)數(shù) 存在正，按第存在正，按第4步換基繼續(xù)迭代步換基繼續(xù)迭代 均非正，停止均非正，停止 （這時(shí)的解即是最優(yōu)解）（這時(shí)的解即是最優(yōu)解）2x為換入變量，應(yīng)換出 變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx)(543PPPB )0,16,2,

17、3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù))0 ,16, 2 , 3 , 0(, 04329 41 3 416 21 2 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù)轉(zhuǎn)轉(zhuǎn) 第第2步步 繼續(xù)迭代, 可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標(biāo)函數(shù)為：最優(yōu)值最優(yōu)解 結(jié)合圖形法分析（單純形法的幾何意義）

18、6 5 4 3 2 1 0 x2|123456789x1)0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù)43)3()2(125.05.114)4,0,0,2,4()0,8 ,0,3,2(xxZXX目標(biāo)函數(shù)為：43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標(biāo)函數(shù)為：A(0,3)B(2,3)C(4,2)D(4,0)單純形法迭代原理單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一

19、般的線性規(guī)劃模型的求解方法單單純形法迭代原理純形法迭代原理。 觀察法:直接觀察得到初始可行基 約束條件: 加入松弛變量即形成可行基。（下頁） 約束條件: 加入非負(fù)人工變量, 以后討論. 1、初始基可行解的確定 0,.,. . . 2111221122111111nmnmnmmmmnnmmnnmmxxxbxaxaxbxaxaxbxaxax1 1、初始基可行解的確定、初始基可行解的確定 不妨設(shè)不妨設(shè) 為松弛變量，則為松弛變量，則約束方程組可表示為約束方程組可表示為mxxx,21 是一初始基可行解。有：令：)0,.,0 , 0 ,.,(),.2 , 1( 0. . . . 2111121122211

20、1111miinmnmnmmmmmnnmmnnmmbbbXmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的確定、初始基可行解的確定2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx11211222111111. . . . 行解：一般情況下，對(duì)于基可 nmjmijijijmiiinnmmjnmjmjmmjnmjjnnxaccbcxcxcxabcxabcxcxcxcZ11111111112221)( . )(.)( .代入目標(biāo)函數(shù)，有：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 jnmjjjjjjn

21、mjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最有解。 )0,.0 ,.,(21)0(mbbbXnmjj,.,1, 0)0(Xnmjj,.,1 02 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 （3）無窮多最優(yōu)解判定定理：若： 且存在某一個(gè)非基變量 則存在無窮多最優(yōu)解。（4）無界解判定定理：若有某一個(gè)非基 變量 并且對(duì)應(yīng)的非基變量的系數(shù) 則具有無界解。 nmjj,.,1, 00

22、的kkx0的kmkmxmiakmi,.2,1,0,2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 kmkmmmmkmkmkmkmxabxxabxxabx222111. . . , , 0, 00ZxxZZxakmkmkmkmkim當(dāng)即解都可行，對(duì)任意（4）之證明：）之證明：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別入基變量大于入基變量大于0，其余，其余仍為非基變量等于仍為非基變量等于0最優(yōu)解判斷小結(jié) （用非基變量的檢驗(yàn)數(shù)）所有 基變量中有非零人工變量某非基變量檢驗(yàn)數(shù)為零唯一最優(yōu)解無窮多最優(yōu)解無可行解對(duì)任一 有 換基繼續(xù)YYYYNNN無界解Njjika000jjika000jjika

23、000以后以后討論討論3、基變換 換入變量確定 對(duì)應(yīng)的 為換入變量. (一般)kmjmj)0(maxkmx注意注意：只要只要 對(duì)應(yīng)的變量對(duì)應(yīng)的變量 均可作為均可作為換入變量換入變量0jjxkmkmxZZ0此時(shí)，目標(biāo)函數(shù)此時(shí)，目標(biāo)函數(shù)入基變量大于入基變量大于0，其余，其余仍為非基變量等于仍為非基變量等于0 換出變量確定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100. .0 0 min3 3、基變換、基變換kmkmxZZ0),.,1(kmmixi（在可行的范圍內(nèi)）（在可行的范圍內(nèi)）入基變量大于入基變量大于0，其余，其余仍為非基變量等于仍為非

24、基變量等于04、迭代運(yùn)算 mlmnkmmmmklmlmnkmmnkmmmlbbbaaaaaaaaabxxxxxx11ln1111111. . 1 . . . . . 1 . . . . . 1 . 寫成增廣矩陣的形式,進(jìn)行迭代.入基入基變量變量出基出基變量變量0,.,1,.,0?例： TXxxZbxxx xx)12,16,8,0,0(320 121681 0 0 4 00 1 0 0 40 0 1 2 1 )0(21543211x3x2x4x5xb4 4、迭代運(yùn)算、迭代運(yùn)算非基變量非基變量基變量基變量001通過初等行變通過初等行變換化主列為換化主列為主元主元 TXxxZ)0,16,2,3,0(

25、 432931621/4 0 0 1 00 1 0 0 41/2- 0 1 0 1)1(511x3x2x4x5xb4 4、迭代運(yùn)算、迭代運(yùn)算檢驗(yàn)數(shù)檢驗(yàn)數(shù)2.3 2.3 單純形法迭代原理單純形法迭代原理 為書寫規(guī)范和便于計(jì)算，對(duì)單純形法的計(jì)算設(shè)計(jì)了單純形表。每一次迭代對(duì)應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計(jì)算線性規(guī)劃問題的步驟。 0. . . . 111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax 單純形表0 . 1. 1 0 . . .

26、 1 0. 1 0 . . Z-211211212111121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxE單位陣N非基陣基變量XB非基變量XNN0 單純形表 將約束方程組和目標(biāo)函數(shù)的系數(shù)用增廣矩陣的形式寫出來xxxxmn12 2 1 0 0 0 jcBCbBXjjzc檢驗(yàn)數(shù)bbm1xxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表 24/65/1minA0znmcccc21C已知xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表A0z)0 , 0 ,(1mbbX基可行解：?jiǎn)渭冃?/p>

27、表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：有時(shí)不有時(shí)不寫此項(xiàng)寫此項(xiàng)單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：jcmjjaa1j單純形表結(jié)構(gòu) 單純形表單

28、純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1km 設(shè)此為主列設(shè)此為主列klmlkimkimiiabaab0minl主行主行單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1km lkmla,主元主元用單純形表求解LP問題0,524261552max212121221xxxxxxxxxz例、用單純形表求解例、用單純形表求解LPLP問題問題解：化標(biāo)準(zhǔn)型0,524261550002

29、max515214213254321xxxxxxxxxxxxxxxz 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBX1x3x2x4x5xjjzc3x4x5x 24/65/1min主元化為1主列單位向量 換出 換入1x4x表表1：列初始單純形表：列初始單純形表 （單位矩陣對(duì)應(yīng)的變量為基變量）（單位矩陣對(duì)應(yīng)的變量為基變量）正檢驗(yàn)數(shù)中最大者對(duì)正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列應(yīng)的列為主列 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6

30、1 0 1/3 0 -1/3 0 jcBCbBX1x3x2x4x5xjjzc3x1x5x 15/524/26/4min 0*5 2*2/6 +0*4/61- 2/3=表表2：換基：換基 （初等行變換，主列化為單位向量，主元為（初等行變換，主列化為單位向量，主元為1）檢驗(yàn)數(shù)檢驗(yàn)數(shù)0確定主列確定主列 最小最小確定主列確定主列主元主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 jcBCbBX1x3x2x4x5xjjzc3x1x2x min檢驗(yàn)數(shù)0，則目標(biāo)函數(shù)不可

31、能實(shí)現(xiàn)最優(yōu)。例: 求解線性規(guī)劃問題0,1 232 411 2 332131321321321xxxxxxxxxxxxxxMinZ3213xxxMaxz一、大 M 法 0,1 23 2 411 2 00376543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxMinZ7654321003MxMxxxxxxMaxz一、大 M 法解:l加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn)加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn) 化化, , 加入人工變量構(gòu)造初始可行基加入人工變量構(gòu)造初始可行基. . 求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解

32、。j 0一、大 M 法l用單純形法求解（見下頁）。用單純形法求解（見下頁）。目標(biāo)函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu);約束條件也不是原來的約束條件M為常數(shù)，運(yùn)算方法為常數(shù)，運(yùn)算方法同基本單純形法同基本單純形法 1 -2 1 -4 1 2 -2 0 1 3-63-6M M -1 3M-1M M -1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11 -M x x6 3 -M x x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0

33、0 1 0 0 - M - M x x6 x x7 i表表1（初始單純形表）（初始單純形表）一、大 M 法（單純形法求解） 3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1x x1 x x2 x x3 0 x x4 10 -M x x6 1 -1 x x3 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M - M - M x x6 x x7 i一、大 M 法（單純形法求解）表表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1

34、-1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 i 2 -5 1 -2 0 1 1-1-M -1M -1 -M-M - M - M x x6 x x7 i表表3一、大 M 法（單純形法求解） 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0

35、0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3-M 2/3-MM 2/3-M - M - M x x6 x x7 i表表4一、大 M 法（單純形法求解）914321xxx檢驗(yàn)數(shù)均非正，此檢驗(yàn)數(shù)均非正，此為最終單純形表為最終單純形表M在計(jì)算機(jī)上處理困難。分兩個(gè)階段處理先求初始基，再求最優(yōu)解。二、兩階段法二、兩階段法原問題的原問題的初始基初始基二、兩階段法 第一階段: 構(gòu)造如下的線性規(guī)劃問題0.,., . . . , 121221122222212111121211121mnnnmmnnmnmmnnnnnnmnnnxxxxxbxxaxaxabxxaxaxabx

36、xaxaxaxxxMin 用單純形法求解上述問題用單純形法求解上述問題,若若=0,進(jìn)進(jìn)入第二階段入第二階段,否則否則,原問題無可行解。原問題無可行解。 第二階段：去掉人工變量，還原目標(biāo)函第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。數(shù)系數(shù)，做出初始單純形表。 用單純形法求解即可。用單純形法求解即可。二、兩階段法二、兩階段法下面舉例說明，仍用大M法的例。0,1 232 411 232131321321xxxxxxxxxxx3213xxxMaxz例：二、兩階段法二、兩階段法 0,1 23 2 411 2 765432173165321432176xxxxxxxxxxxxxxxxxxx

37、xxMin二、兩階段法二、兩階段法l構(gòu)造第一階段問題并求解構(gòu)造第一階段問題并求解解：解：用單純形法求解用單純形法求解二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0 x x1 x x2 x x3 0 x x4 11 -1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 - 1 x x7 i i表表1jjzc -1 - -2 1 1 - -3 - 1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10 -1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5 x x6i二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ）表表2jjzc -5 4 -2 - 1 - -