線性規(guī)劃-大M法、兩階段法與幾種特殊情況

1、1,1-4 線性規(guī)劃- 大M法、兩階段法及幾種特殊情況,School of Business ECUST,3.3 單純形法 3.3.1 單純形法的一般思路+例子 3.3.2 單純形表結(jié)構(gòu)+例子 3.3.3 單純形法的計(jì)算步驟 3.3.4 單純形法的矩陣描述 3.4 大M法 3.5 兩階段法 4 幾種特殊情況 4.1 無可行解 4.2 無界解 4.3 多重最優(yōu)解 4.4 進(jìn)基變量的相持 4.5 出基變量的相持,School of Business ECUST,3.4 大M法一般問題的初始基本可行解,School of Business ECUST,標(biāo)準(zhǔn)化,School of Business E

2、CUST,添加人工變量,School of Business ECUST,添加人工變量,School of Business ECUST,School of Business ECUST,解：首先將原LP問題轉(zhuǎn)化為標(biāo)準(zhǔn)型，引入非負(fù)變量x3，x4，x5,例：考慮下面的LP問題,School of Business ECUST,系數(shù)矩陣：,初始可行基？,大M法：構(gòu)造一個單位矩陣來作初始可行基,如何構(gòu)造？,通過添加人工變量,School of Business ECUST,添加人工變量x6, x7,School of Business ECUST,添加人工變量之后，系數(shù)矩陣變?yōu)椋?單位矩陣， 可作初

3、始可行基,變量x6, x7是為了構(gòu)造單位陣，而人為增加的，要保證最優(yōu)解 滿足原約束，在問題的最優(yōu)解中，這兩個變量必須取0值。 為了達(dá)到這種效果，我們將目標(biāo)函數(shù)改寫為：,其中，M為充分大的正數(shù),顯然，為了保證 Z取最大值，x6, x7 必然取0,School of Business ECUST,為什么可以這樣轉(zhuǎn)化？,= 0,= 0,原問題的最優(yōu)解,School of Business ECUST,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-,-1 1 0 -1 0 0 1,1,X2,2,1/2,2 0

4、 -1 1 0 1 -1,1,X6,-M,1/1,-1 1 0 -1 0 0 1,1,X7,-M,2/1,1 1 -1 0 0 1 0,2,X6,-M,0 0 1/2 3/2 0 -1/2-M -3/2-M,j,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,1+2M 0 -M 2+M 0 0 -2-2M,j,2/1,1 0 0 1 1 0 -1,2,X5,0,-1 2+2M -M -M 0 0 0,j,3/1,0 1 0 0 1 0 0,3,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,0 1 0 0 1 0 0,

5、3,X2,2,1 0 0 1 1 0 -1,2,X4,0,1 1 -1 0 0 1 0,2,X2,2,2 0 -1 1 0 1 -1,1,X4,0,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1/2/1/2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-1 0 0 0 -2 -M -M,j,-1 0 1 0 1 -1 0,1,X3,0,-3 0 2 0 0 -2-M -M,j,-1 0 1 0 1 -1 0,1,X5,0,0 0 1/2 3/2 0 -1/2-M -3/2-M,j,3/2 /1/2,0 0 1/2 1/2 1 -1/2 -1/2

6、,3/2,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,最優(yōu)解 最優(yōu)值,大M法的基本步驟,通過加入人工變量，構(gòu)造初始可行基； 在目標(biāo)函數(shù)中賦予人工變量很大的罰系數(shù)M，建立輔助線性規(guī)劃問題； 利用單純形法，求解上述輔助線性規(guī)劃問題，若： 有最優(yōu)解：如果最優(yōu)解的基變量中不含有非零人工變量，則最優(yōu)解中剔除掉人工變量部分，構(gòu)成原問題的最優(yōu)解；如果最優(yōu)解的基變量中仍含有非零人工變量，則原問題無可行解； 無界解：如果最終單純形表中基變量不含有非零人工變量，則原問題為無界解；否則，如果最終單純形表中基變量含有非零人工變量，則原問題為無可行解。,例：

7、求解下列線性規(guī)劃問題,引入人工變量， 并利用大M法求解,解： 首先將問題化為標(biāo)準(zhǔn)型,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,6/1 - 3/1,Z,-3+M -2+M -1-2M 0 -M -M 0 0,0 -M -2,x4 x7 x2,3 4 3,1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,3/1 4/1 -,Z,

