運籌學5單純形法PPT學習教案

1、會計學1 運籌學運籌學5單純形法單純形法 30 2 . 1 X bAX ts CXZMax (1) 解的基本概念解的基本概念 定義定義 在線性規(guī)劃問題中，約束方程組在線性規(guī)劃問題中，約束方程組(2)(2)的系的系 數(shù)矩陣數(shù)矩陣A(A(假定假定 ) )的任意一個的任意一個 階的非奇階的非奇 異異( (可逆可逆) )的子方陣的子方陣B(B(即即 ) )，稱為線性規(guī)劃，稱為線性規(guī)劃 問題的一個問題的一個基陣基陣或或基基。 mm 0B nm 第1頁/共68頁 mnmmmmmmmm nmmm nmmm aaaaaa aaaaaa aaaaaa A 2121 2221222221 1211111211 m

2、mmm m m aaa aaa aaa B 21 22221 11211 mnmmmm nmm nmm aaa aaa aaa N 21 22212 12111 基陣基陣 非基非基 陣陣 T mB xxxX 21 T nmmN xxxX 21 基基 向向 量量 非非 基基 向向 量量 基變量基變量非基變量非基變量 第2頁/共68頁 NBA N B X X X bAX b X X NB N B bNXBX NB NB NXbBX NB NXBbBX 11 N B X X X N N X NXBbB X 11 令令0 N X 則則 0 1b B X 定義定義 在約束方程組在約束方程組(2) 中，對

3、于中，對于 一個選定的基一個選定的基B，令所有的非基變，令所有的非基變 量為零得到的解，稱為相應(yīng)于基量為零得到的解，稱為相應(yīng)于基B 的基本解。的基本解。 第3頁/共68頁 定義定義 在基本解中，若該基本解滿足非負約束，在基本解中，若該基本解滿足非負約束， 即即 ，則稱此基本解為，則稱此基本解為基本可行解基本可行解，簡，簡 稱稱基可行解基可行解；對應(yīng)的基；對應(yīng)的基B稱為稱為可行基可行基。 0 1 bBX B 定義定義 在線性規(guī)劃問題的一個基本可行解中，如在線性規(guī)劃問題的一個基本可行解中，如 果所有的基變量都取正值，則稱它為果所有的基變量都取正值，則稱它為非退化解非退化解， 如果所有的基本可行解都

4、是非退化解。稱該問題如果所有的基本可行解都是非退化解。稱該問題 為為非退化的線性規(guī)劃問題非退化的線性規(guī)劃問題；若基本可行解中，有；若基本可行解中，有 基變量為零，則稱為基變量為零，則稱為退化解退化解，該問題稱為，該問題稱為退化的退化的 線性規(guī)劃問題線性規(guī)劃問題。 基本解中最多有基本解中最多有m個非零分量。個非零分量。 基本解的數(shù)目不超過基本解的數(shù)目不超過 個。個。 ! ! mnm n C m n 第4頁/共68頁 解空間解空間 第5頁/共68頁 例例 現(xiàn)有線性規(guī)劃問題現(xiàn)有線性規(guī)劃問題 0, 2426 1553 . 2 21 21 21 21 xx xx xx ts xxZMax 試求其基本解、

5、基本可行解并判斷是否為退試求其基本解、基本可行解并判斷是否為退 化解?；?。 第6頁/共68頁 解解: (1)首先將原問題轉(zhuǎn)化為標準型首先將原問題轉(zhuǎn)化為標準型 引入松弛變量引入松弛變量x3和和x4 0, 24026 15053 . 2 4321 4321 4321 21 xxxx xxxx xxxx ts xxZMax (2) 求基本解求基本解 由上式得由上式得 1026 0153 A 24 15 b 第7頁/共68頁 可能的基可能的基 陣陣 1026 0153 A 26 53 12 B 06 13 13 B 16 03 14 B 02 15 23 B 12 05 24 B 10 01 34

6、B 6 1212 1234 !24! 2 ! 4 2 4 C 由于所有由于所有|B| 0, 所以有所以有6個基陣個基陣 和和6個基本解。個基本解。 第8頁/共68頁 2426 1553 21 21 xx xx 對于基陣對于基陣 26 53 12 B令令 0 3 x0 4 x 則則 T X 00 4 3 4 15 246 153 1 31 x xx 對于基陣對于基陣令令0 2 x0 4 x 則則 T X0304 06 13 13 B 為基本可行解，為基本可行解，B13為可行基為可行基 為基本可行解，為基本可行解，B12為可行基為可行基 第9頁/共68頁 246 153 41 1 xx x 對于基

