線性規(guī)劃的二階段法MaxPPT學(xué)習(xí)教案

1、會計學(xué)1目前有兩種方法：目前有兩種方法：大大M M法法和和二階段法二階段法。人人工工變變量量法法在討論單純形法時，我們在討論單純形法時，我們總是假定總是假定AXAXb b的系數(shù)矩陣的系數(shù)矩陣A A的秩的秩r(A)=mn,r(A)=mn,或者已有一個可行基?；蛘咭延幸粋€可行基。但是，在許但是，在許多問題中，初始可行基是不容易找到的，或者多問題中，初始可行基是不容易找到的，或者A A不滿不滿秩。這樣單純形法就很難進行。秩。這樣單純形法就很難進行。所以，我們要探討如何尋找第一個可行基？所以，我們要探討如何尋找第一個可行基？11 112 211121 122 22221 12 201,2,01,2,n

2、 nn nmmmn nmmjia xa xa xyba xaxaxybaxaxaxybxjnyim第1頁/共32頁12111 112211121 12222221 122max(1). .01,2,01,2,njjmjnnnnmmmnnmmjizc xMyMyMya xa xa xybLPa xa xaxybs taxaxaxybxjnyim把原問題化為下列形式：其中把原問題化為下列形式：其中M M是任意大的正數(shù)是任意大的正數(shù)第2頁/共32頁關(guān)于大關(guān)于大M M法的幾點注釋：法的幾點注釋：(1)在引入人工變量之前，約束條件已是等式，為了這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零；為此在

3、目標函數(shù)中人工變量的取值為充分小的負數(shù)，用“-M”代表；(2)若在單純形表中有j0，且存在非零人工變量，則原問題無可行解；若基變量中不再含有非零的人工變量，這表示原問題有解；(3)引入的人工變量個數(shù)越少越好，只要出現(xiàn)單位矩陣作為基陣即可。第3頁/共32頁1312312323min 3421(1). .390,1,2,3jzxxxxxxxxLPstxxxj131234123523max3421.390,1,2,3,4,5jzxxxxxxxxxxstxxxj例例解：將原問題化為標準形為：第4頁/共32頁1323123412352233max3421. .390,1,2,3,4,5,0,2,3jiz

4、xxMyMyxxxxxxxxystxxyxjyi引入的人工變量個數(shù)越少越好引入人工變量y2,y30,由大M法得輔助問題為輔助問題為：其中大M為任意大的正數(shù)得上述輔助問題的單純形初表為：第5頁/共32頁 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 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 -

5、4M0人工變量優(yōu)先出基人工變量優(yōu)先出基第6頁/共32頁 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 -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第7頁/共32頁大大M法舉例（法舉

6、例（5）原線性規(guī)劃問題的最優(yōu)解為*5 30,0,0,0,0,2 2TX*32z 最優(yōu)值為：因為在單純形表T(B4)中，非基變量檢驗數(shù)均小于等于零，且人工變量均為非基變量，取值為零，故原線性規(guī)劃問題達到最優(yōu)。第8頁/共32頁原線性規(guī)劃問題為原線性規(guī)劃問題為第一階段第一階段:y y1 1， y y2 2， y ym m稱為人工變量稱為人工變量構(gòu)造原構(gòu)造原(LP)的輔助問題的輔助問題max(). .0zCXLPAXbs tX1211 112211121 12222221 122in(1). .01,2,01,2,mnnnnmmmnnmmjimwyyya xa xa xyba xa xa xybLPs

