運(yùn)籌學(xué)課件1-6大M兩階段

1、單純形表復(fù)習(xí)小結(jié) 求解思想 頂點(diǎn)的逐步轉(zhuǎn)移， 條件是 使目標(biāo)函數(shù)值不斷得到改善。1表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理。 引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個(gè)單位陣。 確定初始可行基，寫出初始基本可行解2第二步：最優(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的解無界！不屬于上述兩種情況，轉(zhuǎn)入下一步基變換。 確定是停止迭代還是轉(zhuǎn)入基變換？3 選擇（最大）正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列，主元列對(duì)應(yīng)的非基變量為換入變量； 最小比值對(duì)應(yīng)的行為主

2、元行，主元行對(duì)應(yīng)的基變量為換出變量。第三步：基變換確定進(jìn)基變量和出基變量。4 利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，從而得到一張新的單純形表，返回第二步。第四步 換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值5該迭代過程直至下列情況之一發(fā)生時(shí)停止 檢驗(yàn)數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列 0 （最優(yōu)解無界） 停止迭代的標(biāo)志（停機(jī)準(zhǔn)則） 6標(biāo)準(zhǔn)型的單純型算法 (1)變換主行(2)變換主列 除主元保留為1，其余都置0(3)變換非主行、主列元素 aij (包括 bi) 四角算法公式：7 標(biāo)準(zhǔn)型的單純型算法5、迭代過程(4)變換CB，XB(5)計(jì)

3、算目標(biāo)函數(shù)、機(jī)會(huì)成本 zj 和檢驗(yàn)數(shù) cj zj 6、返回步驟 28單純形法的進(jìn)一步討論一、大M法二、兩階段法-人工變量法人工變量法問題：線性規(guī)劃問題化為標(biāo)準(zhǔn)形時(shí)，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？ 人工變量法加入人工變量設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)型為： 加入人工變量,構(gòu)造初始可行基. 人工變量法系數(shù)矩陣為單位矩陣，可構(gòu)成初始可行基。 約束條件已改變，目標(biāo)函數(shù)如何調(diào)整？人工變量法“懲罰” 人工變量?。?）大M法（2）兩階段法思路因?yàn)槿斯ぷ兞?是為了構(gòu)造初始基本可行解，人為加入原約束方程中的虛擬變量，只有當(dāng)它們同時(shí)等于零，加入人工變量的等式約束才與原約束條件相等。也就是說，若經(jīng)

4、過基變換，基變量中不再含有非零人工變量，這表示原問題有解；若經(jīng)過基變換，最終單純形表中還存在非零人工變量，這表示原問題無可行解。一、大 M 法人工變量在目標(biāo)函數(shù)中的系數(shù)為 -M, 其中，M 為任意大的正數(shù)。目標(biāo)函數(shù)中添加“罰因子”M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)。例: 求解線性規(guī)劃問題一、大 M 法 一、大 M 法解:加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn) 化, 加入人工變量構(gòu)造初始可行基. 求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。一、大 M 法用單純形法求解（見下頁(yè)）。目標(biāo)函數(shù)中添加“罰因子”M為人工變量系數(shù)，只

5、要人工變量0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)。 1 -2 1 -4 1 2 -2 0 1 3-6M M -1 3M-1 3 -1 -1 x1 x2 x3 0 x4 11 -M x6 3 -M x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 11 3/2 1 0 0 1 0 0 1 0 0 - M - M x6 x7 表1（初始單純形表）一、大 M 法（單純形法求解） 3 -2 0 0 1 0 -2 0 1 1 M-1 0 3 -1 -1x1 x2 x3 0 x4 10 -M x6 1 -1 x3 1C j - Z j C j CB XB b

6、 1 0 0 -1 0 0 0 -M 0 0 x4 x5 1 0 -1 1 -2 0 1 0 1-3M - M - M x6 x7 一、大 M 法（單純形法求解）表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x1 x2 x3 0 x4 12 -1 x2 1 -1 x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x4 x5 4 i 2 -5 1 -2 0 1 1-M -1 -M - M - M x6 x7 表3一、大 M 法（單純形法求解） 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x1 x2 x3