7、陣對于基陣令令 0 2 x0 3 x 則則 T X6005 242 155 2 32 x xx 對于基陣對于基陣令令0 1 x0 4 x 則則 T X045120 16 03 14 B 02 15 23 B 第10頁/共68頁 242 155 42 2 xx x 對于基陣對于基陣令令 0 1 x0 3 x 則則 T X18030 24 15 4 3 x x 對于基陣對于基陣令令0 1 x0 2 x 則則 T X241500 12 05 24 B 10 01 34 B 為基本可行解，為基本可行解，B24為可行基為可行基 為基本可行解，為基本可行解，B34為可行基為可行基 第11頁/共68頁 0

8、A B C D E T 12 X 00 4 3 4 15 T 13 X0304 T 14 X6005 24 15 0 0 X34 18 0 3 0 X24 0 45 12 0 X23 1 1 基本解為邊界約束方程的交點；基本解為邊界約束方程的交點； 2 2 基對應(yīng)于可行解可行域極點；基對應(yīng)于可行解可行域極點； 3 3 相鄰基本解的腳標有一個相同。相鄰基本解的腳標有一個相同。 第12頁/共68頁 (2) 解的基本性質(zhì)解的基本性質(zhì) 判別可行解為基可行解的準則判別可行解為基可行解的準則 定理定理1 線性規(guī)劃問題的可行解是基可行解的充要線性規(guī)劃問題的可行解是基可行解的充要 條件是它的非零向量所對應(yīng)的列

9、向量線性無關(guān)條件是它的非零向量所對應(yīng)的列向量線性無關(guān). 線性規(guī)劃問題的基本定理線性規(guī)劃問題的基本定理:定理定理2和定理和定理3 定理定理2 線性規(guī)劃問題有可行解線性規(guī)劃問題有可行解,則它必有基可行解則它必有基可行解. 定理定理3 若線性規(guī)劃問題有最優(yōu)解若線性規(guī)劃問題有最優(yōu)解,則一定存在一個則一定存在一個 基可行解是它的最優(yōu)解基可行解是它的最優(yōu)解. 第13頁/共68頁 幾點結(jié)論幾點結(jié)論 v若線性規(guī)劃問題有可行解若線性規(guī)劃問題有可行解,則可行域是一個凸多邊形則可行域是一個凸多邊形 或凸多面體或凸多面體(凸集凸集),且僅有有限個頂點且僅有有限個頂點(極點極點); v線性規(guī)劃問題的每一個基可行解都對應(yīng)

10、于可行域上線性規(guī)劃問題的每一個基可行解都對應(yīng)于可行域上 的一個頂點的一個頂點(極點極點); v若線性規(guī)劃問題有最優(yōu)解若線性規(guī)劃問題有最優(yōu)解,則最優(yōu)解必可在基可行解則最優(yōu)解必可在基可行解 (極點極點)上達到上達到; v線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解(極點極點)的個數(shù)是有限的的個數(shù)是有限的,不不 會超過會超過 個個. m n C 上述結(jié)論說明上述結(jié)論說明: 線性規(guī)劃的最優(yōu)解可通過有限次運算在基可行解中獲得線性規(guī)劃的最優(yōu)解可通過有限次運算在基可行解中獲得. 第14頁/共68頁 l例例1 1 Max Z=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =6

11、0 2X2 +X5 =24 X1 X5 0 0 (1)單純形法的引入單純形法的引入 第15頁/共68頁 解：解：(1)(1)、確定初始可行解、確定初始可行解 B = ( P3 P4 P5 ) = I Z = 0 + 40X1 + 50X2 X3 = 30 - ( X1 + 2X2 ) X4= 60 - ( 3X1 + 2X2 ) X5 = 24 - 2 X2 令令X1 = X2 =0 X(1) =(0, 0, 30, 60, 24)T Z(1) =0 第16頁/共68頁 (2)(2)、判定解是否最優(yōu)、判定解是否最優(yōu) Z=0+40X1+50X2 當當 X1 從從 0 或或 X2 從從 0 Z 從

