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

1、第一章第一章 線性規(guī)劃及其擴展線性規(guī)劃及其擴展 第第5節(jié)節(jié) 單純形法的進一步討論單純形法的進一步討論 線性規(guī)劃的人工變量法線性規(guī)劃的人工變量法目前有兩種方法：目前有兩種方法：大大M M法法和和二階段法二階段法。人人工工變變量量法法在討論單純形法時，我們在討論單純形法時，我們總是假定總是假定AXAXb b的系數矩陣的系數矩陣A A的秩的秩r(A)=mn,r(A)=mn,或者已有一個可行基。或者已有一個可行基。但是，在許多但是，在許多問題中，初始可行基是不容易找到的，或者問題中，初始可行基是不容易找到的，或者A A不滿秩。不滿秩。這樣單純形法就很難進行。這樣單純形法就很難進行。所以，我們要探討如何

2、尋找第一個可行基？所以，我們要探討如何尋找第一個可行基？11 112 211121 122 22221 12 201,2,01,2,n nn nmmmn nmmjia xa xa xyba xaxaxybaxaxaxybxjnyim大大M M法（法（1 1）12111 112211121 12222221 122max(1). .01,2,01,2,njjmjnnnnmmmnnmmjizc xMyMyMya xa xa xybLPa xa xa xybs taxaxaxybxjnyim把原問題化為下列形式：其中把原問題化為下列形式：其中M M是任意大的正數是任意大的正數大大M M法（法（2 2

3、）關于大關于大M M法的幾點注釋：法的幾點注釋：(1)在引入人工變量之前，約束條件已是等式，為了這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零；為此在目標函數中人工變量的取值為充分小的負數，用“-M”代表；(2)若在單純形表中有j0，且存在非零人工變量，則原問題無可行解；若基變量中不再含有非零的人工變量，這表示原問題有解；(3)引入的人工變量個數越少越好，只要出現單位矩陣作為基陣即可。大大M M法舉例（法舉例（1 1）1312312323min 3421(1). .390,1,2,3jzxxxxxxxxLPstxxxj131234123523max3421.390,1,2,3,4,5jz

4、xxxxxxxxxxstxxxj例例解：將原問題化為標準形為：大大M M法舉例（法舉例（2 2）1323123412352233max3421.390,1,2,3,4,5,0,2,3jizxxMyMyxxxxxxxxystxxyxjyi引入的人工變量個數越少越好引入人工變量y2,y30,由大M法得輔助問題為輔助問題為：其中大M為任意大的正數得上述輔助問題的單純形初表為：大大M法舉例（法舉例（3） T(B1)XB b x1 x2 x3 x4 x5 y2 y3x4 y2 y3419 -z10M 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1-2M-3 4M

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

6、1/2 5/2-1/2 1 0 0 -1/4 1/4 1/4 3/23/2 0 1 0 3/4 -3/4 1/4 -3/2-9/20 0 0-3/4-M+3/4 -M-1/4大大M法舉例（法舉例（5）原線性規(guī)劃問題的最優(yōu)解為*5 30,0,0,0,0,2 2TX*32z 最優(yōu)值為：因為在單純形表T(B4)中，非基變量檢驗數均小于等于零，且人工變量均為非基變量，取值為零，故原線性規(guī)劃問題達到最優(yōu)。線性規(guī)劃的二階段法線性規(guī)劃的二階段法(1)原線性規(guī)劃問題為原線性規(guī)劃問題為第一階段第一階段:y y1 1， y y2 2， y ym m稱為人工變量稱為人工變量構造原構造原(LP)的輔助問題的輔助問題m

7、ax(). .0zCXLPAXbs tX1211 112211121 12222221 122in(1). .01,2,01,2,mnnnnmmmnnmmjimwyyya xa xa xyba xa xa xybLPsta xaxaxybxjnyim線性規(guī)劃的二階段法線性規(guī)劃的二階段法(2)原原(LP)的輔助問題的標準形式為：的輔助問題的標準形式為：1211 112211121 12222221 122max(1). .01,2,01,2,mnnnnmmmnnmmjiwwyyya xa xa xyba xa xa xybLPsta xaxaxybxjnyim 輔助問題必有最優(yōu)解輔助問題必有最優(yōu)