7、 3 x1 4 -1 x2 1 -1 x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x4 x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-M 2/3-M - M - M x6 x7 表4一、大 M 法（單純形法求解）最優(yōu)解為目標(biāo)函數(shù)值 z=2檢驗(yàn)數(shù)均非正，此為最終單純形表 最優(yōu)表中，基變量不包含人工變量，則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解，不影響目標(biāo)函數(shù)的取值； 最優(yōu)表中，基變量中仍含有人工變量，表明原線性規(guī)劃的約束條件被破壞，線性規(guī)劃沒有可行解，也就沒有最優(yōu)解！ 結(jié) 果24M在計(jì)算機(jī)上處理困難。分階段處理先求初始基，再求

8、解。二、兩階段法二、兩階段法第一階段: 構(gòu)造如下的線性規(guī)劃問題人工變量的系數(shù)矩陣為單位矩陣，可構(gòu)成初始可行基。 目標(biāo)函數(shù)僅含人工變量，并要求實(shí)現(xiàn)最小化。 若其最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問題無可行解。 用單純形法求解上述問題,若=0,進(jìn)入第二階段,否則,原問題無可行解。第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。 用單純形法求解即可。二、兩階段法下面舉例說明，仍用大M法的例。例：二、兩階段法 二、兩階段法構(gòu)造第一階段問題并求解解：用單純形法求解僅含人工變量極小化：最優(yōu)解？二、兩階段法（第一階段、求min ） 1 -2 1 -4

9、1 2 -2 0 1 -6 1 3 0 0 0 x1 x2 x3 0 x4 11 -1 x6 3 -1 x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x4 x5 x6 0 11 0 3/2 1 1 0 - 1 x7 i 表1 -1 - -2 1 1 - -3 - 1 x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x1 x2 x3 0 x4 10 -1 x6 1 0 x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x4 x5 x6二、兩階段法（第一階段、求mi

10、n ）表2 -5 4 -2 - 1 - -1 - 1 x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x1 x2 x3 0 x4 12 0 x2 1 0 x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x4 x5 x6二、兩階段法（第一階段、求min ）表3：最終單純形表第二階段不含人工變量且=0二、兩階段法第二階段 將去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。 3 0 0 0 1 0 -2 0 1 3 -1 -1 x1 x2 x3 0 x4 12 -1 x2 1 -1 x3 1 C i CB XB b 1 -2

11、 0 -1 0 0 0 0 x4 x5 1 0 0 0 -14二、兩階段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x4 x5 第二階段 0 0 0 -1/3 -1/3最優(yōu)解為目標(biāo)函數(shù)值 z=2二階段法的求解過程第一階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個(gè)沒有人工變量的基礎(chǔ)可行解第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解若第一階段結(jié)束時(shí)，人工變量仍在基變量中，則原問題無解為了簡(jiǎn)化計(jì)算，在第一階段重新定義價(jià)值系數(shù)如下

12、：幾種特殊情況-無可行解 maxz=x1-x2s.t.0.5x1+x24(1)x1+x23(2)x1,x2036當(dāng)前基本可行解：(0, 0, 0, 3, 4) , Z=-4M 37當(dāng)前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3 38無可行解的判別準(zhǔn)則最優(yōu)解時(shí)，人工變量仍為基變量39可行域無界 maxz=x1-x2s.t.0.5x1+x24(1)x1+x23(2)x1,x2040當(dāng)前基本可行解：(0, 0, 0, 0, 4, 3) , Z=-7M 41當(dāng)前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3 42當(dāng)前基本可行解：(0, 4, 0, 1, 0) , Z=

13、-443當(dāng)前基本可行解：(8, 0, 0, 5, 0) , Z= 844可行域無界的判別準(zhǔn)則 存在非基變量，檢驗(yàn)數(shù)0，技術(shù)系數(shù)均045無窮多最優(yōu)解 maxz=8x1+5x2s.t.3x1+5x2150(1)x2 20(2)8x1+5x2300(3)x1,x2 046當(dāng)前基本可行解：(0, 0, 150, 20, 300) , Z=0 847當(dāng)前基本可行解：(75/2, 0, 75/2, 20, 0) , Z=300 48當(dāng)前基本可行解：(30, 12, 0, 8, 0) , Z=30049無窮多解的判別準(zhǔn)則存在非基變量，檢驗(yàn)數(shù)=050單純形法計(jì)算中的幾個(gè)問題1、目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判斷 只需用檢驗(yàn)數(shù) 作為最優(yōu)性的標(biāo)志。2、無可行解的判斷 當(dāng)求解結(jié)果出現(xiàn)所有 時(shí)，如基變量仍 含有非零的人工變量（兩階段法求解時(shí)第