7、ta xaxaxybxjnyim第9頁/共32頁原原(LP)的輔助問題的標準形式為：的輔助問題的標準形式為：1211 112211121 12222221 122max(1). .01,2,01,2,mnnnnmmmnnmmjiwwyyya xa xa xyba xa xa xybLPsta xaxaxybxjnyim 輔助問題必有最優(yōu)解輔助問題必有最優(yōu)解第10頁/共32頁1.00.0.10.0.01.212222111211mnmmnnaaaaaaaaaA).(21mnnnPPPB(0 0.011. 1)C (11.1)BCTmbbbb).(21輔助問題的標準形式輔助問題的標準形式的系數(shù)矩陣

8、為：的系數(shù)矩陣為：第11頁/共32頁用單純形法求解用單純形法求解,最終得到輔助問題的最優(yōu)單純形表最終得到輔助問題的最優(yōu)單純形表T(B*)第12頁/共32頁第二步第二步 若若 w*0,則原線性規(guī)劃無可行解則原線性規(guī)劃無可行解,停止求解停止求解,否則轉(zhuǎn)第三步否則轉(zhuǎn)第三步.第一步第一步 用單純形法求輔助問題的最優(yōu)單純形表用單純形法求輔助問題的最優(yōu)單純形表T(B*)和和最優(yōu)值最優(yōu)值w*. 第三步第三步 T(B*)中基變量中不含人工變量中基變量中不含人工變量y,則把則把T(B*)中人中人工變量所在列劃去工變量所在列劃去,把檢驗數(shù)行用原規(guī)劃的目標函把檢驗數(shù)行用原規(guī)劃的目標函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化

9、為數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得原即得原規(guī)劃的一個可行基的單純形表規(guī)劃的一個可行基的單純形表.再用單純形法迭再用單純形法迭代代,直到終止直到終止.否則轉(zhuǎn)第四步否則轉(zhuǎn)第四步. 第四步第四步 w*=0,T(B*)中基變量中含有人工變量中基變量中含有人工變量yr,若若yr所在所在行的對應(yīng)的行的對應(yīng)的X系數(shù)全為系數(shù)全為0 ,則劃去則劃去T(B*)中中yr所在行所在行和所在的列和所在的列,轉(zhuǎn)第三步轉(zhuǎn)第三步。否則以某變量。否則以某變量xS的系數(shù)的系數(shù)brs 0為軸心項進行換基迭代為軸心項進行換基迭代后轉(zhuǎn)第三步后轉(zhuǎn)第三步。 第13頁/共32頁例例1. 用二階段法求解下列用二階段法求解下列(LP)

10、問問題題 1231231323123in-3-2-64. .3,0mzxxxxxxxxs txxxxx1231234135236max3264. .30(1,.,6)jzzxxxxxxxxxxs txxxxj 解解: 化原問題為標準形式化原問題為標準形式 23123413522363in64. .30(1,.,6),0jimwyyxxxxxxxys txxxyxjy則第一階段的輔助問題為則第一階段的輔助問題為 第14頁/共32頁 23123413522363max64. .30(1,.,6),0jiwwyyxxxxxxxys txxxyxjy 輔助問題的標準形式為輔助問題的標準形式為 第15頁

11、/共32頁則輔助問題的單純表則輔助問題的單純表 T(B1)XB b x1 x2 x3 x4 x5 x6 y2 y3x4 y2 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-10第16頁/共32頁 T(B2)x4 XB b x1 x2 x3 x4 x5 x6 y2 y3x1 y3 w2 0 1 2 1 1 0 -1

12、 04 1 0 -1 0 -1 0 1 03 0 1 -1 0 0 -1 0 1 30 1 -1 00 -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，則原問題無可行解，則原問題無可行解。第17頁/共32頁例例2 用二階段法解用二階段法解線性規(guī)劃線性規(guī)劃 121121234223331324ax-4 -32( ). .30,1,2,3,4jmzxxxxxxlpstxxxj解解: 引進人工變量引

13、進人工變量y20，建立第一階段的輔助問題為建立第一階段的輔助問題為 21121234223133132242min2( ).30,1,2,3,4;0jw yxxxxlpstxxyxjy第18頁/共32頁 輔助問題的標準形式為輔助問題的標準形式為 2112123422333132242max2. .30,1,2,3,4;0jwwyxxxxstxxyxjy 則第一階段的初始則第一階段的初始單純形表單純形表 為為T（B1）第19頁/共32頁 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 T(B

14、1) x2 x1w 1 0 1 1/4 -2/3 -1/321 0 1/2 0 2/3 00000 T(B2)-1第20頁/共32頁得得w*=0，且基變量中不含有人工變量，則劃去，且基變量中不含有人工變量，則劃去T(B2)中中y2所在列所在列,把檢驗數(shù)行用原問題的目標函數(shù)的系數(shù)替代再把把檢驗數(shù)行用原問題的目標函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為基變量的檢驗數(shù)化為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-

15、z 11 0 0 11/4 -2 第21頁/共32頁則原問題的一個初始單純形表如下則原問題的一個初始單純形表如下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第22頁/共32頁例例3 用二階段法解下用二階段法解下列線性規(guī)劃列線性規(guī)劃 12123124134min212( ).210,1,2,3,4jzxxxxxxxxlpstxxxx

16、j解解: 該問題的標準形式為：該問題的標準形式為：12123124134max212( 1). .210,1,2,3,4jzzxxxxxxxxlpstxxxxj 第23頁/共32頁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，

17、建立第一階段的輔助問題為建立第一階段的輔助問題為：第24頁/共32頁 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第25頁/共32頁 XB bx1 x2 x3 x4 y1 y2 y3 y1 y2 x1 3/2 3/2 1/2 0 1 1

18、/2 1/2 1 0 1/2 0 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第26頁/共32頁x2 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所在行的所在行的對應(yīng)的對應(yīng)的X系數(shù)全為系數(shù)全為0 ,則劃去則劃去T(B3)中中y2所在行，此時，基所在行，此時，基變量中不再含有人工變量，則劃去變量中不再含有人工變量，則劃去T(B3)中人工變量所在中人工變量所在列列,把檢驗數(shù)行用原問題的標準形式的目標函數(shù)的系數(shù)替把檢驗數(shù)行用原問題的標準形式的目標函數(shù)的系數(shù)替代再把基變量的