12、從 0 X X(1) (1) 不是最優(yōu)解 不是最優(yōu)解 第17頁/共68頁 (3)(3)、由一個基可行解、由一個基可行解另一個基可行解。另一個基可行解。 50 40 選選 X2 從從 0，X1 =0 X3 = 30 - 2X2 0 0 X2 30/2 X4 = 60 - 2X2 0 0 X2 60/2 X5 = 24 - 2 X2 0 0 X2 24/2 X2 = min ( 30/2 , 60/2 , 24/2 ) =12 X2 ： ：進基變量 進基變量， X5 ： ：出基變量 出基變量。 第18頁/共68頁 B B2 2=( P3 P4 P2 ) Z= 0 + 40 X1 + 50 X2 X

13、3 + 2X2 = 30 - X1 X4 + 2X2 = 60 - 3X1 2X2 = 24 - X5 第19頁/共68頁 1/2 ， 代入代入 式，式， ， Z = 600 + 40X1 - 25X5 X3 = 6 - X1 + X5 X4 = 36 - 3X1 + X5 X2 = 12 -1/2X5 令令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 600 第20頁/共68頁 (2)(2) 判斷判斷 400 X(2)不是最優(yōu)解不是最優(yōu)解。 (3) 選選X1從從0 ， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2

14、=12 0 0 X1=min( 6/1 , 36/3 , 1 ) =6 X1進基，進基， X3出基。出基。 第21頁/共68頁 B3 =(P1 P4 P2 ) Z=840-40X3+15X5 X1=6 - X3 + X5 X4= 18+3X3 - 2X5 X2=12 -1/2X5 令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)T Z(3) =840 第22頁/共68頁 (2) 150 X(3)不是不是 (3) 選選X5從從0 ， X3 =0 X1=6 +X5 0 X4= 18 -2X5 0 X2=12-1/2 X5 0 X5=min( 18/2 , 12/1/2 ) =

15、9 X5進基，進基， X4出基。出基。 第23頁/共68頁 B4=(P1 P5 P2 ) Z=975- 35/2X3 - 15/2X4 X1= 15 + 1/2X3 - 1/2X4 X5= 9 + 3/2X3 - 1/2X4 X2= 15/2 -3/4X3 + 1/4X4 令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975 第24頁/共68頁 0(0,0) X2 X1 A D C B (0,12) (6,12) (15,7.5) X(4) X(1) X(2) X(3) Z=40X1+50X2 第25頁/共68頁 單純形法小結(jié)：單純形法小結(jié)： 單

16、純形法是這樣一種迭代算法單純形法是這樣一種迭代算法如下圖如下圖 當當Zk中中非基變量非基變量的系數(shù)的系數(shù)全為負值時，這時的基本可的系數(shù)的系數(shù)全為負值時，這時的基本可 行解行解Xk即是線性規(guī)劃問題的最優(yōu)解，即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。迭代結(jié)束。 X 1 Z 1 保持單調(diào)增保持單調(diào)增 保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性 保持單調(diào)增保持單調(diào)增保持單調(diào)增保持單調(diào)增保持單調(diào)增保持單調(diào)增 X2X3.Xk Z 2 Z 3 . Z k 當當Zk 中中非基變量非基變量的系數(shù)的系數(shù)全為負值時，這時的的系數(shù)的系數(shù)全為負值時，這時的 基本可行解基本可行解Xk 即是

17、線性規(guī)劃問題的最優(yōu)解，即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。迭代結(jié)束。 第26頁/共68頁 (2) 線性規(guī)劃的典則形式線性規(guī)劃的典則形式 0X bAX t . s CXZMax NBA N B X X X NB CCC 標準型標準型 第27頁/共68頁 bAX b X X NB N B bNXBX NB N 11 B NXBbBX N 1 BN 1- B NNN 1- B 1- B NNN 11 B NNBB N B NB XNBCCbBC XCNXBCbBC XCNXBbBC XCXC X X CCCXZ 第28頁/共68頁 0X,0X bBNXBX t . s XNBCCbBCZMax NB