8、Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3 -M -2,x1 x7 x2,3 1 3,1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,在以上最優(yōu)單純形表中，所有非基變量檢驗(yàn)數(shù)都小于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解。,例 求解下列線性規(guī)劃問題：,變標(biāo)準(zhǔn)型,添加人工變量 利用大M法,C,x1 x2 x3 x4 x5 x6,1 -1 0 0 -M -M,0.5 1 -1 0 1 0 4,1 1 0 -1 0 1 3,XB,x5 x6,CB

9、,-M -M,1+1.5M 2M-1 -M -M 0 0,b,4/1 3/1,-0.5 0 -1 1 1 -1 1,1 1 0 -1 0 1 3,x5 x2,-M -1,1/1 -,2-0.5M 0 -M -1+M 0 1-2M,-0.5 0 -1 1 1 -1 1,0.5 1 -1 0 1 0 4,x4 x2,0 -1,- 4/0.5,1.5 0 -1 0 1-M -M,-0.5 0 -1 1 1 -1,0.5 1 -1 0 1 0,x4 x2,0 -1,1 4,- 4/0.5,1.5 0 -1 0 1-M -M,C,x1 x2 x3 x4 x5 x6,1 -1 0 0 -M -M,XB,C

10、B,b,0 1 -2 1 2 -1 5,1 2 -2 0 2 0 8,x4 x1,0 1,0 -3 2 0 -M-2 -M,非基變量x3對應(yīng)的檢驗(yàn)數(shù)0, 并且該非基變量對應(yīng)的系數(shù)列向量的全部系數(shù)=0,輔助線性規(guī)劃問題 無界解,原問題 無界解,3.5 兩階段法,大M法實(shí)際上是利用單純形法直接求解原問題的輔助線性規(guī)劃問題，然后再根據(jù)最終能否將人工變量全部趕出基變量，來判斷原問題和輔助線性規(guī)劃問題之間解的對應(yīng)關(guān)系。 兩階段法則將原線性規(guī)劃問題的求解分為兩個階段： 第一階段，尋找原問題的初始基可行解或判斷原問題無可行解； 第二階段，尋找原問題最優(yōu)解或判斷原問題無界。,第一階段，尋找原問題的初始基可行解

11、或判斷原問題無可行解； 在原線性規(guī)劃問題中引入人工變量后，構(gòu)造一個新的線性規(guī)劃問題(輔助問題)，其中系數(shù)矩陣中包含單位陣，目標(biāo)函數(shù)是極小化人工變量之和(為了使人工變量取0值)； 用單純形方法求解輔助問題，若求得的基可行解可使目標(biāo)函數(shù)達(dá)到最小值0(人工變量均取0)，則我們就找到了原問題的初始基可行解； 若輔助問題的目標(biāo)函數(shù)不能達(dá)到最小值0，則原問題無可行解，求解過程結(jié)束。,第二階段，尋找原問題的最優(yōu)解或或判斷原問題無界。 在第一階段得到的最終單純形表基礎(chǔ)上，劃去人工變量所在的列，引入原問題的目標(biāo)函數(shù)，對原問題進(jìn)行求解。,School of Business ECUST,例：用兩階段法求解線性規(guī)劃

12、問題。 解：首先將問題化為標(biāo)準(zhǔn)型 添加人工變量x6,x7,構(gòu)造輔助線性規(guī)劃如下：,School of Business ECUST,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,0,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,0,-,-1 1 0 -1 0 0 1,1,X2,0,1/2,2 0 -1 1 0 1 -1,1,X6,-1,1/1,-1 1 0 -1 0 0 1,1,X7,-1,2/1,1 1 -1 0 0 1 0,2,X6,-1,0 0 0 0 0 -1 -1,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,2 0 -1 1 0

13、0 -2,2/1,1 0 0 1 1 0 -1,2,X5,0,0 2 -1 -1 0 0 0,3/1,0 1 0 0 1 0 0,3,X5,0,x1 x2 x3 x4 x5 x6 x7,b,XB,CB,0 0 0 0 0 -1 -1,C,輔助問題的最優(yōu)解：,School of Business ECUST,于是我們找到了原問題的一個基可行解,由上表可知，通過若干次初等行變換，原問題的約束方程組已變換成包含一個單位矩陣的約束方程組 該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解。,School of Business ECUST,-1 0 0

