單純形法原理講解課件

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

根據(jù)顯然，可構(gòu)成初等可行基B。

為基變量第1步確定初始基可行解根據(jù)顯然，

第2步求出基可行解

基變量用非基變量表示，并令非基變量為0時(shí)對(duì)應(yīng)的解是否是最優(yōu)解？第2步求出基可行解基變量用非基變量表示，并令非基第3步最優(yōu)性檢驗(yàn)分析目標(biāo)函數(shù)檢驗(yàn)數(shù)<=0時(shí)，最優(yōu)解>0時(shí)，無解換基，繼續(xù)只要取或的值可能增大。換入？基變量換出？基變量考慮將或換入為基變量第3步最優(yōu)性檢驗(yàn)分析目標(biāo)函數(shù)檢驗(yàn)數(shù)<=0時(shí)，最優(yōu)解無第4步基變換換入基變量：換入變量（即選最大非負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量）一般選取對(duì)應(yīng)的變量均可換入。第4步基變換換入基變量：換入變量（即選換出變量使換入的變量越大越好同時(shí)，新的解要可行。選非負(fù)的最小者對(duì)應(yīng)的變量換出為換入變量，應(yīng)換出？變量。思考：當(dāng)時(shí)會(huì)怎樣？換出變量使換入的變量越大越好選非負(fù)的最小者對(duì)應(yīng)的變量換出因此，基由變?yōu)檗D(zhuǎn)第2步：基變量用非基變量表示。

第3步：最優(yōu)性判斷檢驗(yàn)數(shù)存在正，按第4步換基繼續(xù)迭代均非正，停止（這時(shí)的解即是最優(yōu)解）為換入變量，應(yīng)換出

變量。因此，基由轉(zhuǎn)第2步：基變量用非基變量表示。為換入變量，應(yīng)換

轉(zhuǎn)第2步轉(zhuǎn)第2步

繼續(xù)迭代,可得到:最優(yōu)值Ｚ＝１４最優(yōu)解繼續(xù)迭代,可得到:最優(yōu)值Ｚ＝１４最優(yōu)解結(jié)合圖形法分析（單純形法的幾何意義）6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1A(0,3)B(2,3)C(4,2)D(4,0)結(jié)合圖形法分析（單純形法的幾何意義）x2| | | | | 單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法——單純形法迭代原理。單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思觀察法:直接觀察得到初始可行基≤約束條件:加入松弛變量即形成可行基。（下頁）≥約束條件:加入非負(fù)人工變量,以后討論.1、初始基可行解的確定觀察法:直接觀察得到初始可行基1、初始基可行解的確定1、初始基可行解的確定

不妨設(shè)為松弛變量，則約束方程組可表示為1、初始基可行解的確定不妨設(shè)

1、初始基可行解的確定1、初始基可行解的確定2、最優(yōu)性檢驗(yàn)與解的判別2、最優(yōu)性檢驗(yàn)與解的判別

2、最優(yōu)性檢驗(yàn)與解的判別代入目標(biāo)函數(shù)有：2、最優(yōu)性檢驗(yàn)與解的判別代入目標(biāo)函數(shù)有：

2、最優(yōu)性檢驗(yàn)與解的判別2、最優(yōu)性檢驗(yàn)與解的判別

(1)最優(yōu)解判別定理：若：為基可行解，且全部則為最優(yōu)解。（2）唯一最優(yōu)解判別定理：若所有則存在唯一最優(yōu)解。2、最優(yōu)性檢驗(yàn)與解的判別(1)最優(yōu)解判別定理：若：2、最優(yōu)性檢驗(yàn)與解的判別

（3）無窮多最優(yōu)解判定定理：若：且存在某一個(gè)非基變量則存在無窮多最優(yōu)解。（4）無界解判定定理：若有某一個(gè)非基變量并且對(duì)應(yīng)的非基變量的系數(shù)

則具有無界解。

2、最優(yōu)性檢驗(yàn)與解的判別（3）無窮多最優(yōu)解判定定理：若：2、最優(yōu)性檢驗(yàn)與解的判別

（4）之證明：2、最優(yōu)性檢驗(yàn)與解的判別（4）之證明：2、最優(yōu)性檢驗(yàn)與解的判別最優(yōu)解判斷小結(jié)

（用非基變量的檢驗(yàn)數(shù)）所有基變量中有非零人工變量某非基變量檢驗(yàn)數(shù)為零唯一最優(yōu)解無窮多最優(yōu)解無可行解對(duì)任一有

換基繼續(xù)YYYYNNN無界解N以后討論最優(yōu)解判斷小結(jié)所有基變量中有某非基變量唯一最優(yōu)解無3、基變換換入變量確定

對(duì)應(yīng)的為換入變量.(一般)注意：只要對(duì)應(yīng)的變量均可作為換入變量此時(shí)，目標(biāo)函數(shù)3、基變換換入變量確定注意：只要對(duì)應(yīng)

換出變量確定3、基變換Z

大大（在可行的范圍內(nèi)）則對(duì)應(yīng)的為換出變量.換出變量確定3、基變換Z大大（在可行的范圍內(nèi)）則對(duì)應(yīng)的4、迭代運(yùn)算

寫成增廣矩陣的形式,進(jìn)行迭代.4、迭代運(yùn)算寫成增廣矩陣的形式,進(jìn)行迭代.例：

4、迭代運(yùn)