18、 1 N 1 B N 1 BN 1 B 上式稱為線性規(guī)劃問題對應(yīng)于基上式稱為線性規(guī)劃問題對應(yīng)于基B的的典則形式典則形式，簡稱，簡稱 典式典式。 1.約束方程組的系數(shù)矩陣中含有一個單位矩陣，并以約束方程組的系數(shù)矩陣中含有一個單位矩陣，并以 其為基；其為基； 2.目標函數(shù)中不含基變量，只有非基變量。目標函數(shù)中不含基變量，只有非基變量。 NBCC0 NBCCBBCC NBBCCCABCC 1 BN 1 BN 1 BB 1 BNB 1 B 檢檢 驗驗 數(shù)數(shù) 第29頁/共68頁 (3) 最優(yōu)性判別定理最優(yōu)性判別定理 在線性規(guī)劃問題的典式中，設(shè)在線性規(guī)劃問題的典式中，設(shè) X(0)=(x1,x2,xm,0,

19、0) 為對應(yīng)于基為對應(yīng)于基B 的一個基可行解，若有的一個基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 則則X(0)是線性規(guī)劃問題的是線性規(guī)劃問題的最優(yōu)解最優(yōu)解，基，基B為為最優(yōu)基最優(yōu)基。 證：設(shè)證：設(shè)X為線性規(guī)劃問題的一個可行解，必有為線性規(guī)劃問題的一個可行解，必有 X 0 ，當，當 j 0， 則則 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故故X(0)為線性規(guī)劃問題的最優(yōu)解為線性規(guī)劃問題的最優(yōu)解。 。 第30頁/共68頁 在線性規(guī)劃問題的典式中，設(shè)在線性規(guī)劃問題的典式中，設(shè) X(0)=(x1,x2,xm,0,0) 為對應(yīng)于基為對應(yīng)于基B 的一

20、個基可行解，若有的一個基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 且且 j+k = 0 則則線性規(guī)劃問題有無窮多個最優(yōu)解。線性規(guī)劃問題有無窮多個最優(yōu)解。 無窮多最優(yōu)解判別定理無窮多最優(yōu)解判別定理 在線性規(guī)劃問題的典式中，設(shè)在線性規(guī)劃問題的典式中，設(shè)X(0) 為對應(yīng)于基為對應(yīng)于基B 的一個的一個 基可行解，若某一非基變量基可行解，若某一非基變量xj+k的檢驗數(shù)的檢驗數(shù) j+k 0 且對應(yīng)的列向量且對應(yīng)的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 則則線性規(guī)劃問題具有無界解，即無有限最優(yōu)解。線性規(guī)劃問題具有無界解，即無有限最優(yōu)解。 無界解判別定理

21、無界解判別定理 第31頁/共68頁 (4) 基可行解改進定理基可行解改進定理 在線性規(guī)劃問題的典式中，設(shè)在線性規(guī)劃問題的典式中，設(shè) X(0)=(x1,x2,xm,0,0) 為對應(yīng)于基為對應(yīng)于基B 的一個基可行解，若滿足以下條件：的一個基可行解，若滿足以下條件： 1)某個非基變量的檢驗數(shù)某個非基變量的檢驗數(shù) k 0 ( m+1 k n ); 2)aik ( i = 1,2,m )不全小于或等于零，即至少有一個不全小于或等于零，即至少有一個 aik 0 ( 1 k m ); 3)bi 0( I = 1 , 2,m ),即即X(0)為非退化的基可行解。為非退化的基可行解。 則從則從X(0)出發(fā)，一定

22、能找到一個新的基可行解出發(fā)，一定能找到一個新的基可行解X(1)，使得，使得 CX(1) CX(0) 。 第32頁/共68頁 (5) 單純形表單純形表 將線性規(guī)劃問題典式中將線性規(guī)劃問題典式中各變量及系數(shù)填寫在一張各變量及系數(shù)填寫在一張 表格中表格中，該表即為，該表即為單純形表單純形表。 cj c1 c2 cn cn+1 cn+2 cn+m 解解 CB基基 x1 x2 xn xn+1 xn+2 xn+m 0 0 0 0 xn+1 xn+2 xn+m a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1 b1 b2 bm 1 2 m j = cj zj 1 2 n n

23、+1 n+2 n+m 第33頁/共68頁 0X bAX t . s CXzMax 0X,X,X bIXNXBX t . s 0XXCXCzMax sNB sNB sNNBB bIXNXBX 00XXCXCz- sNB sNNBB bBBNBI0 00CC1 bINB0 00CC1 1-1-1- NBNB bBBNBI0 bBC-BC-NBCC01 1-1-1- -1 B -1 B -1 BN 單單 純純 形形 方方 法法 的的 矩矩 陣陣 表表 示示 0X, 0X bBNXBX t . s XNBCCbBCZMax NB 1 N 1 B N 1 BN 1 B BNIb CBCN00 IB-1N

