第三講線性規(guī)劃的二階段法

1、第一章 線性規(guī)劃及其擴(kuò)展,第5節(jié) 單純形法的進(jìn)一步討論,線性規(guī)劃的人工變量法,目前有兩種方法：大M法和二階段法。,人工變量法,在討論單純形法時(shí)，我們總是假定AXb的系數(shù)矩陣A的秩r(A)=mn,或者已有一個(gè)可行基。但是，在許多問題中，初始可行基是不容易找到的，或者A不滿秩。這樣單純形法就很難進(jìn)行。,所以，我們要探討如何尋找第一個(gè)可行基？,大M法（1）,把原問題化為下列形式：其中M是任意大的正數(shù),大M法（2）,關(guān)于大M法的幾點(diǎn)注釋：,(1)在引入人工變量之前，約束條件已是等式，為了這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零；為此在目標(biāo)函數(shù)中人工變量的取值為充分小的負(fù)數(shù)，用“-M”代表；

2、,(2)若在單純形表中有j0，且存在非零人工變量，則原問題無可行解；若基變量中不再含有非零的人工變量，這表示原問題有解；,(3)引入的人工變量個(gè)數(shù)越少越好，只要出現(xiàn)單位矩陣作為基陣即可。,大M法舉例（1）,例,解：將原問題化為標(biāo)準(zhǔn)形為：,大M法舉例（2）,引入的人工變量個(gè)數(shù)越少越好,引入人工變量y2,y30,由大M法得輔助問題為：,其中大M為任意大的正數(shù),得上述輔助問題的單純形初表為：,大M法舉例（3）,T(B1),XB,b,x1 x2 x3 x4 x5 y2 y3,x4 y2 y3,41 9,-z,10M,1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0

3、1,-2M-3 4M 1 0 -M 0 0,T(B2),x4,x2,y3,-z,3,3 0 2 1 1 -1 0,1,-2 1 -1 0 -1 1 0,6,6 0 4 0 3 -3 1,6M,6M-3,0,4M+1,0,3M,-4M,0,人工變量優(yōu)先出基,大M法舉例（4）,T(B3),XB,b,x1 x2 x3 x4 x5 y2 y3,x4 x2 x1,03 1,-z,3,0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6,0 0 3 0 3/2 -M-3/2 -M+1/2,T(B4),x4,x2,x3,-z,0,0 0

4、 0 1 -1/2 1/2 -1/2,5/2,-1/2 1 0 0 -1/4 1/4 1/4,3/2,3/2 0 1 0 3/4 -3/4 1/4,-3/2,-9/2,0,0,0,-3/4,-M+3/4,-M-1/4,大M法舉例（5）,原線性規(guī)劃問題的最優(yōu)解為,因?yàn)樵趩渭冃伪鞹(B4)中，非基變量檢驗(yàn)數(shù)均小于等于零，且人工變量均為非基變量，取值為零，故原線性規(guī)劃問題達(dá)到最優(yōu)。,線性規(guī)劃的二階段法(1),原線性規(guī)劃問題為,第一階段:,y1， y2， ym稱為人工變量,構(gòu)造原(LP)的輔助問題,線性規(guī)劃的二階段法(2),原(LP)的輔助問題的標(biāo)準(zhǔn)形式為：,輔助問題必有最優(yōu)解,線性規(guī)劃的二階段法(初

5、始單純形表1),輔助問題的標(biāo)準(zhǔn)形式的系數(shù)矩陣為：,線性規(guī)劃的二階段法(初始單純形表2),用單純形法求解,最終得到輔助問題的最優(yōu)單純形表T(B*),二階段法的計(jì)算步驟:,第二步 若 w*0,則原線性規(guī)劃無可行解,停止求解, 否則轉(zhuǎn)第三步.,第一步 用單純形法求輔助問題的最優(yōu)單純形表T(B*) 和最優(yōu)值w*.,第三步 T(B*)中基變量中不含人工變量y,則把T(B*)中人 工變量所在列劃去,把檢驗(yàn)數(shù)行用原規(guī)劃的目標(biāo)函 數(shù)的系數(shù)替代再把基變量的檢驗(yàn)數(shù)化為0,即得原 規(guī)劃的一個(gè)可行基的單純形表.再用單純形法迭 代,直到終止.否則轉(zhuǎn)第四步.,第四步 w*=0,T(B*)中基變量中含有人工變量yr,若yr

