運(yùn)籌學(xué)第一章 1.4 大M法和兩階段法

四、單純形法的一般描述：

1、初始可行解的確定

(1)初始可行基的確定觀察法—系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類型的約束將新增的松弛變量作為初始基變量，對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣；1可編輯ppt

先將約束條件標(biāo)準(zhǔn)化，再引入非負(fù)的人工變量，以人工變量作為初始基變量，其對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣，稱為“人造基”；然后用大M法或兩階段法求解；

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——2可編輯ppt等式約束左端引入人工變量的目的使約束方程的系數(shù)矩陣中出現(xiàn)一個(gè)單位陣，用單位陣的每一個(gè)列向量對(duì)應(yīng)的決策變量作為“基變量”，這樣，出現(xiàn)在單純形表格中的B(i)列（即約束方程的右邊常數(shù)）值正好就是基變量的取值。(注意:用非基變量表示基變量的表達(dá)式)3可編輯ppt①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎麼辦？構(gòu)造“不完全的人造基”！

討論②為什麼初始可行基一定要選單位陣？b列正好就是基變量的取值，檢驗(yàn)數(shù)行和b列交叉處元素也正好對(duì)應(yīng)目標(biāo)函數(shù)值，

因此稱b列為解答列4可編輯ppt（2）寫出初始基本可行解——根據(jù)“用非基變量表示基變量的表達(dá)式”，非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解。

2、建立判別準(zhǔn)則：（1）兩個(gè)基本表達(dá)式的一般形式LP限制條件中全部是“≤”類型約束，新增的松弛變量作為初始基變量的情況來描述：5可編輯ppt此時(shí)LP的標(biāo)準(zhǔn)型為非基變量 基變量6可編輯ppt初始可行基：初始基本可行解：

7可編輯ppt一般（經(jīng)過若干次迭代），對(duì)于基B，用非基變量表出基變量的表達(dá)式為：用非基變量表示目標(biāo)函數(shù)的表達(dá)式：

8可編輯ppt若是對(duì)應(yīng)于基B的基本可行解，是非基變量的檢驗(yàn)數(shù)，若對(duì)于一切非基變量的角指標(biāo)j，均有≤0，則X(0)為最優(yōu)解。（2）最優(yōu)性判別定理（3）無“有限最優(yōu)解”的判別定理

若為一基本可行解，有一非基變量xk,其檢驗(yàn)數(shù),而對(duì)于i=1,2,…，m，均有，則該線性規(guī)劃問題沒有“有限最優(yōu)解”。9可編輯ppt舉例：用非基變量表示基變量的表達(dá)式代表兩個(gè)約束條件：x2對(duì)應(yīng)的系數(shù)列向量P2=（1，3）T，設(shè)：當(dāng)前的換入變量是X2，按最小比值原則確定換出變量：10可編輯ppt要求：

于是：如果x2的系數(shù)列變成P2’=（-1，0）T,則用非基變量表示基變量的表達(dá)式就變成；可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大→原線性規(guī)劃無“有限最優(yōu)解”。11可編輯ppt

3、進(jìn)行基變換（1）選擇進(jìn)基變量——原則：正檢驗(yàn)數(shù)（或最大正檢驗(yàn)數(shù)）所對(duì)應(yīng)的變量進(jìn)基，目的是使目標(biāo)函數(shù)得到改善（較快增大）；進(jìn)基變量對(duì)應(yīng)的系數(shù)列稱為主元列。（2）出基變量的確定——按最小比值原則確定出基變量，為的是保持解的可行性；出基變量所在的行稱為主元行。主元行和主元列的交叉元素稱為主元素。12可編輯ppt

4、主元變換（旋轉(zhuǎn)運(yùn)算或樞運(yùn)算）按照主元素進(jìn)行矩陣的初等行變換——把主元素變成1，主元列的其他元素變成0（即主元列變?yōu)閱挝幌蛄浚懗鲂碌幕究尚薪?，返回最?yōu)性檢驗(yàn)。例1.8的表格單純形法計(jì)算過程：

13可編輯ppt表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理。引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個(gè)單位陣。

（這一步計(jì)算機(jī)可自動(dòng)完成）

確定初始可行基，寫出初始基本可行解14可編輯ppt第二步：最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，檢查：所有檢驗(yàn)數(shù)是否≤0？

是——結(jié)束，寫出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值；還有正檢驗(yàn)數(shù)——檢查相應(yīng)系數(shù)列≤0？是——結(jié)束，該LP無“有限最優(yōu)解”！不屬于上述兩種情況，轉(zhuǎn)入下一步—基變換。

確定是停止迭代還是轉(zhuǎn)入基變換？15可編輯ppt