24、B-1B-1b 0CN -CB B-1N-CB B-1CBB-1b 第34頁/共68頁 對應(yīng)對應(yīng)I 式式的的單純形表單純形表 I 表表(初始單純形表初始單純形表) 對應(yīng)對應(yīng)B 式式的的單純形表單純形表 B 表表 迭迭 代代 IB-1NB-1B-1b 0CN -CB B-1N-CB B-1CBB-1b BNIb CBCN00 價值系數(shù)價值系數(shù)cjCBCN0 解解 基系數(shù)基系數(shù)基基XBXNXS CBXBIB-1NB-1B-1b 檢驗數(shù)檢驗數(shù)j0CN -CB B-1N-CB B-1CBB-1b 當當CN -CBB-1N0時，即為時，即為最優(yōu)單純形表最優(yōu)單純形表 價值系數(shù)價值系數(shù)cjCBCN0 解解

25、基系數(shù)基系數(shù)基基XBXNXS 0XBBNIb 檢驗數(shù)檢驗數(shù)jCBCN00 第35頁/共68頁 (1)、確定初始基域初始基本可行解、確定初始基域初始基本可行解,列出初始單列出初始單 純形表純形表 (3)、若有、若有 j 0，Pj 全全 0，停止，停止， 沒有有限最優(yōu)解；沒有有限最優(yōu)解； 否則轉(zhuǎn)否則轉(zhuǎn) (4) (2)、對應(yīng)于非基變量檢驗數(shù)、對應(yīng)于非基變量檢驗數(shù) j全小于全小于零零。 若是，停止，得到最優(yōu)解；若是，停止，得到最優(yōu)解； 若否，轉(zhuǎn)若否，轉(zhuǎn)(3)。 (6) (6) 單純形法的迭代步驟單純形法的迭代步驟 第36頁/共68頁 = = min aim+k 0 =0 = bi aim+k br a

26、rm+k 定定Xr為出基變量，為出基變量，arm+k為為主元。主元。 由最小由最小比值法求：比值法求： Max j = m+kXm+k 進基變量進基變量 j 0 0 (4)、 第37頁/共68頁 轉(zhuǎn)轉(zhuǎn)(2) (2) a1m+k 0 a2m+k 0 ar,m+k 1 amm+k 0 初等行變換初等行變換 Pm+k = (5)、以、以arm+k為中心，換基迭代為中心，換基迭代 從步驟從步驟(2)-(5)(2)-(5)的每一個循環(huán)，稱為一次的每一個循環(huán)，稱為一次單純形迭代單純形迭代. . 第38頁/共68頁 單純形表計算步驟舉例單純形表計算步驟舉例 給定線性規(guī)劃問題給定線性規(guī)劃問題 例例1 Max

27、z = 50X1 + 30X2 4X1+3X2 120 s.t 2X1+ X2 50 X1，X2 0 Max z = 50X1 + 30X2 4X1+ 3X2 + X3 = 120 s.t 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0 第39頁/共68頁 cj503000 B-1b cBxBx1x2x3x4 0 x34310120120/4 0 x4(2)1015050/2 j5030000 0 x30(1)1-22020 50 x111/201/22550 j050-251250 30 x2011-220 50 x110-1/25/215 j00-5-151350 初

28、始單純形表初始單純形表 最優(yōu)單純形表最優(yōu)單純形表B-1 唯一最優(yōu)解唯一最優(yōu)解 最優(yōu)值最優(yōu)值 第40頁/共68頁 例例2 0 x,x 242x 602x3x 302xx s.t 80 x40 xzMax 21 2 21 21 21 0 x,x 24x2x 60 x2x3x 30 x2xx s.t 80 x40 xzMax 51 52 421 321 21 第41頁/共68頁 cj4080000 B-1b cBxBx1x2x3x4x5 0 x3121003015 0 x4320106030 0 x5020012412 j40800000 cj4080000 B-1b cBxBx1x2x3x4x5