6、所在 行的對應(yīng)的X系數(shù)全為0 ,則劃去T(B*)中yr所在行 和所在的列,轉(zhuǎn)第三步。否則以某變量xS的系數(shù) brs0為軸心項(xiàng)進(jìn)行換基迭代后轉(zhuǎn)第三步。,線性規(guī)劃的二階段法舉例（1）,例1. 用二階段法求解下列(LP)問題,解:,化原問題為標(biāo)準(zhǔn)形式,則第一階段的輔助問題為,線性規(guī)劃的二階段法舉例（1-2）,輔助問題的標(biāo)準(zhǔn)形式為,線性規(guī)劃的二階段法舉例（例1-3）,則輔助問題的單純表,T(B1),XB,b,x1 x2 x3 x4 x5 x6 y2 y3,x4 y2 y3,64 3,w,7,1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,1 1

7、-2 0 -1 -1 0 0,T(B2),x4,x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1 0 1 0,3,0 1 -1 0 0 -1 0 1,3,0,1,-1,0,0,-1,-1,0,二階段法舉例（例1-4）,T(B2),x4,XB,b,x1 x2 x3 x4 x5 x6 y2 y3,x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1 0 1 0,3,0 1 -1 0 0 -1 0 1,3,0,1,-1,0,0,-1,-1,0,x2,T(B3),x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1

8、 0 1 0,1,0 0 -3 -1 -1 -1 1 1,1,0,0,-3,-1,-1,-1,0,0,因?yàn)檩o助問題的最優(yōu)值W*=10，則原問題無可行解。,線性規(guī)劃的二階段法 例2-1,例2 用二階段法解 線性規(guī)劃,解:,引進(jìn)人工變量y20，建立第一階段的輔助問題為,線性規(guī)劃的二階段法舉例（例2-2）,輔助問題的標(biāo)準(zhǔn)形式為,則第一階段的初始單純形表 為T（B1）,例2-3,T(B1),x2,x1,w,1,0 1 1/4 -2/3 -1/3,2,1 0 1/2 0 2/3,0,0,0,0,0,T(B2),-1,例2-4,得w*=0，且基變量中不含有人工變量，則劃去T(B2)中y2所在列,把檢驗(yàn)數(shù)行

9、用原問題的目標(biāo)函數(shù)的系數(shù)替代再把基變量的檢驗(yàn)數(shù)化為0,即得第二階段的初始單純形表.,T(B2),c,-4,-3,0,0,-z,11,0 0 11/4 -2,例2-5,則原問題的一個(gè)初始單純形表如下,x2,x1,1,2,0 1 1/4 -2/3,1 0 1/2 0,-z,0 0 11/4 -2,x2,x3,-z,11,0,-1/2 1 0 -2/3,4,2 0 1 0,0,-11/2 0 0 -2,原問題最優(yōu)解X*=(0,0,4,0)T,原問題最優(yōu)值為z*=0,例3-1,例3 用二階段法解下 列線性規(guī)劃,解: 該問題的標(biāo)準(zhǔn)形式為：,線性規(guī)劃的二階段法舉例（例3-2）,輔助問題的標(biāo)準(zhǔn)形式為,則第一

10、階段的單純形初表為T（B1）,引進(jìn)人工變量y1,y2,y3，建立第一階段的輔助問題為：,例3-3,T(B1),y1,y2,w,3/2,0 1 1/2 1/2 1 0 1/2,3/2,0 1 1/2 1/2 0 1 -1/2,3,0,2,1,1,0,T(B2),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-1,例3-4,T(B2),x2,y2,w,3/2,0 1 1/2 1/2 1 0 1/2,0,0 0 0 0 -1 1 -1,0,0,0,0,0,0,T(B3),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-2,例3-5,x2,y2,w,3/2,0 1 1/2

11、1/2 1 0 1/2,0,0 0 0 0 -1 1 -1,0,0,0,0,0,0,T(B3),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-2,c,2,1,0,0,得w*=0，T(B3)中基變量中含有人工變量y2,且y2所在行的對應(yīng)的X系數(shù)全為0 ,則劃去T(B3)中y2所在行，此時(shí)，基變量中不再含有人工變量，則劃去T(B3)中人工變量所在列,把檢驗(yàn)數(shù)行用原問題的標(biāo)準(zhǔn)形式的目標(biāo)函數(shù)的系數(shù)替代再把基變量的檢驗(yàn)數(shù)化為0,即得第二階段的初始單純形表.,XB,b,x1 x2 x3 x4 y1 y2 y3,例3-6,T(B3),T(B4),z,0,0,-5/2,1/2,-3/2,x3 x1,3 2,0 2 1 1 1 1 0 1,z,-4,0 -1 0 -2,原最優(yōu)解X* =(2,0,3,0)T,最優(yōu)值為 z*=-4,Yes,Yes,NO,NO,Yes,NO,二階段法