or[第二章]02

1、運 籌 學(xué) 課 件目 錄運籌學(xué)概論 第一章 線性規(guī)劃基礎(chǔ)第二章 單純形法 第三章 LP對偶理論第四章 靈敏度分析 第五章 運輸問題第六章 整數(shù)規(guī)劃第七章 動態(tài)規(guī)劃第八章 網(wǎng)絡(luò)分析第二章第二章 單純形法單純形法 (SM-Simplex Method) 19471947年，美國運籌學(xué)家年，美國運籌學(xué)家Dantzig提出，原理是提出，原理是代數(shù)迭代。代數(shù)迭代。 單純形法中的單純形的這個術(shù)語，與該方法單純形法中的單純形的這個術(shù)語，與該方法毫無關(guān)系，它源于求解方法的早期階段所研究的毫無關(guān)系，它源于求解方法的早期階段所研究的一個特殊問題，并延用下來。一個特殊問題，并延用下來。 n維空間的單純形，是指具有維

2、空間的單純形，是指具有(n+1)個頂點的個頂點的多面體，如果各棱長相等，則稱為正規(guī)單純形，多面體，如果各棱長相等，則稱為正規(guī)單純形，如二維空間中的三角形如二維空間中的三角形(正三角形正三角形)三維空間的四三維空間的四面體面體(正四面體正四面體)等等, ,其一般表達式為：其一般表達式為： 0 , 11jnjjxx 如前述如前述, ,當(dāng)當(dāng)m=50,n=100m=50,n=100時，枚舉法要枚時，枚舉法要枚舉舉 100!/(50!)21029 個個50階階50元的線性方程組；與之相比，單元的線性方程組；與之相比，單純形法只需約檢查純形法只需約檢查100個基本可行解，就可個基本可行解，就可得到最優(yōu)解。

3、幾十年的計算實踐表明，單得到最優(yōu)解。幾十年的計算實踐表明，單純形法只需很少的迭代次數(shù)就能得到純形法只需很少的迭代次數(shù)就能得到LP問問題的最優(yōu)解，因此，它不僅成為題的最優(yōu)解，因此，它不僅成為LP的最基的最基本算法之一，而且已成為本算法之一，而且已成為IP和和NLP某些算某些算法的基礎(chǔ)。法的基礎(chǔ)。 本章分以下幾節(jié)介紹本章分以下幾節(jié)介紹 1 SM的基本原理的基本原理 2 SM計算步驟及應(yīng)用舉例計算步驟及應(yīng)用舉例 作業(yè)二： P70 1.7中(2)題 3 初始基本可行解的確定初始基本可行解的確定 4 改進單純形法改進單純形法 作業(yè)三： P70 1.8中(2)題1 SM的基本原理一、單純形法的基本思想一、