29、0 x31010-166 0 x43001-13612 80 x201001/212 j40000-40960 第42頁/共68頁 cj4080000 B-1b cBxBx1x2x3x4x5 40 x11010-16 0 x400-312189 80 x201001/21224 j00-40001200 cj4080000 B-1b cBxBx1x2x3x4x5 40 x110-1/21/2015 0 x500-3/21/219 80 x2013/4-1/4015/2 j00-40001200 達到最優(yōu)狀態(tài)時，若存在非基變量為零，則為達到最優(yōu)狀態(tài)時，若存在非基變量為零，則為有無窮多最優(yōu)解有無窮

30、多最優(yōu)解 第43頁/共68頁 0 0 5 2 21 21 21 21 x,x xx xx t . s xxZMax 0 0 5 2 41 421 321 21 xx xxx xxx t . s xxZMax 例例3 第44頁/共68頁 cj2100 B-1b cBxBx1x2x3x4 0 x3111055 0 x41-10100 j21000 0 x3021-155/2 2x11-1010 j030-20 1x2011/2-1/25/2 2x1101/21/25/2 j00-3/2-1/215/2 可以為零可以為零 第45頁/共68頁 例例4 0 x,x 2x2x- 8x2x t . s 4x

31、2xzMax 21 21 21 21 0 x,x,x,x 2xx2x- 8xx2x t . s 4x2xzMax 4321 421 321 21 例例5 0 x,x 1xx- t . s 2x3xzMax 21 21 21 0 x,x,x 1xxx- t . s 2x3xzMax 321 321 21 無法獲得初始基無法獲得初始基 和初始基可行解和初始基可行解 第46頁/共68頁 求解線性規(guī)劃問題的單純形法第一步就是要找到一個初求解線性規(guī)劃問題的單純形法第一步就是要找到一個初 始可行基并求出初始基可行解，以它作為迭代的起點。始可行基并求出初始基可行解，以它作為迭代的起點。 獲得初始可行基及初始

32、基可行解的途徑主要有：獲得初始可行基及初始基可行解的途徑主要有： (1) 試算法；試算法； (2) 人工變量法。人工變量法。 在約束方程組中的每一個沒有單位向量的約束方程中人在約束方程組中的每一個沒有單位向量的約束方程中人 為加入一個變量，使系數(shù)矩陣中湊成一個單位方陣，以為加入一個變量，使系數(shù)矩陣中湊成一個單位方陣，以 形成一個初始可行基陣。形成一個初始可行基陣。 第47頁/共68頁 約束條件約束條件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nxn +xn+2 = b2 . . . am1x1 + am2x2 + + amn

33、xn +xn+m = bm x1 ，x2 ， ，xn , xn+1 , , xn+m 0 s.t 0 M M X,X bIXAX t . s 人工變量人工變量 人工基人工基 第48頁/共68頁 0 . X bAX ts CXZMax 0, . M M XX bIXAX ts CXZMax 等價否？等價否？ 0 . X bAX ts CXZMax 0, . M M XX bIXAX ts CXZMax 0 M X 第49頁/共68頁 0X bAX t . s CXzMax 0 M M M X,X bIXAX t . s MXCXzMax 0X bAX t . s CXzMax 0 M M M X

34、,X bIXAX t . s IXzMax 大大M法法 兩階段法兩階段法 第50頁/共68頁 大大M法與二階段法的一些說明法與二階段法的一些說明 n由于人工變量在原問題的解中是不能存在的，應(yīng)盡快由于人工變量在原問題的解中是不能存在的，應(yīng)盡快 被迭代出去，因此人工變量在目標函數(shù)中對應(yīng)的價值被迭代出去，因此人工變量在目標函數(shù)中對應(yīng)的價值 系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。 q大大M法實質(zhì)上與原單純型法一樣，法實質(zhì)上與原單純型法一樣，M可看成一個很可看成一個很 大的常數(shù)大的常數(shù) q人工變量被迭代出去后就不會再成為基變量人工變量被迭代出去后就不會再成為基變量 q當檢驗數(shù)都滿足

35、最優(yōu)條件，但基變量中仍有人工變當檢驗數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變 量，說明原線性規(guī)劃問題無可行解量，說明原線性規(guī)劃問題無可行解 q大大M法手算很不方便，因此提出了二階段法法手算很不方便，因此提出了二階段法 n計算機中常用大計算機中常用大M法法 n二階段法手算可能容易二階段法手算可能容易 第51頁/共68頁 二階段法的求解過程二階段法的求解過程 n第一階段的任務(wù)是將人工變量盡快迭代出去，從而找第一階段的任務(wù)是將人工變量盡快迭代出去，從而找 到一個沒有人工變量的基本可行解到一個沒有人工變量的基本可行解 n第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采第二階段以第一階段得到的基礎(chǔ)可行解為初