8、解線性規(guī)劃的二階段法線性規(guī)劃的二階段法(初始單純形表初始單純形表1)1.00.0.10.0.01.212222111211mnmmnnaaaaaaaaaA).(21mnnnPPPB(0 0.011. 1)C (11.1)BCTmbbbb).(21輔助問題的標準形式輔助問題的標準形式的系數矩陣為：的系數矩陣為：線性規(guī)劃的二階段法線性規(guī)劃的二階段法(初始單純形表初始單純形表2)用單純形法求解用單純形法求解,最終得到輔助問題的最優(yōu)單純形表最終得到輔助問題的最優(yōu)單純形表T(B*)二階段法的計算步驟二階段法的計算步驟:第二步第二步 若若 w*0,則原線性規(guī)劃無可行解則原線性規(guī)劃無可行解,停止求解停止求解

9、,否則轉第三步否則轉第三步.第一步第一步 用單純形法求輔助問題的最優(yōu)單純形表用單純形法求輔助問題的最優(yōu)單純形表T(B*)和和最優(yōu)值最優(yōu)值w*. 第三步第三步 T(B*)中基變量中不含人工變量中基變量中不含人工變量y,則把則把T(B*)中人中人工變量所在列劃去工變量所在列劃去,把檢驗數行用原規(guī)劃的目標函把檢驗數行用原規(guī)劃的目標函數的系數替代再把基變量的檢驗數化為數的系數替代再把基變量的檢驗數化為0,即得原即得原規(guī)劃的一個可行基的單純形表規(guī)劃的一個可行基的單純形表.再用單純形法迭再用單純形法迭代代,直到終止直到終止.否則轉第四步否則轉第四步. 第四步第四步 w*=0,T(B*)中基變量中含有人工變

10、量中基變量中含有人工變量yr,若若yr所在所在行的對應的行的對應的X系數全為系數全為0 ,則劃去則劃去T(B*)中中yr所在行所在行和所在的列和所在的列,轉第三步轉第三步。否則以某變量。否則以某變量xS的系數的系數brs 0為軸心項進行換基迭代為軸心項進行換基迭代后轉第三步后轉第三步。 線性規(guī)劃的二階段法舉例（線性規(guī)劃的二階段法舉例（1）例例1. 用二階段法求解下列用二階段法求解下列(LP)問題問題 1231231323123in-3-2-64. .3,0mzxxxxxxxxs txxxxx1231234135236max3264. .30(1,.,6)jzzxxxxxxxxxxs txxxx

11、j 解解: 化原問題為標準形式化原問題為標準形式 23123413522363in64. .30(1,.,6),0jimwyyxxxxxxxys txxxyxjy則第一階段的輔助問題為則第一階段的輔助問題為 線性規(guī)劃的二階段法舉例（線性規(guī)劃的二階段法舉例（1-2） 23123413522363max64. .30(1,.,6),0jiwwyyxxxxxxxys txxxyxjy 輔助問題的標準形式為輔助問題的標準形式為 線性規(guī)劃的二階段法舉例（例線性規(guī)劃的二階段法舉例（例1-3）則輔助問題的單純表則輔助問題的單純表 T(B1)XB b x1 x2 x3 x4 x5 x6 y2 y3x4 y2

12、y3643 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 -2 0 -1 -1 0 0 T(B2)x4 x1 y3 w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 03 0 1 -1 0 0 -1 0 1 301 -1 0 0-1 -1 0二階段法舉例（例二階段法舉例（例1-4） T(B2)x4 XB b x1 x2 x3 x4 x5 x6 y2 y3x1 y3 w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 03 0 1 -1 0 0 -1 0 1 30 1 -1 0

13、0 -1-10 x2 T(B3)x1y3w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 01 0 0 -3 -1 -1 -1 1 1 1 0 0 -3 -1 -1 -1 0 0 因為輔助問題的因為輔助問題的最優(yōu)值最優(yōu)值W*=10，則原問題無可行解，則原問題無可行解。線性規(guī)劃的二階段法線性規(guī)劃的二階段法 例例2-1例例2 用二階段法解用二階段法解線性規(guī)劃線性規(guī)劃 121121234223331324ax-4 -32( ). .30,1,2,3,4jmzxxxxxxlpstxxxj解解: 引進人工變量引進人工變量y20，建立第一階段的輔助問題為建立第一階段的輔助問題為 2

14、1121234223133132242min2( ).30,1,2,3,4;0jw yxxxxlpstxxyxjy線性規(guī)劃的二階段法舉例（例線性規(guī)劃的二階段法舉例（例2-2） 輔助問題的標準形式為輔助問題的標準形式為 2112123422333132242max2. .30,1,2,3,4;0jwwyxxxxstxxyxjy 則第一階段的初始單純形表則第一階段的初始單純形表 為為T（B1） XB b x1 x2 x3 x4 y2 x2 y2 2 31/2 1 1/2 -2/3 0 3/2 0 3/4 0 1 w 33/2 0 3/4 0 0例例2-3 T(B1) x2 x1w 1 0 1 1/

15、4 -2/3 -1/321 0 1/2 0 2/3 00000 T(B2)-1例例2-4得得w*=0，且基變量中不含有人工變量，則劃去，且基變量中不含有人工變量，則劃去T(B2)中中y2所在列所在列,把檢驗數行用原問題的目標函數的系數替代再把把檢驗數行用原問題的目標函數的系數替代再把基變量的檢驗數化為基變量的檢驗數化為0,即得第二階段的初始單純形表即得第二階段的初始單純形表. T(B2)c-4-300 XB b x1 x2 x3 x4 y2 x2 x1 1 20 1 1/4 -2/3 -1/3 1 0 1/2 0 2/3 w 00 0 0 0 -1-z 11 0 0 11/4 -2 例例2-5

16、則原問題的一個初始單純形表如下則原問題的一個初始單純形表如下x2 x1 12 0 1 1/4 -2/3 1 0 1/2 0 -z 0 0 11/4 -2 XBb x1 x2 x3 x4 x2 x3 -z 110-1/2 1 0 -2/3 4 2 0 1 0 0-11/2 0 0 -2 原問題最優(yōu)解原問題最優(yōu)解X*=(0,0,4,0)T原問題最優(yōu)值為原問題最優(yōu)值為z*=0例例3-1例例3 用二階段法解下用二階段法解下列線性規(guī)劃列線性規(guī)劃 12123124134min212( ).210,1,2,3,4jzxxxxxxxxlpstxxxxj解解: 該問題的標準形式為：該問題的標準形式為：12123

17、124134max212( 1). .210,1,2,3,4jzzxxxxxxxxlpstxxxxj 線性規(guī)劃的二階段法舉例（例線性規(guī)劃的二階段法舉例（例3-2）123123112421343max12. .210,1,2,3,4,0,1,2,3jjwwyyyxxxyxxxystxxxyxjyj 輔助問題的標準形式為輔助問題的標準形式為 則第一階段的單純形初表為則第一階段的單純形初表為T（B1）123123112421343min12(2). .210,1,2,3,4,0,1,2,3jjwyyyxxxyxxxylpstxxxyxjyj引進引進人工變量人工變量y1,y2,y3，建立第一階段的輔助

18、問題為：建立第一階段的輔助問題為：例例3-3 XB b x1 x2 x3 x4 y1 y2 y3 y1 y2 y3 1 2 1-1 1 1 0 1 0 0 1 1 0 1 0 1 0 2 0 -1 1 0 0 1 w 4 2 2 0 2 0 0 0 T(B1)y1 y2w3/2 0 1 1/2 1/2 1 0 1/23/20 1 1/2 1/2 0 1 -1/2 3021 10 T(B2)0 x11/2 1 0 -1/2 1/2 0 0 1/2 -1例例3-4 XB bx1 x2 x3 x4 y1 y2 y3 y1 y2 x1 3/2 3/2 1/2 0 1 1/2 1/2 1 0 1/2 0

19、 1 1/2 1/2 0 1 -1/2 1 0 -1/2 1/2 0 0 1/2 w 3 0 2 1 1 0 0 -1 T(B2)x2 y2w3/2 0 1 1/2 1/2 1 0 1/200 0 0 0 -1 1 -1 0000 00 T(B3)0 x11/21 0 -1/2 1/2 0 0 1/2 -2例例3-5x2 y2w3/2 0 1 1/2 1/2 1 0 1/200 0 0 0 -1 1 -1 000 0 00 T(B3)0 x11/21 0 -1/2 1/2 0 0 1/2 -2 c 2 100得得w*=0，T(B3)中基變量中含有人工變量中基變量中含有人工變量y2,且且y2所在行的所在行的對應的對應的X系數全為系數全為0 ,則劃去則劃去T(B3)中中y2所在行，此時，基變所在行，此時，基變量中不再含有人工變量，則劃去量中不再含有人工變量，則劃去T(B3)中人工變量所在列中人工變量所在列,把檢驗數行用原問題的標準形式的目