4、單純形法的基本思想對于標準形式的LP問題：0 maxXbAXCXz) 1 (X1z*X*z 初始基本可行解初始基本可行解設(shè)想：)0(X0z最優(yōu)解最優(yōu)解 基于上述設(shè)想可以總結(jié)出單純形法的基于上述設(shè)想可以總結(jié)出單純形法的基本思想如下：基本思想如下： 從一個基本可行解出發(fā)迭代到另一個從一個基本可行解出發(fā)迭代到另一個基本可行解，每次迭代使目標函數(shù)值上升，基本可行解，每次迭代使目標函數(shù)值上升，反復(fù)迭代，逐步選優(yōu)，直到目標函數(shù)取得反復(fù)迭代，逐步選優(yōu)，直到目標函數(shù)取得最大值為止。最大值為止。 單純形法的實現(xiàn)形式：單純形法的實現(xiàn)形式： 方程組；方程組； 表格；表格； 矩陣。矩陣。 二、方程組形式的單純形法二、

5、方程組形式的單純形法( (單純形法引例單純形法引例) ) 2513 maxxxz0,36431228212121xxxxxx例：例：解：首先將問題化為解：首先將問題化為標準形式：標準形式：0,36431228515214231xxxxxxxxx2513 maxxxz觀察標準形式，易得初始基本可行解：觀察標準形式，易得初始基本可行解： zmax0, 3643 122 8 05351(4)521(3)42(2)31(1)21xxxxxxxxxxxz0)36,12,8 ,0,0(0)0(zXTAB=(P3，P4，P5)基于基于X(0)，改寫標準形式：改寫標準形式： 觀察上述形式觀察上述形式，滿足：滿

6、足： 基本可行解基本可行解X(0)對應(yīng)的可行基是一個對應(yīng)的可行基是一個m m階排列階排列陣或單位陣；陣或單位陣； 目標函數(shù)方程中所有基變量的系數(shù)全部為目標函數(shù)方程中所有基變量的系數(shù)全部為0 0。 我們將滿足上述兩個條件的方程組稱為我們將滿足上述兩個條件的方程組稱為典式典式( (方方程組典型形式程組典型形式) )，這是單純形法下任何一個基本可行，這是單純形法下任何一個基本可行解必須滿足的。一般地將這兩個條件稱為解必須滿足的。一般地將這兩個條件稱為條典條典( (典型典型條件條件) )。 zmax0, 36 43 12 2 8 0 5 351(4)521(3)42(2)31(1)21xxxxxxxx

7、xxxz 現(xiàn)在分析現(xiàn)在分析X(0)是否最優(yōu)：目標函數(shù)中非基變量是否最優(yōu)：目標函數(shù)中非基變量的系數(shù)的系數(shù)( (非基變量的系數(shù)可以作為檢驗當(dāng)前基本可非基變量的系數(shù)可以作為檢驗當(dāng)前基本可行解是否最優(yōu)的一個標志，稱之為檢驗數(shù)行解是否最優(yōu)的一個標志，稱之為檢驗數(shù))進基進基變量變量離基變量。離基變量。 zmax0, 36 43 12 2 8 0 5 351(4)521(3)42(2)31(1)21xxxxxxxxxxxz檢驗數(shù)0)36,12,8 ,0,0(0)0(zXT可去掉 因此，因此，在下一個基本可行解中，若在下一個基本可行解中，若 043602120825243xxxxx9436621222xx2x

8、1x進基進基，仍為非基變量，則有：仍為非基變量，則有：4x即即, 62x離基離基。對應(yīng)典式為：對應(yīng)典式為：01x62x，由83x04x125x301z得，1223683035414212314251xxxxxxxxxz2/ )12(42xx(將代入后，得)即TX)12,0,8 ,6,0()1( 稱為一次迭代稱為一次迭代( (從圖解法看是相鄰頂點從圖解法看是相鄰頂點的轉(zhuǎn)移的轉(zhuǎn)移) )2513 maxxxz0,36431228212121xxxxxx可行域最優(yōu)解680 x1x2 比較迭代，可將其過程描述為：確定迭代，可將其過程描述為：確定換入變量換入變量確定換出變量確定換出變量主元主元變換變換(

9、(初等變換初等變換) ) 典式典式新解新解36 43 12 2 8 0 5 3 52142 31 21xxxxxxxxxz122 3 6 8 30 3541 4212 31 4251xxxxxxxxxz檢驗數(shù)檢驗數(shù)94/36 62/12 主元化主元化為為1 1，主，主元所在元所在列的其列的其余元素余元素化為化為0 0新典式新典式主元主元繼續(xù)求解：繼續(xù)求解：122 3 6 8 30 3541 4212 31 4251xxxxxxxxxz43/12 81 / 8 主元化主元化為為1 1，主，主元所在元所在列的其列的其余元素余元素化為化為0 0新典式新典式主元主元4 6 4 42 531432 1

10、4212531432 35 421xxxxxxxxxxz檢驗數(shù)檢驗數(shù) 觀察最后一個典式，所有檢驗數(shù)均為非負，觀察最后一個典式，所有檢驗數(shù)均為非負，故其對應(yīng)的基本可行解為最優(yōu)解，即故其對應(yīng)的基本可行解為最優(yōu)解，即 說明：說明：單純形法的幾何意義：相鄰頂點的迭代單純形法的幾何意義：相鄰頂點的迭代( (路徑路徑 統(tǒng)計規(guī)律統(tǒng)計規(guī)律) )。 理論上缺陷：每次只換入一個變量，速度不理論上缺陷：每次只換入一個變量，速度不 理想理想如何尋求快速算法。如何尋求快速算法。 42 0 , 0 , 6 , 6 , 4*T*zX 去掉引入變量，得原問題的最優(yōu)解為：去掉引入變量，得原問題的最優(yōu)解為：42 6 , 4*T*

11、zX 迭代路徑迭代路徑: :最優(yōu)解2513 maxxxz0,36431228212121xxxxxx0 x2可行域68x1三、單純形法原理三、單純形法原理 由由SM思想、引例可見，用思想、引例可見，用SM求解標準求解標準形式的形式的LP問題，必須解決三個問題：問題，必須解決三個問題： 初始基本可行解的確定；初始基本可行解的確定； 解的最優(yōu)性檢驗；解的最優(yōu)性檢驗； 基本可行解的轉(zhuǎn)移規(guī)則?；究尚薪獾霓D(zhuǎn)移規(guī)則。 這里先放一下，研究和，為此，這里先放一下，研究和，為此，先討論一下對應(yīng)基先討論一下對應(yīng)基B B的單純形表。的單純形表。 ( (一一) )對應(yīng)于基對應(yīng)于基B的單純形表的單純形表 討論單純形表

12、結(jié)構(gòu)的目的：最優(yōu)性檢討論單純形表結(jié)構(gòu)的目的：最優(yōu)性檢驗；完成迭代；為以后討論奠定基礎(chǔ)。驗；完成迭代；為以后討論奠定基礎(chǔ)。 對于標準形式的對于標準形式的LPLP問題：問題： 0 maxXbAXCXz 若已知若已知B是其一個可行基，不妨設(shè)是其一個可行基，不妨設(shè)B位于位于A的前的前m列，即列，即mpppB,21對對A、X、C按基按基B進行劃分，得進行劃分，得因此因此 ),(NBA ),(NBCCC NBXXXbNXBXXXNBAXNBNB),(得得 NBNXBbBX11nmmpppN,21上式表明基變量可以用非基變量表示。上式表明基變量可以用非基變量表示。 對于對于z=CX，有，有NNBBNNBBN

13、BNBXCNBCbBCXCXCXXCCCXz11 ),(與上式寫在一起，得與上式寫在一起，得 將將 NBNXBbBX11上式表明目標函數(shù)可以用非基變量表示。上式表明目標函數(shù)可以用非基變量表示。 bBNXBXbBCXCNBCzNBBNNB1111 上述方程組的矩陣形式為上述方程組的矩陣形式為上式的系數(shù)增廣陣稱為上式的系數(shù)增廣陣稱為對應(yīng)于基對應(yīng)于基B的單純形表：的單純形表： bBNXBXbBCXCNBCzNBBNNB1111 bBbBCXXzNBCNBCBNBNB1111 I001NBbBCNBCbBCNBB1111 I 0T(B)如果如果B B不是位于不是位于A A的前的前m m列，則有：列，則

14、有：此時對應(yīng)于基此時對應(yīng)于基B的單純形表為：的單純形表為： bBAXBbBCXCABCzBB1111 ABbBCABCbBCBB1111T(B)單純形表四部分內(nèi)容為：單純形表四部分內(nèi)容為：目標函數(shù)值目標函數(shù)值001bbBCB檢驗數(shù)檢驗數(shù)),(002011nBbbbCABCABbBCABCbBCBB1111T(B)基變量取值基變量取值T020101),(mbbbbB對應(yīng)基對應(yīng)基B B的約束系數(shù)矩陣的約束系數(shù)矩陣mnmmnnbbbbbbbbbAB2122221112111因此，對應(yīng)于基因此，對應(yīng)于基B B的單純形表可表示如下：的單純形表可表示如下：mnmmmnnnBBbbbbbbbbbbbbbbb

15、bABbBCABCbBC2102222120112111000201001111 T(B) 例：找出下列例：找出下列LPLP問問題的兩個基，并構(gòu)造相題的兩個基，并構(gòu)造相應(yīng)的單純形表。應(yīng)的單純形表。0,36 4312 2 8 51521 42 31xxxxxxxxx2153 maxxxz 解：取基解：取基B B如下：如下：103010001,541pppB1030100011B計算各部分如下：計算各部分如下：T1)12,12, 8(bBT)36,12, 8(b)0 , 0 , 3(BC241bBCBT541),(xxxXB對應(yīng)基對應(yīng)基B B的單純形表如下：的單純形表如下：103400102000

16、101100430102000101 1030100011AB0 , 0 , 3 , 5, 00 , 0 , 0 , 5 , 3)0 , 0 , 3 , 0 , 3(1CABCB103401201020120010180035024T(B)54321541xxxxxxxxz 取基取基B B如下：如下：IpppB543,IB1T543),(xxxXBT)36,12, 8(b)0 , 0 , 0(BC)0 , 0 , 0 , 5 , 3(C所以：所以：bbB101bBCBAAB1CCABCB1100433601020120010180005300T(B)54321543xxxxxxxxzAbC 通

17、過上例可見，當(dāng)取基通過上例可見，當(dāng)取基B不同時，構(gòu)造不同時，構(gòu)造相應(yīng)的單純形表的計算量是不同的，而當(dāng)基相應(yīng)的單純形表的計算量是不同的，而當(dāng)基B是單位陣時，計算量較小，是單位陣時，計算量較小，特別是特別是當(dāng)基當(dāng)基B是由引入的松弛變量對應(yīng)的列向量構(gòu)成時，是由引入的松弛變量對應(yīng)的列向量構(gòu)成時，其對應(yīng)的單純形表幾乎就是模型的原始數(shù)據(jù)。其對應(yīng)的單純形表幾乎就是模型的原始數(shù)據(jù)。這一點為我們后續(xù)介紹的確定這一點為我們后續(xù)介紹的確定初始基本可行初始基本可行解解提供了思路。提供了思路。ABbBCABCbBCBB1111T(B)AbC0T(B)IB1 ( (二二) )最優(yōu)判別定理最優(yōu)判別定理 *XB定理：若定理：

18、若是與基是與基對應(yīng)的基本可行解，對應(yīng)的基本可行解，優(yōu)解。優(yōu)解。 并且滿足并且滿足01CABCB*X，則，則是是LPLP問題的最問題的最NNBBBBXCNBCbBCXCABCbBCz)( )(1111根據(jù)根據(jù)時，目標函數(shù)值不能再提高，時，目標函數(shù)值不能再提高，直觀觀察可見，當(dāng)基直觀觀察可見，當(dāng)基B對應(yīng)的對應(yīng)的01CABCB或或01NBCNBC故當(dāng)前的基本可行解就是最優(yōu)解。故當(dāng)前的基本可行解就是最優(yōu)解。通常稱通常稱或或 jnjbczcPBCjjjjjBj, 2 , 1 01mnmmmnnnBBbbbbbbbbbbbbbbbbABbBCABCbBC21022221201121110002010011

19、11T(B) 因此，最優(yōu)判別準則為：若基本可行解對應(yīng)因此，最優(yōu)判別準則為：若基本可行解對應(yīng)的檢驗數(shù)都大于等于零，則相應(yīng)的基本可行解就的檢驗數(shù)都大于等于零，則相應(yīng)的基本可行解就是最優(yōu)解。是最優(yōu)解。 從單純形表上看，所有從單純形表上看，所有b b0j0j00，則對應(yīng)的基本則對應(yīng)的基本可行解就是最優(yōu)解?？尚薪饩褪亲顑?yōu)解。CABCB1為檢驗數(shù)，記為：為檢驗數(shù)，記為： ( (三三) )換基迭代換基迭代( (基于基于T(B)T(B) 根據(jù)最優(yōu)判別準則，當(dāng)判定基根據(jù)最優(yōu)判別準則，當(dāng)判定基B對應(yīng)的對應(yīng)的基本可行解不是最優(yōu)時，就要進行換基迭代，基本可行解不是最優(yōu)時，就要進行換基迭代，尋求一個目標函數(shù)值更大的新的

20、基本可行解，尋求一個目標函數(shù)值更大的新的基本可行解，具體過程如下：具體過程如下：1 1、確定換入變量、確定換入變量。具體方法有兩種：。具體方法有兩種：sx(1)(1)確定確定njbbbjjss, 2 , 1 , 0 min000則與則與sx為換入變量；為換入變量；s對應(yīng)的非基變量對應(yīng)的非基變量(2)(2)確定確定njbjsj, 2 , 1 , 0 min0sx為換入變量；為換入變量；則位于表中第則位于表中第s列的非基變量列的非基變量 上述兩種方法中上述兩種方法中第一種第一種通常在通常在手算手算中采中采用，用，第二種第二種通常在通常在計算機求解計算機求解中采用。中采用。 當(dāng)同時有若干個非基變量可

21、作為換入當(dāng)同時有若干個非基變量可作為換入變量時，可任選其一。變量時，可任選其一。2 2、確定換出變量、確定換出變量。先計算最小比值：。先計算最小比值：rJxmibbbbbisisirsr, 2 , 1 , 0min00rJx為換出變量；為換出變量；則位于表中第則位于表中第r行的基變量行的基變量 若同時有若干個基變量可作為換出變量，可若同時有若干個基變量可作為換出變量，可任選其一。任選其一。 換入變量所在列與換出變量所在行交叉換入變量所在列與換出變量所在行交叉位置的元素，即為主元位置的元素，即為主元 。mnmsmmmrnrsrrrnsnsnsnsJJJJbbbbbbbbbbbbbbbbbbbbb

22、bbbbxxxxxxxxzmr2102102222212011121110000201002121T(B)rsb 從從值確定可知，值確定可知，的值有三種情況：大于的值有三種情況：大于零、等于零或不存在零、等于零或不存在( (當(dāng)當(dāng)bis0,i=1,2,m) )。 可以證明：可以證明：當(dāng)當(dāng)0時，新的基本可行解使時，新的基本可行解使目標函數(shù)值上升；當(dāng)目標函數(shù)值上升；當(dāng)=0時，目標函數(shù)值不變；時，目標函數(shù)值不變；當(dāng)當(dāng)值不存在時，值不存在時，LPLP問題無有限最優(yōu)解。問題無有限最優(yōu)解。 3 3、進行進行(r,s)旋轉(zhuǎn)變換旋轉(zhuǎn)變換 將主元化為將主元化為1，主元所在列的其余元素化，主元所在列的其余元素化為為

23、0。 即可即可確定新的基本可行解對應(yīng)的單純形表。確定新的基本可行解對應(yīng)的單純形表。 變換公式如下式所示：變換公式如下式所示：將主元化為將主元化為1:rsrjisijijbbbbbnjmiri, 2 , 1 , 0 , 2 , 1 , 0,主元所在列的其余元素化為主元所在列的其余元素化為0: :rsrjrjbbbnj, 2 , 1 , 02 SM計算步驟及應(yīng)用舉例計算步驟及應(yīng)用舉例一、計算步驟一、計算步驟( (參見書參見書P P1818P P2121) ) 1 1、把把LPLP問題化成標準形式。問題化成標準形式。 2 2、找到問題的一個基本可行解，并構(gòu)造、找到問題的一個基本可行解，并構(gòu)造初始單純

24、形表。初始單純形表。 3 3、若所有檢驗數(shù)、若所有檢驗數(shù)j j00，就得到一個基就得到一個基本最優(yōu)解；此時若存在某個非基變量的檢驗本最優(yōu)解；此時若存在某個非基變量的檢驗數(shù)為數(shù)為0 0，則最優(yōu)解可能不唯一，一般不再求其，則最優(yōu)解可能不唯一，一般不再求其它的解，停止計算；否則轉(zhuǎn)它的解，停止計算；否則轉(zhuǎn)4 4。 4 4、在所有在所有j j00中，只要有一個中，只要有一個k k00所所對應(yīng)的系數(shù)列向量中各分量均小于等于零，對應(yīng)的系數(shù)列向量中各分量均小于等于零，即即 bik0 , i=1,2, ,m 則該則該LPLP問題無有限最優(yōu)解問題無有限最優(yōu)解( (或無最優(yōu)解或無最優(yōu)解) )，停，停止計算；否則轉(zhuǎn)止

25、計算；否則轉(zhuǎn)5 5。 5 5、按最小檢驗數(shù)規(guī)則、按最小檢驗數(shù)規(guī)則njbbbjjss, 2 , 1 , 0 min000確定換入變量確定換入變量sx；再按最小比值規(guī)則；再按最小比值規(guī)則mibbbbbisisirsr, 2 , 1 , 0min00 一般地，稱換入變量所在列為主一般地，稱換入變量所在列為主( (元元) )列，列，換出變量所在的行為主換出變量所在的行為主( (元元) )行，兩者交叉位行，兩者交叉位置的元素置的元素brs稱為主元。稱為主元。 6 6、以以brs為主元對當(dāng)前表格進行一次換基為主元對當(dāng)前表格進行一次換基運算，得到一個新單純形表運算，得到一個新單純形表( (同時，換入變量同時

26、，換入變量替代換出變量替代換出變量) )，返，返3 3。 上述步驟中，上述步驟中，1 1、2 2為預(yù)備步驟或第為預(yù)備步驟或第0 0次迭次迭代，代，3 36 6為迭代步驟。為迭代步驟。rJx確定換出變量確定換出變量。二、二、SM應(yīng)用舉例應(yīng)用舉例 例例1 1：( (說明說明SMSM的計算過程及換的計算過程及換入或換出變量不入或換出變量不唯一時的確定方唯一時的確定方法法) )32133 maxxxxz0,62253222321321321321xxxxxxxxxxxx解解：(1)(1)首先將問題化首先將問題化 為標準形式：為標準形式：0,6 225 32 2 2616321 53214321xxxx

27、xxxxxxxxxx32133 maxxxxz(2)(2)建立初始單純形表建立初始單純形表654,xxx取初始基取初始基即以即以IpppB),(654為初始基變量，則易得初始基本可行解為初始基變量，則易得初始基本可行解X(0)為為T)0()6 , 5 , 2 , 0 , 0 , 0(X根據(jù)前一節(jié)討論，可得初始單純形表如下根據(jù)前一節(jié)討論，可得初始單純形表如下: :0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB (3) (3)觀察上表，因檢驗數(shù)中存在小于零觀察上表，因檢驗數(shù)中存在小于零的，所以當(dāng)前解不是最優(yōu)解。的，所以當(dāng)前解不是最優(yōu)解。

28、 (4)(4)確定換入變量。因為：確定換入變量。因為：3100033,-1,-3-min 0 minjjssbbb若取若取1x1s則則為換入變量，而其對應(yīng)的為換入變量，而其對應(yīng)的系數(shù)列向量系數(shù)列向量(2(2，1 1，2)2)T T存在正分量；轉(zhuǎn)存在正分量；轉(zhuǎn)(5)(5)。 (5) (5)確定換出變量。計算最小比值：確定換出變量。計算最小比值：111000126,15,22min 3,2, 1 ,0minbbibbbbbisisirsr4, 11JJrr即即主元為主元為b b1111=2=2，在表中用在表中用“ ”“ ”標出。標出。，亦即，亦即4x為換出變量為換出變量0-3-1-30002211

29、10051230106221001654321 xxxxxx654xxxzbXB (6)(6)以主元為中心進行初等變換，即可得到新以主元為中心進行初等變換，即可得到新的單純形表。的單純形表。0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB 654321 xxxxxx651xxxzbXB 0 0 1 1 2121210 1 - 0 4 2125231 0 1 0 1 0 4 0 0 - 0 3 232321 由上表知，新的基本可行解為由上表知，新的基本可行解為3 ,)4, 4, 0 , 0 , 0 , 1 (T)1(zX重復(fù)上述重復(fù)上述

30、(3) (3) (6)(6)得下表：得下表：27/507/506/53/501/511/503/5-1/508/503/51-1/52/504010-101654321 xxxxxx631xxxzbXB 由于上表中所有檢驗數(shù)均已非負，因此由于上表中所有檢驗數(shù)均已非負，因此得到問題的最優(yōu)解：得到問題的最優(yōu)解：527max ,)4,0,0,58,0,51(T*zX 去掉引入變量，得原問題的最優(yōu)解與最去掉引入變量，得原問題的最優(yōu)解與最優(yōu)值為：優(yōu)值為：527max ,)58, 0 ,51(T*zX 在實際運算過程中，上述迭代過程可連續(xù)在實際運算過程中，上述迭代過程可連續(xù)進行。見下頁表。進行。見下頁表。

31、0-3-1-3000221110051230106221001654321 xxxxxx654xxxzbXB 651xxxz0 0 1 1 2121210 1 - 0 4 2125231 0 1 0 1 0 4 0 0 - 0 3 232321 27/507/506/53/501/511/503/5-1/508/503/51-1/52/504010-101631xxxz 例例2 2：( (無界解的判別無界解的判別) )2152maxxxz0,8 23 4 51521 4231xxxxxxxxx解：選解：選543,xxx為初始基，易得初始單純形表，并在此基礎(chǔ)上為初始基，易得初始單純形表，并在此基

32、礎(chǔ)上迭迭對應(yīng)的列向量構(gòu)成的單位陣對應(yīng)的列向量構(gòu)成的單位陣代求最優(yōu)解的過程如下表所示：代求最優(yōu)解的過程如下表所示：0-2-50004-101003010108-1200154321 xxxxx543xxxzbXB 0 0 1 0 1- 4 0 1 0 1 0 3 1 2 0 0 1 2 0 5 0 0 2 15 523xxxz 從上表最后一表可見，對從上表最后一表可見，對1 1=-2=-2，它所對應(yīng)的，它所對應(yīng)的列向量列向量(-1，0，-1)T0，故目標函數(shù)最優(yōu)值無上界，故目標函數(shù)最優(yōu)值無上界，即問題無最優(yōu)解。即問題無最優(yōu)解。 實質(zhì)上，所謂無有限最優(yōu)解的判別，直實質(zhì)上，所謂無有限最優(yōu)解的判別，直

33、觀上看就是對應(yīng)于換入變量，按最小比值法觀上看就是對應(yīng)于換入變量，按最小比值法則找不出一個換出變量，亦即使則找不出一個換出變量，亦即使SM迭代過程迭代過程無法進行。無法進行。 對本例來說，從第一個表中即可看出有對本例來說，從第一個表中即可看出有無界解：如果選取無界解：如果選取1=-2對應(yīng)的變量對應(yīng)的變量x x1為換入為換入變量，此時就找不出換出變量，故可判定問變量，此時就找不出換出變量，故可判定問題無有限最優(yōu)解題無有限最優(yōu)解( (或無最優(yōu)解或無最優(yōu)解) )。 例例3:3:( (說明有多說明有多重最優(yōu)解的情況的重最優(yōu)解的情況的判定判定) ) 解解：首先將問題化首先將問題化 為標準形式：為標準形式：

34、0,4 3 8 2515241321xxxxxxxxx212 maxxxz212maxxxz0,4382212121xxxxxx以以543,xxx并在此基礎(chǔ)上迭代求最優(yōu)解的過程如下表所示：并在此基礎(chǔ)上迭代求最優(yōu)解的過程如下表所示：為基變量，構(gòu)造初始單純形表，為基變量，構(gòu)造初始單純形表，0-2-10008211003 1 001040100154321 xxxxx543xxxzbXB 513xxxz0 1 0 0 1 3 0 2- 1 1 0 2 1 0 0 1 0 4 0 2 0 1 0 6 8001002011-20310010200-121512xxxz 從最優(yōu)表可見，問題的最優(yōu)解與最優(yōu)值

35、為：從最優(yōu)表可見，問題的最優(yōu)解與最優(yōu)值為：8001002011-20310010200-121512xxxz54321 xxxxxbXB 8max ,)2,0,0,2,3(T*zX 去掉引入變量，得原問題的最優(yōu)解與最優(yōu)值為：去掉引入變量，得原問題的最優(yōu)解與最優(yōu)值為：8max ,)2 , 3(T*zX 在在SM計算步驟中曾講過，若在最優(yōu)表中，某計算步驟中曾講過，若在最優(yōu)表中，某個非基變量的檢驗數(shù)為個非基變量的檢驗數(shù)為0，則此時最優(yōu)解可能不唯，則此時最優(yōu)解可能不唯一，即可能有多重最優(yōu)解。一，即可能有多重最優(yōu)解。 對于本例，對于本例， x x4為非基變量且為非基變量且4 4=0=0，此時若在，此時若

36、在最優(yōu)表的基礎(chǔ)上選最優(yōu)表的基礎(chǔ)上選x x4為換入變量，進行單純形法強行為換入變量，進行單純形法強行迭代迭代( (如下表所示如下表所示) ) ，雖不能使目標函數(shù)值增加，但，雖不能使目標函數(shù)值增加，但卻可得到另外一個基本可行解，即：卻可得到另外一個基本可行解，即：8001002011-20310010200-121512xxxz54321 xxxxxbXB 8001004010012101/20-1/2100-1/211/2412xxxz8max ,)0, 1 ,0,4,2(T*zX 由圖解討論易知，在這兩個基本可行解邊線間由圖解討論易知，在這兩個基本可行解邊線間的任意一點也必為最優(yōu)解。若記的任意

37、一點也必為最優(yōu)解。若記T*2)0, 1 ,0,4,2(XT*1)2,0,0,2,3(X則由則由10 ,)1(*2*1*XXX可求出任意一個最優(yōu)解。如令可求出任意一個最優(yōu)解。如令21則可得新的則可得新的最優(yōu)解最優(yōu)解*3X為為T2125*221*121*31 ,0,3,XXX 但是，在單純形表運算過程中，只要找到一個最但是，在單純形表運算過程中，只要找到一個最優(yōu)解就可以停止了。在實際應(yīng)用中，問題若有多重最優(yōu)解就可以停止了。在實際應(yīng)用中，問題若有多重最優(yōu)解可增加決策的選擇機會，做出更加合意的決策。優(yōu)解可增加決策的選擇機會，做出更加合意的決策。 由多重最優(yōu)解的確定過程可知，由多重最優(yōu)解的確定過程可知，

38、若在最若在最優(yōu)表中，某個非基變量的檢驗數(shù)為優(yōu)表中，某個非基變量的檢驗數(shù)為0，相應(yīng)，相應(yīng)的列向量中不存在大于的列向量中不存在大于0的分量，則此時并的分量，則此時并不存在多重最優(yōu)解；換句話說，當(dāng)檢驗數(shù)不存在多重最優(yōu)解；換句話說，當(dāng)檢驗數(shù)為為0的非基變量作為換入變量時，找不到換的非基變量作為換入變量時，找不到換出變量，此時最優(yōu)解仍唯一。出變量，此時最優(yōu)解仍唯一。 綜上，可以給出綜上，可以給出多重最優(yōu)解的判別條多重最優(yōu)解的判別條件件是：是： 在最優(yōu)表中至少有一個非基變量的檢在最優(yōu)表中至少有一個非基變量的檢驗數(shù)為驗數(shù)為0，且其對應(yīng)的列向量中至少有一個，且其對應(yīng)的列向量中至少有一個大于大于0的分量。的分量

39、。 例例4:4:( (說明說明SM的另一種表格形式的另一種表格形式) ) 0,20 286 -8 51521 421321xxxxxxxxxxx4212 maxxxxz 解解：該模型約束方程組的系數(shù)矩陣中含有一個該模型約束方程組的系數(shù)矩陣中含有一個543,xxx初始單純形表初始單純形表( (見下頁見下頁) )。三階單位陣，因此可選取三階單位陣，因此可選取為基變量，構(gòu)造為基變量，構(gòu)造 z z行的數(shù)字可通過下述方法獲得：行的數(shù)字可通過下述方法獲得：6120008111006-110102082001543xxxz54321 xxxxxbXB 62068)0 , 1 , 0(1IbBCzB)0 ,

40、0 , 0 , 2 , 1 ( )0 , 1 , 0 , 1, 2()0 , 1 , 0 , 1 , 1( )0 , 1 , 0(1CACABCB z z行的數(shù)字還可通過將目標函數(shù)用非基變行的數(shù)字還可通過將目標函數(shù)用非基變量表示后，取系數(shù)的相反數(shù)獲得，即量表示后，取系數(shù)的相反數(shù)獲得，即4212xxxz21212126 )6(2xxxxxxz2146xxx 為了很容易地得到目標函數(shù)行或檢驗數(shù)行為了很容易地得到目標函數(shù)行或檢驗數(shù)行的數(shù)，當(dāng)目標函數(shù)中含有基變量時，可采用另的數(shù)，當(dāng)目標函數(shù)中含有基變量時，可采用另一種形式的單純形表。借助表的結(jié)構(gòu)，可直接一種形式的單純形表。借助表的結(jié)構(gòu)，可直接在表上運算

41、就可得到目標函數(shù)行的所有分量。在表上運算就可得到目標函數(shù)行的所有分量。 對于本例：對于本例：-2-1010612000081110016-1101002082001jc543xxxz54321 xxxxxbXB BC 檢查問題的初始單純檢查問題的初始單純形表，易知已得問題的最形表，易知已得問題的最優(yōu)解，其最優(yōu)解和最優(yōu)值優(yōu)解，其最優(yōu)解和最優(yōu)值分別為：分別為：jpB1jjBjcpBC1T*)20,6 ,8 ,0 ,0(X6maxz作業(yè)二 P P7070 1.7 1.7中中(2)(2)題題3 初始基本可行解的確定初始基本可行解的確定 現(xiàn)在讓我們回過頭來考慮現(xiàn)在讓我們回過頭來考慮SMSM的第一階段的第

42、一階段問題，即如何求得第一個基本可行解。問題，即如何求得第一個基本可行解。 在前面的討論中，我們都假定約束方程在前面的討論中，我們都假定約束方程組的系數(shù)矩陣中含有一個組的系數(shù)矩陣中含有一個m階單位或存在一階單位或存在一個可行基，所以一開始就很容易地得到初始個可行基，所以一開始就很容易地得到初始基本可行解。但是，在許多問題中，往往不基本可行解。但是，在許多問題中，往往不存在現(xiàn)行的可行基。而且當(dāng)問題規(guī)模較大時，存在現(xiàn)行的可行基。而且當(dāng)問題規(guī)模較大時，判斷判斷m階矩陣是否滿秩的計算量都是很大的。階矩陣是否滿秩的計算量都是很大的。那么如何才能快速得到一個可行基，使算法那么如何才能快速得到一個可行基，使

43、算法的迅速進入迭代過程呢？的迅速進入迭代過程呢？ 方法是通過引入方法是通過引入人工人工(造造)變量變量，即在，即在 原原問題的約束方程中加入人工變量形成一個可問題的約束方程中加入人工變量形成一個可作為基的單位陣，這樣的單位陣稱為人造基。作為基的單位陣，這樣的單位陣稱為人造基。 一般地，當(dāng)給定的一般地，當(dāng)給定的LPLP問題約束方程組的問題約束方程組的系數(shù)矩陣中不含有可作為基的單位陣時，則系數(shù)矩陣中不含有可作為基的單位陣時，則為每一個為每一個( (或部分或部分) )約束方程引入一個人工變約束方程引入一個人工變量，從而較容易地得到一個初始基本可行解。量，從而較容易地得到一個初始基本可行解。0jjij

44、ijxbxa0,injjiinjijxxbxxa 于是在新的約束方程組的系數(shù)矩陣中便得到一于是在新的約束方程組的系數(shù)矩陣中便得到一個個m階單位陣，以階單位陣，以mnnxx,1為基變量，易得為基變量，易得新約束條件下的一個基本可行解：新約束條件下的一個基本可行解：T21)0(), 0 , 0 , 0(mbbbX 因為人工變量是強行加入原約束方程組中的虛因為人工變量是強行加入原約束方程組中的虛擬變量，它可能破壞約束條件的等式關(guān)系，影響所擬變量，它可能破壞約束條件的等式關(guān)系，影響所求求LPLP問題的解。為此，需要對目標函數(shù)進行相應(yīng)的問題的解。為此，需要對目標函數(shù)進行相應(yīng)的修改，并構(gòu)造一個新的修改，并

45、構(gòu)造一個新的LP問題，通過求解新問題，問題，通過求解新問題，來獲得原問題的最優(yōu)解。根據(jù)對目標函數(shù)處理方法來獲得原問題的最優(yōu)解。根據(jù)對目標函數(shù)處理方法的不同，形成了不同的解決問題的方法，常用的有的不同，形成了不同的解決問題的方法，常用的有大大M法和兩階段法法和兩階段法實質(zhì)上都是實質(zhì)上都是SM的變形。的變形。 本部分內(nèi)容，我們主要介紹本部分內(nèi)容，我們主要介紹兩階段法兩階段法。兩階段法兩階段法 一、兩階段法原理一、兩階段法原理01jnjijijxbxanjjjxcz1max對于標準形式的對于標準形式的LPLP問題：問題：miiyw1max0,1ijnjiijijyxbyxa構(gòu)造輔助構(gòu)造輔助LPLP問

46、題：問題： 對于輔助對于輔助LPLP問題，顯然存在基本可行解，問題，顯然存在基本可行解，且對應(yīng)的單純形表易于構(gòu)造，如下表所示：且對應(yīng)的單純形表易于構(gòu)造，如下表所示：miib10 0 111miinmiiaambbb2112111maaamnnnaaa21001100mnyyxx 11myyy21bXB w 觀察輔助觀察輔助LP問題，易知它一問題，易知它一定有最優(yōu)解，且定有最優(yōu)解，且0maxwmiiyw1max0,1ijnjiijijyxbyxa輔助輔助LP問題：問題： 下面我們看一看輔助下面我們看一看輔助LP問題與原問題與原LP問題解之問題解之間的關(guān)系。間的關(guān)系。結(jié)論結(jié)論1 1：若：若 0ma

47、xw，則原問題無可行解。，則原問題無可行解。( (此結(jié)論用反證法易證此結(jié)論用反證法易證) ) 結(jié)論結(jié)論2 2：原問原問題有可行解的充題有可行解的充要條件是要條件是 0maxwmiiyw1max0,1ijnjiijijyxbyxa輔助輔助LP問題：問題： 綜上，兩階段法的過綜上，兩階段法的過程是：程是： 第一階段：第一階段：求解輔助求解輔助LP問題。問題。若若 0maxw，則原問題無可行解。，則原問題無可行解。若若 ，則得原問題一個基本可行解。，則得原問題一個基本可行解。0maxw第二階段：第二階段：求解原問題。求解原問題。 二、兩階段法基本步驟二、兩階段法基本步驟 對于一般的對于一般的LP問題

48、問題( (標準形式標準形式) )而言，兩階段法而言，兩階段法通過引入人工變量將問題的求解分為兩個階段。通過引入人工變量將問題的求解分為兩個階段。 階段階段：求解輔助求解輔助LP問題。判明原問題是否存問題。判明原問題是否存在可行解，若存在就找出一個初始基本可行解。在可行解，若存在就找出一個初始基本可行解。 用用SM求解輔助求解輔助LP問題，最終單純形表可能出現(xiàn)問題，最終單純形表可能出現(xiàn)以下幾種情況：以下幾種情況：(1)(1)若若 0maxw，則原問題無可行解，停止計算。，則原問題無可行解，停止計算。(2)(2)若若 ，且人工變量都不是基變量，則，且人工變量都不是基變量，則得得0maxw原問題一個

49、基本可行解。轉(zhuǎn)入階段原問題一個基本可行解。轉(zhuǎn)入階段求解原問題。求解原問題。 階段階段：求解原問題。求解原問題。 首先首先，建立原問題的初始單純形表。只需把，建立原問題的初始單純形表。只需把階段階段的最終單純形表修改如下：的最終單純形表修改如下：(3)(3)若若 ，但最優(yōu)基變量中存在人工變量，但最優(yōu)基變量中存在人工變量，0maxw且相應(yīng)行中原始變量對應(yīng)的系數(shù)全部為且相應(yīng)行中原始變量對應(yīng)的系數(shù)全部為0 0，則說明，則說明原問題的該約束方程是多余的，此時刪去相應(yīng)行，原問題的該約束方程是多余的，此時刪去相應(yīng)行，并轉(zhuǎn)入階段并轉(zhuǎn)入階段求解原問題。求解原問題。(4)(4)若若 ，且人工變量存在最優(yōu)基變量中，

50、且人工變量存在最優(yōu)基變量中，0maxw但相應(yīng)行中原始變量對應(yīng)的系數(shù)不全部為但相應(yīng)行中原始變量對應(yīng)的系數(shù)不全部為0 0，此時，此時以非零系數(shù)其中之一為主元進行一次換基迭代，從以非零系數(shù)其中之一為主元進行一次換基迭代，從而使人工變量變?yōu)榉腔兞?，并轉(zhuǎn)入階段而使人工變量變?yōu)榉腔兞?，并轉(zhuǎn)入階段求解原求解原問題。問題。 (1)(1)刪去人工變量諸列；刪去人工變量諸列； (2) (2)采用第二種形式的單純形表，把采用第二種形式的單純形表，把c cj j行與行與C CB B列的數(shù)字添上；列的數(shù)字添上； (3) (3)用用z z替代替代w w，并計算原問題相應(yīng)基本可行解，并計算原問題相應(yīng)基本可行解的目標函數(shù)

51、值和檢驗數(shù)；的目標函數(shù)值和檢驗數(shù)； 這樣就得到原問題的初始單純形表。這樣就得到原問題的初始單純形表。 然后然后，進行單純形法迭代，直到運算結(jié)束。，進行單純形法迭代，直到運算結(jié)束。此過程中，可判定問題有此過程中，可判定問題有無界解無界解或有或有多重最優(yōu)解多重最優(yōu)解。 下面舉例說明兩階段法的應(yīng)用。下面舉例說明兩階段法的應(yīng)用。三、三、兩階段法兩階段法應(yīng)用舉例應(yīng)用舉例313 maxxxz0,93 124 32132321321xxxxxxxxxxx解解：(1)(1)首先將問題化首先將問題化 為標準形式：為標準形式：0,9 3 1 2-4 5132 5321 4321xxxxxxxxxxxx313 ma

52、xxxz例例：用單純形法求解下用單純形法求解下列問題：列問題： (2)(2)構(gòu)造輔助構(gòu)造輔助LPLP問題，并求其最優(yōu)解：問題，并求其最優(yōu)解： 觀察該問題的約束系數(shù)矩陣，并不存在可作觀察該問題的約束系數(shù)矩陣，并不存在可作為基的單位陣，因此需引入人工變量構(gòu)造輔助為基的單位陣，因此需引入人工變量構(gòu)造輔助LP問題。但構(gòu)造輔助問題。但構(gòu)造輔助LPLP問題時，并不需要每個約束問題時，并不需要每個約束方程均需引入人工變量。因此，可構(gòu)造如下輔助方程均需引入人工變量。因此，可構(gòu)造如下輔助LPLP問題：問題：0,9 3 1 2-4 7173265321 4321xxxxxxxxxxxxxx76 maxxxw 求解

53、求解輔助輔助LPLP問題的過程如下表所示：問題的過程如下表所示：-102-400100411110001 1-2-2 1 1 -1-10 0-1-11 10 09 90 03 31 10 00 00 01 17654321 xxxxxxx764xxxwbXB 初始表初始表0000001100001-1/21/2-1/23 30 01 11/31/30 00 00 01/31/31 11 10 02/32/30 01/21/2-1/21/61/67654321 xxxxxxx124xxxwbXB 最優(yōu)表最優(yōu)表 由輔助由輔助LPLP問題最優(yōu)表可見，其最優(yōu)值為問題最優(yōu)表可見，其最優(yōu)值為0 0，且最優(yōu)

54、基變量中不含有人工變量，因此得到原且最優(yōu)基變量中不含有人工變量，因此得到原問題的一個問題的一個基本可行解?；究尚薪?。這樣我們就可以構(gòu)造這樣我們就可以構(gòu)造原問題的初始單純形表，從而進入第二階段求原問題的初始單純形表，從而進入第二階段求解。解。0000001100001-1/21/2-1/23011/30001/31102/301/2-1/21/67654321 xxxxxxx124xxxwbXB (3)(3)構(gòu)造原問題的初始單純形表，并求其最優(yōu)構(gòu)造原問題的初始單純形表，并求其最優(yōu)解。如下表所示：解。如下表所示：-30100-300-30-3/2000001-1/203011/300-31102

55、/301/254321 xxxxx124xxxzbXB jcBC3/29/20003/4000001-1/205/2-1/2100-1/4-33/23/20103/4324xxxzBC 根據(jù)上表，得原問題的最優(yōu)解與最優(yōu)值為：根據(jù)上表，得原問題的最優(yōu)解與最優(yōu)值為：-301003/29/20003/4000001-1/205/2-1/2100-1/413/23/20103/454321 xxxxxbXB jcBC324xxxz 去掉引入變量，得原始問題的最優(yōu)解與最優(yōu)值為：去掉引入變量，得原始問題的最優(yōu)解與最優(yōu)值為：23T2325*max ,)0 , 0 , 0(zX23T2325*max ,),