36、始解，采 用原單純型法求解用原單純型法求解 n若第一階段結(jié)束時，人工變量仍在基變量中，則原問若第一階段結(jié)束時，人工變量仍在基變量中，則原問 題無（可行）解題無（可行）解 n為了簡化計算，在第一階段重新定義價值系數(shù)如下：為了簡化計算，在第一階段重新定義價值系數(shù)如下： 不是人工變量時當 為人工變量時當 時目標函數(shù)為 不是人工變量時當 為人工變量時當 時目標函數(shù)為 jj jj jj jj xc xc axM xc xc inM 0 1 0 1 第52頁/共68頁 0 321 321 321 321 x,x,x 1x2x 32xx4x 11x2xx t . s xx3xzMax 21 例例6 0 1

37、321 321 321 7 721 65 4 76 x,x 1xx2x 3xx2xx4x 11xx2xx t . s xxMxx3xzMax 大大M法法 第53頁/共68頁 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0 x41-2110001111 -Mx6-4120-11033/2 -Mx7-201000111 j-6M+3M-13M-10-M00-4M cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0 x43-20100-110 -Mx60100-11-211 -1x3-20100011 j1M-100-M0-3M+1 -M-

38、1 第54頁/共68頁 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0 x43001-22-5124 -1x20100-11-21 -1x3-20100011 j1000-1-M+1 -M-1-2 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 3x11001/3-2/32/3-5/34 -1x20100-11-21 -1x30012/3-4/34/3-7/39 j000-1/3-1/3-M+1/3 -M+2/32 最最 優(yōu)優(yōu) 解解 人工變量被迭代出去后就不會再成為基變?nèi)斯ぷ兞勘坏鋈ズ缶筒粫俪蔀榛?量量 第55頁/共68頁 例

39、例4 0 x,x 2x2x- 8x2x t . s 4x2xzMax 21 21 21 21 0 x,x,x,x 2xx2x- 8xx2x t . s 4x2xzMax 4321 421 321 21 0 x,x,x,x 2xx2x- 8xxx2x t . s Mx4x2xzMax 4321 421 5321 521 第56頁/共68頁 cj2400-M B-1b cBxBx1x2x3x4x5 -Mx521-10184 0 x4-210102 j2+2M4+M-M00-8M cj2400-M B-1b cBxBx1x2x3x4x5 2x111/2-1/201/248 0 x402-111105

40、 j0310-M-18 cj2400-M B-1b cBxBx1x2x3x4x5 2x110-1/4-1/41/43/2 4x201-1/21/21/25 j005/2-3/2-M-5/226 未達到最優(yōu)狀態(tài)，但無法繼續(xù)改進，即未達到最優(yōu)狀態(tài)，但無法繼續(xù)改進，即無有限最優(yōu)解無有限最優(yōu)解 第57頁/共68頁 例例5 0 x,x 1xx- t . s 2x3xzMax 21 21 21 0 x,x,x 1xxx- t . s 2x3xzMax 321 321 21 0 x,x,x,x 1xxxx- t . s Mx2x3xzMax 4321 4321 421 cj320-M B-1b cBxBx1

41、x2x3x4 -Mx4-1-1-111 j-M+3-M+2-M0-M 已達到最優(yōu)狀態(tài)，但基變量中的人工變量未退出，故已達到最優(yōu)狀態(tài)，但基變量中的人工變量未退出，故無可行解無可行解 第58頁/共68頁 0 321 321 321 321 x,x,x 1x2x 32xx4x 11x2xx t . s xx3xzMax 21 例例6 0 1 321 321 7 721 65 4 76 x,x 1xx2x 3xx2xx4x 11xx2xx t . s xxzMax (2) 兩階段法兩階段法 第59頁/共68頁 第一階段第一階段 cj00000-1-1 B-1b cBxBx1x2x3x4x5x6x7 0 x41-2110001111 -1x6-4120-11033/2 -1x7-201000111 j-6130-100-4 第60頁/共68頁 cj00000-1-1 B-1b cBxBx