單純形法原理講解

1、單純形法原理講解第1頁，共28頁，2022年，5月20日，3點18分，星期二引例（上一章例）第2頁，共28頁，2022年，5月20日，3點18分，星期二求解線性規(guī)劃問題的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優(yōu)性檢驗：判斷是否最優(yōu)解；4、基變化，轉2。要保證目標函數(shù)值比 原來更優(yōu)。從線性規(guī)劃解的性質可知求解線性規(guī)劃問題的基本思路。第3頁，共28頁，2022年，5月20日，3點18分，星期二第1步 確定初始基可行解 根據(jù)顯然 ， 可構成初等可行基B 。 為基變量第4頁，共28頁，2022年，5月20日，3點18分，星期二 第2步 求出基可行解 基變量用非基變量表示，并令非

2、基變量為 0時對應的解是否是最優(yōu)解？第5頁，共28頁，2022年，5月20日，3點18分，星期二第3步 最優(yōu)性檢驗分析目標函數(shù)檢驗數(shù)0 時， 無解換基，繼續(xù)只要取 或 的 值可能增大。換入？基變量換出？基變量考慮將 或 換入為基變量第6頁，共28頁，2022年，5月20日，3點18分，星期二第4步 基變換換入基變量：換入變量 （即選最大非負檢驗數(shù)對應的變量）一般選取 對應的變量均可換入。第7頁，共28頁，2022年，5月20日，3點18分，星期二換出變量使換入的變量越大越好同時，新的解要可行。選非負 的最小者對應的變量換出為換入變量，應換出 ？ 變量。思考：當 時會怎樣？第8頁，共28頁，20

3、22年，5月20日，3點18分，星期二因此，基由 變?yōu)?轉第2步：基變量用非基變量表示。 第3步：最優(yōu)性判斷 檢驗數(shù) 存在正，按第4步換基繼續(xù)迭代 均非正，停止 （這時的解即是最優(yōu)解）為換入變量，應換出 變量。第9頁，共28頁，2022年，5月20日，3點18分，星期二 轉 第2步第10頁，共28頁，2022年，5月20日，3點18分，星期二 繼續(xù)迭代, 可得到:最優(yōu)值最優(yōu)解第11頁，共28頁，2022年，5月20日，3點18分，星期二結合圖形法分析（單純形法的幾何意義）6 5 4 3 2 1 0 x2|123456789x1A(0,3)B(2,3)C(4,2)D(4,0)第12頁，共28頁，

4、2022年，5月20日，3點18分，星期二單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單純形法迭代原理。第13頁，共28頁，2022年，5月20日，3點18分，星期二觀察法:直接觀察得到初始可行基約束條件: 加入松弛變量即形成可行基。（下頁）約束條件: 加入非負人工變量, 以后討論. 1、初始基可行解的確定第14頁，共28頁，2022年，5月20日，3點18分，星期二1、初始基可行解的確定 不妨設 為松弛變量，則約束方程組可表示為第15頁，共28頁，2022年，5月20日，3點18分，星期二 1、初始基可行解的確定第16頁，共28頁，2022年

5、，5月20日，3點18分，星期二2、最優(yōu)性檢驗與解的判別第17頁，共28頁，2022年，5月20日，3點18分，星期二 2、最優(yōu)性檢驗與解的判別代入目標函數(shù)有：第18頁，共28頁，2022年，5月20日，3點18分，星期二 2、最優(yōu)性檢驗與解的判別第19頁，共28頁，2022年，5月20日，3點18分，星期二 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。（2）唯一最優(yōu)解判別定理：若所有 則存在唯一最優(yōu)解。 2、最優(yōu)性檢驗與解的判別第20頁，共28頁，2022年，5月20日，3點18分，星期二 （3）無窮多最優(yōu)解判定定理：若： 且存在某一個非基變量 則存在無窮多最優(yōu)解。（4）

6、無界解判定定理：若有某一個非基 變量 并且對應的非基變量的系數(shù) 則具有無界解。 2、最優(yōu)性檢驗與解的判別第21頁，共28頁，2022年，5月20日，3點18分，星期二 （4）之證明：2、最優(yōu)性檢驗與解的判別第22頁，共28頁，2022年，5月20日，3點18分，星期二最優(yōu)解判斷小結 （用非基變量的檢驗數(shù)）所有 基變量中有非零人工變量某非基變量檢驗數(shù)為零唯一最優(yōu)解無窮多最優(yōu)解無可行解對任一 有 換基繼續(xù)YYYYNNN無界解N以后討論第23頁，共28頁，2022年，5月20日，3點18分，星期二3、基變換換入變量確定 對應的 為換入變量. (一般)注意：只要 對應的變量 均可作為換入變量此時，目標函數(shù)第24頁，共28頁，2022年，5月20日，3點18分，星期二 換出變量確定3、基變換Z 大大（在可行的范圍內）則對應的 為換出變量.第25頁，共28頁，2022年，5月20日，3點18分，星期二4、迭代運算 寫成增廣矩陣的形式,進行迭代.第26頁，共28頁，2022年，5月20日，3點18分，星期二例： 4、迭代運算非基變量基變量001通過