56、0(zX 關(guān)于單純形法的計算效率關(guān)于單純形法的計算效率 許多從事數(shù)學(xué)規(guī)劃研究的人員都曾指出：許多從事數(shù)學(xué)規(guī)劃研究的人員都曾指出：SMSM從理論上看并不是有效的算法。因為這種算從理論上看并不是有效的算法。因為這種算法只是在相鄰基本可行解之間迭代。于是人們法只是在相鄰基本可行解之間迭代。于是人們產(chǎn)生這樣一種想法：要是使產(chǎn)生這樣一種想法：要是使SMSM能同時考察非相能同時考察非相鄰的基本可行解，那么達到最優(yōu)就會快些。但鄰的基本可行解，那么達到最優(yōu)就會快些。但是，對于單純形法改革的許多方案，在總的計是，對于單純形法改革的許多方案，在總的計算時間方面并未產(chǎn)生顯著的效果，所以上述的算時間方面并未產(chǎn)生顯著的

57、效果，所以上述的單純形法仍被認為是求解單純形法仍被認為是求解LPLP的最好方法。的最好方法。 SMSM的計算效率依賴于：的計算效率依賴于：(1)(1)達到最優(yōu)解前的達到最優(yōu)解前的迭代次數(shù)；迭代次數(shù)；(2)(2)解決問題總的計算時間。解決問題總的計算時間。 計算數(shù)以千計的計算數(shù)以千計的LP實際問題積累的實踐經(jīng)實際問題積累的實踐經(jīng)驗表明，具有驗表明，具有m個約束條件和個約束條件和n n個變量的標準形個變量的標準形式的式的LP問題的迭代次數(shù)介于問題的迭代次數(shù)介于m與與3m之間，平均之間，平均為為2m。迭代次數(shù)的實際上限是迭代次數(shù)的實際上限是2(m+n)。 總的計算時間大約與約束條件個數(shù)的立方總的計算

58、時間大約與約束條件個數(shù)的立方(m3)成正比。即若問題成正比。即若問題的約束條件個數(shù)是問的約束條件個數(shù)是問題題的的2倍，則問題倍，則問題的計算時間大約是問題的計算時間大約是問題的的8倍。倍。 由此可見，由此可見，SMSM的計算效率對約束條件個數(shù)的的計算效率對約束條件個數(shù)的變化比對于變量個數(shù)的變化更為敏感。因此，變化比對于變量個數(shù)的變化更為敏感。因此，在解決實際問題時，應(yīng)盡是避免多余的約束條在解決實際問題時，應(yīng)盡是避免多余的約束條件，使約束條件個數(shù)盡可能地少。件，使約束條件個數(shù)盡可能地少。4 改進單純形法改進單純形法 雖然雖然SM的表格算法是求解的表格算法是求解LPLP問題行之有問題行之有效的算法

59、。但在計算過程中，每次迭代必須效的算法。但在計算過程中，每次迭代必須對所有的列進行運算。而實際上必不可少的對所有的列進行運算。而實際上必不可少的運算只有下列幾項：運算只有下列幾項： 1 1、計算相應(yīng)于基本可行解的非基變量的、計算相應(yīng)于基本可行解的非基變量的檢驗數(shù)。檢驗數(shù)?；蚧?jnjbczcPBCjjjjjBj, 2 , 1 01njbbbjjss, 2 , 1 , 0 min000或或 njbjsj, 2 , 1 , 0 min0。此時用到。此時用到3 3、確定換出變量、確定換出變量rJx，及其所對應(yīng)的列，及其所對應(yīng)的列向量向量rJpspB1。4 4、將基變換的運算施于、將基變換的運算施于這

60、需要確定新的基這需要確定新的基sp及及b等；等；B的逆陣的逆陣1B。2 2、確定換入變量、確定換入變量sx，及其所對應(yīng)的列，及其所對應(yīng)的列向量向量sp。 改進改進SM就是針對這些在每次迭代中必不可就是針對這些在每次迭代中必不可少的運算進行的，從而大大地提高了計算效率，少的運算進行的，從而大大地提高了計算效率，而且節(jié)省計算機的存貯空間和節(jié)約計算時間，并而且節(jié)省計算機的存貯空間和節(jié)約計算時間，并可在中、小型計算機上求解一些大型的可在中、小型計算機上求解一些大型的LP問題。問題。B為了完成為了完成1 1、2 2、3 3，必須計算出當(dāng)前可行基，必須計算出當(dāng)前可行基的逆陣的逆陣1B。如果每次迭代都重新計