單純形法原理講解ppt課件(PPT 29頁(yè))

1、 本節(jié)通過(guò)一個(gè)引例，可以了解利用單純形法求解線性規(guī)劃問(wèn)題的思路，并將每一次的結(jié)果與圖解法作一對(duì)比，其幾何意義更為清楚。第1頁(yè)，共29頁(yè)。引例（上一章例）第2頁(yè)，共29頁(yè)。求解線性規(guī)劃問(wèn)題的基本思路1、構(gòu)造初始可行基；2、求出一個(gè)基可行解（頂點(diǎn)）3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；4、基變化，轉(zhuǎn)2。要保證目標(biāo)函數(shù)值比 原來(lái)更優(yōu)。從線性規(guī)劃解的性質(zhì)可知求解線性規(guī)劃問(wèn)題的基本思路。第3頁(yè)，共29頁(yè)。第1步 確定初始基可行解 根據(jù)顯然 ， 可構(gòu)成初等可行基B 。 為基變量第4頁(yè)，共29頁(yè)。 第2步 求出基可行解 基變量用非基變量表示，并令非基變量為 0時(shí)對(duì)應(yīng)的解是否是最優(yōu)解？第5頁(yè)，共29頁(yè)。第3步 最優(yōu)

2、性檢驗(yàn)分析目標(biāo)函數(shù)檢驗(yàn)數(shù)0 時(shí)， 無(wú)解換基，繼續(xù)只要取 或 的 值可能增大。換入？基變量換出？基變量考慮將 或 換入為基變量第6頁(yè)，共29頁(yè)。第4步 基變換換入基變量：換入變量 （即選最大非負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量）一般選取 對(duì)應(yīng)的變量均可換入。第7頁(yè)，共29頁(yè)。換出變量使換入的變量越大越好同時(shí)，新的解要可行。選非負(fù) 的最小者對(duì)應(yīng)的變量換出為換入變量，應(yīng)換出 ？ 變量。思考：當(dāng) 時(shí)會(huì)怎樣？第8頁(yè)，共29頁(yè)。因此，基由 變?yōu)?轉(zhuǎn)第2步：基變量用非基變量表示。 第3步：最優(yōu)性判斷 檢驗(yàn)數(shù) 存在正，按第4步換基繼續(xù)迭代 均非正，停止 （這時(shí)的解即是最優(yōu)解）為換入變量，應(yīng)換出 變量。第9頁(yè)，共29頁(yè)。 轉(zhuǎn)

3、第2步第10頁(yè)，共29頁(yè)。 繼續(xù)迭代, 可得到:最優(yōu)值最優(yōu)解第11頁(yè)，共29頁(yè)。結(jié)合圖形法分析（單純形法的幾何意義）6 5 4 3 2 1 0 x2|123456789x1A(0,3)B(2,3)C(4,2)D(4,0)第12頁(yè)，共29頁(yè)。單純形法迭代原理從引例中了解了線性規(guī)劃的求解過(guò)程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單純形法迭代原理。第13頁(yè)，共29頁(yè)。觀察法:直接觀察得到初始可行基約束條件: 加入松弛變量即形成可行基。（下頁(yè)）約束條件: 加入非負(fù)人工變量, 以后討論. 1、初始基可行解的確定第14頁(yè)，共29頁(yè)。1、初始基可行解的確定 不妨設(shè) 為松弛變量，則約束方程組可表示為第

4、15頁(yè)，共29頁(yè)。 1、初始基可行解的確定第16頁(yè)，共29頁(yè)。2、最優(yōu)性檢驗(yàn)與解的判別第17頁(yè)，共29頁(yè)。 2、最優(yōu)性檢驗(yàn)與解的判別代入目標(biāo)函數(shù)有：第18頁(yè)，共29頁(yè)。 2、最優(yōu)性檢驗(yàn)與解的判別第19頁(yè)，共29頁(yè)。 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。（2）唯一最優(yōu)解判別定理：若所有 則存在唯一最優(yōu)解。 2、最優(yōu)性檢驗(yàn)與解的判別第20頁(yè)，共29頁(yè)。 （3）無(wú)窮多最優(yōu)解判定定理：若： 且存在某一個(gè)非基變量 則存在無(wú)窮多最優(yōu)解。（4）無(wú)界解判定定理：若有某一個(gè)非基 變量 并且對(duì)應(yīng)的非基變量的系數(shù) 則具有無(wú)界解。 2、最優(yōu)性檢驗(yàn)與解的判別第21頁(yè)，共29頁(yè)。 （4）之證明

5、：2、最優(yōu)性檢驗(yàn)與解的判別第22頁(yè)，共29頁(yè)。最優(yōu)解判斷小結(jié) （用非基變量的檢驗(yàn)數(shù)）所有 基變量中有非零人工變量某非基變量檢驗(yàn)數(shù)為零唯一最優(yōu)解無(wú)窮多最優(yōu)解無(wú)可行解對(duì)任一 有 換基繼續(xù)YYYYNNN無(wú)界解N以后討論第23頁(yè)，共29頁(yè)。3、基變換換入變量確定 對(duì)應(yīng)的 為換入變量. (一般)注意：只要 對(duì)應(yīng)的變量 均可作為換入變量此時(shí)，目標(biāo)函數(shù)第24頁(yè)，共29頁(yè)。 換出變量確定3、基變換Z 大大（在可行的范圍內(nèi)）則對(duì)應(yīng)的 為換出變量.第25頁(yè)，共29頁(yè)。4、迭代運(yùn)算 寫成增廣矩陣的形式,進(jìn)行迭代.第26頁(yè)，共29頁(yè)。例： 4、迭代運(yùn)算非基變量基變量001通過(guò)初等行變換化主列為主元第27頁(yè)，共29頁(yè)。 4、迭代運(yùn)算每次迭代的信