物流優(yōu)化技術(shù)課件大M法和兩階段法

物流優(yōu)化技術(shù)課件大M法和兩階段法第1頁，共31頁，2023年，2月20日，星期日

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

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——第2頁，共31頁，2023年，2月20日，星期日等式約束左端引入人工變量的目的

使約束方程的系數(shù)矩陣中出現(xiàn)一個單位陣，用單位陣的每一個列向量對應(yīng)的決策變量作為“基變量”，這樣，出現(xiàn)在單純形表格中的B(i)列（即約束方程的右邊常數(shù)）值正好就是基變量的取值。

(注意:用非基變量表示基變量的表達式)第3頁，共31頁，2023年，2月20日，星期日①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎麼辦？構(gòu)造“不完全的人造基”！

討論②為什麼初始可行基一定要選單位陣？

b列正好就是基變量的取值，檢驗數(shù)行和b列交叉處元素也正好對應(yīng)目標(biāo)函數(shù)值，

因此稱b列為解答列第4頁，共31頁，2023年，2月20日，星期日（2）寫出初始基本可行解——

根據(jù)“用非基變量表示基變量的表達式”，非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解。

2、建立判別準(zhǔn)則：（1）兩個基本表達式的一般形式

LP限制條件中全部是“≤”類型約束，新增的松弛變量作為初始基變量的情況來描述：第5頁，共31頁，2023年，2月20日，星期日此時LP的標(biāo)準(zhǔn)型為非基變量 基變量第6頁，共31頁，2023年，2月20日，星期日初始可行基：初始基本可行解：

第7頁，共31頁，2023年，2月20日，星期日

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

第8頁，共31頁，2023年，2月20日，星期日

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

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

于是：

如果x2的系數(shù)列變成P2’=（-1，0）T,則用非基變量表示基變量的表達式就變成；可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大→原線性規(guī)劃無“有限最優(yōu)解”。第11頁，共31頁，2023年，2月20日，星期日

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

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

例1.8的表格單純形法計算過程：

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

（這一步計算機可自動完成）

確定初始可行基，寫出初始基本可行解第14頁，共31頁，2023年，2月20日，星期日第二步：最優(yōu)性檢驗計算檢驗數(shù)，檢查：所有檢驗數(shù)是否≤0？

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

確定是停止迭代還是轉(zhuǎn)入基變換？第15頁，共31頁，2023年，2月20日，星期日

選擇（最大）正檢驗數(shù)對應(yīng)的系數(shù)列為主元列，主元列對應(yīng)的非基變量為換入變量；最小比值對應(yīng)的行為主元行，主元行對應(yīng)的基變量為換出變量。第三步：基變換確定進基變量和出基變量。第16頁，共31頁，2023年，2月20日，星期日

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進基變量對應(yīng)的檢驗數(shù)變成0，從而得到一張新的單純形表，返回第二步。第四步換基迭代（旋轉(zhuǎn)運算、樞運算)

完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值第17頁，共31頁，2023年，2月20日，星期日該迭代過程直至下列情況之一發(fā)生時停止檢驗數(shù)行全部變?yōu)榉钦担唬ǖ玫阶顑?yōu)解）或主元列≤0（最優(yōu)解無界）

停止迭代的標(biāo)志（停機準(zhǔn)則）

依據(jù)：最優(yōu)性檢驗的兩個定理最優(yōu)性判別定理；無“有限最優(yōu)解”判斷定理第18頁，共31頁，2023年，2月20日，星期日五、各種類型線性規(guī)劃的處理1、分類及處理原則：（1）類型一：目標(biāo)要求是“Max”，約束條件是“≤”類型——左邊加上非負(fù)松弛變量變成等式約束（約束條件標(biāo)準(zhǔn)化），將引入的松弛變量作為初始基變量，則初始可行基是一個單位陣，用原始單純形法求解。第19頁，共31頁，2023年，2月20日，星期日（2）類型二：目標(biāo)要求是“Max”，約束條件是“=”類型——左邊引入非負(fù)的人工變量，并將引入的人工變量作為初始基變量，則初始可行基是一個單位陣，然后用大M法或兩階段法求解。（3）類型三：目標(biāo)要求是“Max”，約束條件是“≥”類型——約束條件標(biāo)準(zhǔn)化，左邊減去非負(fù)的剩余變量，變成等式約束，化為類型二。第20頁，共31頁，2023年，2月20日，星期日2、處理人工變量的方法：（1）大M法——在約束條件中人為地加入非負(fù)的人工變量，以便使它們對應(yīng)的系數(shù)列向量構(gòu)成單位陣。問題：加入的人工變量是否合理？如何處理？在目標(biāo)函數(shù)中，給人工變量前面添上一個絕對值很大的負(fù)系數(shù)-M（M>>0），迭代過程中，只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實現(xiàn)極大化——懲罰！第21頁，共31頁，2023年，2月20日，星期日①最優(yōu)表中，基變量不包含人工變量，則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解，不影響目標(biāo)函數(shù)的取值；②最優(yōu)表中，基變量中仍含有人工變量，表明原線性規(guī)劃的約束條件被破壞，線性規(guī)劃沒有可行解，也就沒有最優(yōu)解！

結(jié)果問題結(jié)果②中求得的最優(yōu)解是哪個線性規(guī)劃的最優(yōu)解？為什麼？第22頁，共31頁，2023年，2月20日，星期日大M法舉例加入松弛變量、剩余變量和人工變量：第23頁，共31頁，2023年，2月20日，星期日六、迭代過程中可能出現(xiàn)的問題及處理方法1、為確定出基變量要計算比值，該比值=解答列元素/主元列元素。對于主元列的0元素或負(fù)元素是否也要計算比值？（此時解的可行性自然滿足，不必計算；如果主元列元素全部為0元素或負(fù)元素，則最小比值失效，線性規(guī)劃無“有限最優(yōu)解”）第24頁，共31頁，2023年，2月20日，星期日2、出現(xiàn)若干個相同的最小比值怎麼辦？（說明出現(xiàn)了退化的基本可行解，即非0分量的個數(shù)小于約束方程的個數(shù)。按照“攝動原理”所得的規(guī)則，從相同比值對應(yīng)的基變量中選下標(biāo)最大的基變量作為換出變量可以避免出現(xiàn)“死循環(huán)”現(xiàn)象）3、選擇進基變量時，同時有若干個正檢驗數(shù)，怎麼選？（最大正檢驗數(shù)或從左至右第1個出現(xiàn)的正檢驗數(shù)所對應(yīng)的非基變量進基）第25頁，共31頁，2023年，2月20日，星期日（2）

兩階段法

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

第26頁，共31頁，2023年，2月20日，星期日

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

選一個不是人工變量的非基變量進基，把在基中的人工變量替換出來第27頁，共31頁，2023年，2月20日，星期日③W最優(yōu)值>0——至少有一個人工變量取值>0,說明基變量中至少有1個人工變量,表明原問題沒有可行解,討論結(jié)束。（1）+++=+++…..21tsxxxMinZmnnn………----=+++.21tsxxxMaxZmnnn（2）…………試比較第28