選擇（最大）正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列，主元列對(duì)應(yīng)的非基變量為換入變量；最小比值對(duì)應(yīng)的行為主元行，主元行對(duì)應(yīng)的基變量為換出變量。第三步：基變換確定進(jìn)基變量和出基變量。16可編輯ppt利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成0，從而得到一張新的單純形表，返回第二步。第四步換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值17可編輯ppt該迭代過程直至下列情況之一發(fā)生時(shí)停止

檢驗(yàn)數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤0（最優(yōu)解無界）停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）依據(jù)：最優(yōu)性檢驗(yàn)的兩個(gè)定理最優(yōu)性判別定理；無“有限最優(yōu)解”判斷定理18可編輯ppt五、各種類型線性規(guī)劃的處理1、分類及處理原則：（1）類型一：目標(biāo)要求是“Max”，約束條件是“≤”類型——左邊加上非負(fù)松弛變量變成等式約束（約束條件標(biāo)準(zhǔn)化），將引入的松弛變量作為初始基變量，則初始可行基是一個(gè)單位陣，用原始單純形法求解。19可編輯ppt（2）類型二：目標(biāo)要求是“Max”，約束條件是“=”類型——左邊引入非負(fù)的人工變量，并將引入的人工變量作為初始基變量，則初始可行基是一個(gè)單位陣，然后用大M法或兩階段法求解。（3）類型三：目標(biāo)要求是“Max”，約束條件是“≥”類型——約束條件標(biāo)準(zhǔn)化，左邊減去非負(fù)的剩余變量，變成等式約束，化為類型二。20可編輯ppt2、處理人工變量的方法：（1）大M法——在約束條件中人為地加入非負(fù)的人工變量，以便使它們對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣。問題：加入的人工變量是否合理？如何處理？在目標(biāo)函數(shù)中，給人工變量前面添上一個(gè)絕對(duì)值很大的負(fù)系數(shù)-M（M>>0），迭代過程中，只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化——懲罰！21可編輯ppt①最優(yōu)表中，基變量不包含人工變量，則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解，不影響目標(biāo)函數(shù)的取值；②最優(yōu)表中，基變量中仍含有人工變量，表明原線性規(guī)劃的約束條件被破壞，線性規(guī)劃沒有可行解，也就沒有最優(yōu)解！結(jié)果問題結(jié)果②中求得的最優(yōu)解是哪個(gè)線性規(guī)劃的最優(yōu)解？為什麼？22可編輯ppt大M法舉例加入松弛變量、剩余變量和人工變量：23可編輯ppt六、迭代過程中可能出現(xiàn)的問題及處理方法1、為確定出基變量要計(jì)算比值，該比值=解答列元素/主元列元素。對(duì)于主元列的0元素或負(fù)元素是否也要計(jì)算比值？（此時(shí)解的可行性自然滿足，不必計(jì)算；如果主元列元素全部為0元素或負(fù)元素，則最小比值失效，線性規(guī)劃無“有限最優(yōu)解”）24可編輯ppt2、出現(xiàn)若干個(gè)相同的最小比值怎麼辦？（說明出現(xiàn)了退化的基本可行解，即非0分量的個(gè)數(shù)小于約束方程的個(gè)數(shù)。按照“攝動(dòng)原理”所得的規(guī)則，從相同比值對(duì)應(yīng)的基變量中選下標(biāo)最大的基變量作為換出變量可以避免出現(xiàn)“死循環(huán)”現(xiàn)象）3、選擇進(jìn)基變量時(shí)，同時(shí)有若干個(gè)正檢驗(yàn)數(shù)，怎麼選？（最大正檢驗(yàn)數(shù)或從左至右第1個(gè)出現(xiàn)的正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量進(jìn)基）25可編輯ppt（2）兩階段法

第一階段：建立輔助線性規(guī)劃并求解，以判斷原線性規(guī)劃是否存在基本可行解。輔助線性規(guī)劃的結(jié)構(gòu)：目標(biāo)函數(shù)W為所有人工變量之和，目標(biāo)要求是使目標(biāo)函數(shù)極小化，約束條件與原線性規(guī)劃相同。

26可編輯ppt

求解結(jié)果①W最優(yōu)值=0——即所有人工變量取值全為0（為什麼？），均為非基變量，最優(yōu)解是原線性規(guī)劃的一個(gè)基本可行解，轉(zhuǎn)入第二階段；②W最優(yōu)值=0——但人工變量中有等于0的基變量，構(gòu)成退化的基本可行解，可以轉(zhuǎn)化為情況①；如何轉(zhuǎn)化？

選一個(gè)不是人工變量的非基變量進(jìn)基，把在基中的人工變量替換出來27可編輯ppt③W最優(yōu)值>0——至少有一個(gè)人工變量取值>0,說明基變量中至少有1個(gè)人工變量,表明原問題沒有可行解,討論結(jié)束。（1）+++=+++…..21tsxxxMinZmnnn………----=+++