14、 0 -2,1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1,2 3 1,X4 X2 X3,0 2 0,-3 0 2 0 0,2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1,1 2 1,X4 X2 X5,0 2 0,0 0 1/2 3/2 0,1/2/1/2 - 3/2/1/2,1 0 -1/2 1/2 0 0 1 -1/2 -1/2 0 0 0 1/2 1/2 1,1/2 3/2 3/2,X1 X2 X5,-1 2 0,x1 x2 x3 x4 x5,b,XB,CB,-1 2 0 0 0,C,可得最優(yōu)解 ，目標(biāo)函數(shù)值maxZ=6， 與用大M法的結(jié)果完全相同。,4

15、單純形法計(jì)算中的幾個特殊情況,4.1 無可行解(可行域?yàn)榭占? 在用大M法計(jì)算過程中，判斷問題達(dá)到最優(yōu)解或無界解之后，在基變量中仍含有非零的人工變量； 在用兩階段法計(jì)算過程中，第一階段的輔助問題無法使目標(biāo)函數(shù)值達(dá)到零，即基變量中存在非零的人工變量。 4.2 無界解 存在某個非基變量的檢驗(yàn)數(shù)大于零，而該非基變量的系數(shù)矩陣列的所有元素均小于等于零。,4.3 多重最優(yōu)解 所有非基變量的檢驗(yàn)數(shù)均小于等于零，并且至少存在一個非基變量的檢驗(yàn)數(shù)等于零。 4.4 進(jìn)基變量的相持 4.5 出基變量的相持,School of Business ECUST,4.1無可行解,School of Business EC

16、UST,當(dāng)前基本可行解：(0, 0, 0, 3, 4) , Z=-4M,School of Business ECUST,當(dāng)前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,School of Business ECUST,無可行解的判別準(zhǔn)則,最優(yōu)解時，人工變量仍為基變量， 且人工變量不為,School of Business ECUST,4.2 無界解,School of Business ECUST,當(dāng)前基本可行解：(0, 0, 0, 0, 4, 3) , Z=-7M,School of Business ECUST,當(dāng)前基本可行解：(0, 3, 0, 0, 1) , Z=-

17、M-3,School of Business ECUST,當(dāng)前基本可行解：(0, 4, 0, 1, 0) , Z= -4,School of Business ECUST,當(dāng)前基本可行解：(8, 0, 0, 5, 0) , Z= 8,School of Business ECUST,無界解的判別準(zhǔn)則,存在非基變量，檢驗(yàn)數(shù)0，技術(shù)系數(shù)均 0,School of Business ECUST,4.3 無窮多（多重）最優(yōu)解,School of Business ECUST,當(dāng)前基本可行解：(0, 0, 150, 20, 300) , Z=0,School of Business ECUST,當(dāng)前基本

18、可行解：(75/2, 0, 75/2, 20, 0) , Z=300,School of Business ECUST,當(dāng)前基本可行解：(30, 12, 0, 8, 0) , Z=300,School of Business ECUST,無窮多最優(yōu)解的判別準(zhǔn)則,所有檢驗(yàn)數(shù) 存在非基變量，檢驗(yàn)數(shù)=0,School of Business ECUST,解的判別： 若 是對應(yīng)于基Bk = (P1,P2, ., Pm)的基可行解，對于一切 j = m+1,.,n, 均有檢驗(yàn)數(shù) ，則 為最優(yōu)解； 若 是對應(yīng)于基 Bk = (P1,P2, ., Pm)的基可行解，對于一切 j = m+1,.,n, 均有檢驗(yàn)數(shù) ，并且存在某個非基變量(比如xm+r)的檢驗(yàn)數(shù) ，則該線性規(guī)劃問題有無窮多最優(yōu)解； 若 是對應(yīng)于基 Bk = (P1,P2, ., Pm)的基可行解，若存在某個非基變量(比如xm+r)的檢驗(yàn)數(shù) ，并且對i=1,2,m, 均有 ，則該線性規(guī)劃問題有無界解(無最優(yōu)解)。,School of Business ECUST,利用大M法，求解輔助線性規(guī)劃問題，若： 有最優(yōu)解：如果最優(yōu)解的基變量中不含有非零人工變量，則最優(yōu)解中剔除掉人工變量部分，構(gòu)成原問題的最優(yōu)解； 如果最優(yōu)解的基變量中仍含有非零人工變量，則