單純形法原理講解課件

1、單純形法原理講解 本節(jié)通過一個(gè)引例，可以了解利用單純形法求解線性規(guī)劃問題的思路，并將每一次的結(jié)果與圖解法作一對(duì)比，其幾何意義更為清楚。單純形法原理講解引例引例（上一章例）（上一章例）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步 確定初始基

2、可行解 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 。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ù)z

3、xx02312檢驗(yàn)數(shù)檢驗(yàn)數(shù)0 時(shí)，時(shí)， 無解無解換基，繼續(xù)換基，繼續(xù)xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。換入？基變量換入？基變量換出？基變量換出？基變量考慮將考慮將 或或 換入為基變換入為基變量量21 xx單純形法原理講解第4步 基變換 換入基變量：zxxxx0230121122換入變量 x2（即選最大非負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量）一般選取一般選取 對(duì)應(yīng)的變量),max(2121, xx,02, 1均可均可換入。單純形法原理講解 換出變量使換入的變量越大越好同時(shí)，新的解要可行。選非負(fù) 的最小者對(duì)應(yīng)的變量換出i3241522 8 20 16 - 4 0 12 40 min

4、(8 / 2,12 / 4)3xxxxxxx2x為換入變量，應(yīng)換出 ？ 變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx3)4/12, 2/8min(0,min2323222121kaababab思考：當(dāng) 時(shí)會(huì)怎樣？02ka單純形法原理講解因此，基由 變?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)

5、解）2x為換入變量，應(yīng)換出 變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx)(543pppb單純形法原理講解 )0,16,2,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得

6、一基可行解令：代入目標(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é)合圖形法分析（單純形法的幾何意義）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(xxz

7、xx目標(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ī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單單純形法迭代原理純形法迭代原理。單純形法原理講解 觀察法:直接觀察得到初始可行基 約束條件: 加入松弛變量即形成可行基。（下頁） 約束條件: 加入非負(fù)人工變量, 以后討論. 1、初始基可行解的確定單純形法原理講解 0,.,. . . 2111221122111111nmnmnmmmmnnmmnnmmxxx

8、bxaxaxbxaxaxbxaxax1 1、初始基可行解的確定、初始基可行解的確定 不妨設(shè)不妨設(shè) 為松弛變量，為松弛變量，則約束方程組可表示為則約束方程組可表示為mxxx,21單純形法原理講解 是一初始基可行解。有：令：)0,.,0 , 0 ,.,(),.2 , 1( 0. . . . 21111211222111111miinmnmnmmmmmnnmmnnmmbbbxmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的確定、初始基可行解的確定單純形法原理講解2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx

9、11211222111111. . . . 行解：一般情況下，對(duì)于基可單純形法原理講解 1 1221111111111. ().() . ()nnnnjjmmmjjj mj mmmnnmnmiijiijjij mizc xc xc xc ba xcba xcxc xcbcc ax2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別代入目標(biāo)函數(shù)有：單純形法原理講解 jnmjjjjjjnmjjjmiijijmiiixzzzcxzczzaczbcz1010110 )()( 檢驗(yàn)數(shù)令：令：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別單純形法原理講解 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部

10、 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最優(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的kkx0的kmkmxmiakmi,.2,1,0,2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別單純形法原理講解 kmkmmmmkmkmkmkmxabxxabxxabx222111

11、. . . , , 0, 00zxxzzxakmkmkmkmkim當(dāng)即解都可行，對(duì)任意（4）之證明：）之證明：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別單純形法原理講解最優(yōu)解判斷小結(jié) （用非基變量的檢驗(yàn)數(shù)）所有 基變量中有非零人工變量某非基變量檢驗(yàn)數(shù)為零唯一最優(yōu)解無窮多最優(yōu)解無可行解對(duì)任一 有 換基繼續(xù)yyyynnn無界解njjika000jjika000jjika000以后以后討論討論單純形法原理講解3、基變換 換入變量確定 對(duì)應(yīng)的 為換入變量. (一般)kmjmj)0(maxkmx注意注意：只要只要 對(duì)應(yīng)的變量對(duì)應(yīng)的變量 均可作為換入變量均可作為換入變量0jjxkmkmxzz0此時(shí)

12、，目標(biāo)函數(shù)此時(shí)，目標(biāo)函數(shù)單純形法原理講解 換出變量確定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100. .0 0 min3 3、基變換、基變換kmkmxzz0kmxz 大大大大（在可行的范圍內(nèi)）（在可行的范圍內(nèi)）lx單純形法原理講解4、迭代運(yùn)算 mmnkmmmmklmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111. . 1 . . . . . 1 . . . . . 1 . 寫成增廣矩陣的形式,進(jìn)行迭代.單純形法原理講解例： txxxzbxxx xx)12,16,8,0,0(320 121681 0 0 4 00 1 0 0 40