or[第二章]02

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

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

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

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

5、方程組形式的單純形法( (單純形法引例單純形法引例) ) 2513 maxxxz0,36431228212121xxxxxx例：例：解：首先將問題化為解：首先將問題化為標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式：0,36431228515214231xxxxxxxxx2513 maxxxz觀察標(biāo)準(zhǔn)形式，易得初始基本可行解：觀察標(biāo)準(zhǔn)形式，易得初始基本可行解： 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)，改寫標(biāo)準(zhǔn)形式：改寫標(biāo)準(zhǔn)形式： 觀察上述形式觀察上述形式，滿足：滿

6、足： 基本可行解基本可行解X(0)對(duì)應(yīng)的可行基是一個(gè)對(duì)應(yīng)的可行基是一個(gè)m m階排列階排列陣或單位陣；陣或單位陣； 目標(biāo)函數(shù)方程中所有基變量的系數(shù)全部為目標(biāo)函數(shù)方程中所有基變量的系數(shù)全部為0 0。 我們將滿足上述兩個(gè)條件的方程組稱為我們將滿足上述兩個(gè)條件的方程組稱為典式典式( (方方程組典型形式程組典型形式) )，這是單純形法下任何一個(gè)基本可行，這是單純形法下任何一個(gè)基本可行解必須滿足的。一般地將這兩個(gè)條件稱為解必須滿足的。一般地將這兩個(gè)條件稱為條典條典( (典型典型條件條件) )。 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)：目標(biāo)函數(shù)中非基變量是否最優(yōu)：目標(biāo)函數(shù)中非基變量的系數(shù)的系數(shù)( (非基變量的系數(shù)可以作為檢驗(yàn)當(dāng)前基本可非基變量的系數(shù)可以作為檢驗(yàn)當(dāng)前基本可行解是否最優(yōu)的一個(gè)標(biāo)志，稱之為檢驗(yàn)數(shù)行解是否最優(yōu)的一個(gè)標(biāo)志，稱之為檢驗(yàn)數(shù))進(jìn)基進(jìn)基變量變量離基變量。離基變量。 zmax0, 36 43 12 2 8 0 5 351(4)521(3)42(2)31(1)21xxxxxxxxxxxz檢驗(yàn)數(shù)0)36,12,8 ,0,0(0)0(zXT可去掉 因此，因此，在下一個(gè)基本可行解中，若在下一個(gè)基本可行解中，若 043602120825243xxxxx9436621222xx2x

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

9、(初等變換初等變換) ) 典式典式新解新解36 43 12 2 8 0 5 3 52142 31 21xxxxxxxxxz122 3 6 8 30 3541 4212 31 4251xxxxxxxxxz檢驗(yàn)數(shù)檢驗(yàn)數(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檢驗(yàn)數(shù)檢驗(yàn)數(shù) 觀察最后一個(gè)典式，所有檢驗(yàn)數(shù)均為非負(fù)，觀察最后一個(gè)典式，所有檢驗(yàn)數(shù)均為非負(fù)，故其對(duì)應(yīng)的基本可行解為最優(yōu)解，即故其對(duì)應(yīng)的基本可行解為最優(yōu)解，即 說(shuō)明：說(shuō)明：?jiǎn)渭冃畏ǖ膸缀我饬x：相鄰頂點(diǎn)的迭代單純形法的幾何意義：相鄰頂點(diǎn)的迭代( (路徑路徑 統(tǒng)計(jì)規(guī)律統(tǒng)計(jì)規(guī)律) )。 理論上缺陷：每次只換入一個(gè)變量，速度不理論上缺陷：每次只換入一個(gè)變量，速度不 理想理想如何尋求快速算法。如何尋求快速算法。 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求解標(biāo)準(zhǔn)求解標(biāo)準(zhǔn)形式的形式的LP問題，必須解決三個(gè)問題：?jiǎn)栴}，必須解決三個(gè)問題： 初始基本可行解的確定；初始基本可行解的確定； 解的最優(yōu)性檢驗(yàn)；解的最優(yōu)性檢驗(yàn)； 基本可行解的轉(zhuǎn)移規(guī)則?；究尚薪獾霓D(zhuǎn)移規(guī)則。 這里先放一下，研究和，為此，這里先放一下，研究和，為此，先討論一下對(duì)應(yīng)基先討論一下對(duì)應(yīng)基B B的單純形表。的單純形表。 ( (一一) )對(duì)應(yīng)于基對(duì)應(yīng)于基B的單純形表的單純形表 討論單純形表

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

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

14、有：此時(shí)對(duì)應(yīng)于基此時(shí)對(duì)應(yīng)于基B的單純形表為：的單純形表為： bBAXBbBCXCABCzBB1111 ABbBCABCbBCBB1111T(B)單純形表四部分內(nèi)容為：?jiǎn)渭冃伪硭牟糠謨?nèi)容為：目標(biāo)函數(shù)值目標(biāo)函數(shù)值001bbBCB檢驗(yàn)數(shù)檢驗(yàn)數(shù)),(002011nBbbbCABCABbBCABCbBCBB1111T(B)基變量取值基變量取值T020101),(mbbbbB對(duì)應(yīng)基對(duì)應(yīng)基B B的約束系數(shù)矩陣的約束系數(shù)矩陣mnmmnnbbbbbbbbbAB2122221112111因此，對(duì)應(yīng)于基因此，對(duì)應(yīng)于基B B的單純形表可表示如下：的單純形表可表示如下：mnmmmnnnBBbbbbbbbbbbbbbbb

15、bABbBCABCbBC2102222120112111000201001111 T(B) 例：找出下列例：找出下列LPLP問問題的兩個(gè)基，并構(gòu)造相題的兩個(gè)基，并構(gòu)造相應(yīng)的單純形表。應(yīng)的單純形表。0,36 4312 2 8 51521 42 31xxxxxxxxx2153 maxxxz 解：取基解：取基B B如下：如下：103010001,541pppB1030100011B計(jì)算各部分如下：計(jì)算各部分如下：T1)12,12, 8(bBT)36,12, 8(b)0 , 0 , 3(BC241bBCBT541),(xxxXB對(duì)應(yīng)基對(duì)應(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、過(guò)上例可見，當(dāng)取基通過(guò)上例可見，當(dāng)取基B不同時(shí)，構(gòu)造不同時(shí)，構(gòu)造相應(yīng)的單純形表的計(jì)算量是不同的，而當(dāng)基相應(yīng)的單純形表的計(jì)算量是不同的，而當(dāng)基B是單位陣時(shí)，計(jì)算量較小，是單位陣時(shí)，計(jì)算量較小，特別是特別是當(dāng)基當(dāng)基B是由引入的松弛變量對(duì)應(yīng)的列向量構(gòu)成時(shí)，是由引入的松弛變量對(duì)應(yīng)的列向量構(gòu)成時(shí)，其對(duì)應(yīng)的單純形表幾乎就是模型的原始數(shù)據(jù)。其對(duì)應(yīng)的單純形表幾乎就是模型的原始數(shù)據(jù)。這一點(diǎn)為我們后續(xù)介紹的確定這一點(diǎn)為我們后續(xù)介紹的確定初始基本可行初始基本可行解解提供了思路。提供了思路。ABbBCABCbBCBB1111T(B)AbC0T(B)IB1 ( (二二) )最優(yōu)判別定理最優(yōu)判別定理 *XB定理：若定理：

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

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

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

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

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

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

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

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

26、，換入變量替代換出變量替代換出變量) )，返，返3 3。 上述步驟中，上述步驟中，1 1、2 2為預(yù)備步驟或第為預(yù)備步驟或第0 0次迭次迭代，代，3 36 6為迭代步驟。為迭代步驟。rJx確定換出變量確定換出變量。二、二、SM應(yīng)用舉例應(yīng)用舉例 例例1 1：( (說(shuō)明說(shuō)明SMSM的計(jì)算過(guò)程及換的計(jì)算過(guò)程及換入或換出變量不入或換出變量不唯一時(shí)的確定方唯一時(shí)的確定方法法) )32133 maxxxxz0,62253222321321321321xxxxxxxxxxxx解解：(1)(1)首先將問題化首先將問題化 為標(biāo)準(zhǔn)形式：為標(biāo)準(zhǔn)形式：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)觀察上表，因檢驗(yàn)數(shù)中存在小于零觀察上表，因檢驗(yàn)數(shù)中存在小于零的，所以當(dāng)前解不是最優(yōu)解。的，所以當(dāng)前解不是最優(yōu)解。

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

29、10051230106221001654321 xxxxxx654xxxzbXB (6)(6)以主元為中心進(jìn)行初等變換，即可得到新以主元為中心進(jìn)行初等變換，即可得到新的單純形表。的單純形表。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 由于上表中所有檢驗(yàn)數(shù)均已非負(fù)，因此由于上表中所有檢驗(yàn)數(shù)均已非負(fù)，因此得到問題的最優(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 在實(shí)際運(yùn)算過(guò)程中，上述迭代過(guò)程可連續(xù)在實(shí)際運(yùn)算過(guò)程中，上述迭代過(guò)程可連續(xù)進(jìn)行。見下頁(yè)表。進(jìn)行。見下頁(yè)表。

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：( (無(wú)界解的判別無(wú)界解的判別) )2152maxxxz0,8 23 4 51521 4231xxxxxxxxx解：選解：選543,xxx為初始基，易得初始單純形表，并在此基礎(chǔ)上為初始基，易得初始單純形表，并在此基

32、礎(chǔ)上迭迭對(duì)應(yīng)的列向量構(gòu)成的單位陣對(duì)應(yīng)的列向量構(gòu)成的單位陣代求最優(yōu)解的過(guò)程如下表所示：代求最優(yōu)解的過(guò)程如下表所示：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 從上表最后一表可見，對(duì)從上表最后一表可見，對(duì)1 1=-2=-2，它所對(duì)應(yīng)的，它所對(duì)應(yīng)的列向量列向量(-1，0，-1)T0，故目標(biāo)函數(shù)最優(yōu)值無(wú)上界，故目標(biāo)函數(shù)最優(yōu)值無(wú)上界，即問題無(wú)最優(yōu)解。即問題無(wú)最優(yōu)解。 實(shí)質(zhì)上，所謂無(wú)有限最優(yōu)解的判別，直實(shí)質(zhì)上，所謂無(wú)有限最優(yōu)解的判別，直

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

34、0,4 3 8 2515241321xxxxxxxxx212 maxxxz212maxxxz0,4382212121xxxxxx以以543,xxx并在此基礎(chǔ)上迭代求最優(yōu)解的過(guò)程如下表所示：并在此基礎(chǔ)上迭代求最優(yōu)解的過(guò)程如下表所示：為基變量，構(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計(jì)算步驟中曾講過(guò)，若在最優(yōu)表中，某計(jì)算步驟中曾講過(guò)，若在最優(yōu)表中，某個(gè)非基變量的檢驗(yàn)數(shù)為個(gè)非基變量的檢驗(yàn)數(shù)為0，則此時(shí)最優(yōu)解可能不唯，則此時(shí)最優(yōu)解可能不唯一，即可能有多重最優(yōu)解。一，即可能有多重最優(yōu)解。 對(duì)于本例，對(duì)于本例， x x4為非基變量且為非基變量且4 4=0=0，此時(shí)若在，此時(shí)若

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

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

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

39、。 例例4:4:( (說(shuō)明說(shuō)明SM的另一種表格形式的另一種表格形式) ) 0,20 286 -8 51521 421321xxxxxxxxxxx4212 maxxxxz 解解：該模型約束方程組的系數(shù)矩陣中含有一個(gè)該模型約束方程組的系數(shù)矩陣中含有一個(gè)543,xxx初始單純形表初始單純形表( (見下頁(yè)見下頁(yè)) )。三階單位陣，因此可選取三階單位陣，因此可選取為基變量，構(gòu)造為基變量，構(gòu)造 z z行的數(shù)字可通過(guò)下述方法獲得：行的數(shù)字可通過(guò)下述方法獲得：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ù)字還可通過(guò)將目標(biāo)函數(shù)用非基變行的數(shù)字還可通過(guò)將目標(biāo)函數(shù)用非基變量表示后，取系數(shù)的相反數(shù)獲得，即量表示后，取系數(shù)的相反數(shù)獲得，即4212xxxz21212126 )6(2xxxxxxz2146xxx 為了很容易地得到目標(biāo)函數(shù)行或檢驗(yàn)數(shù)行為了很容易地得到目標(biāo)函數(shù)行或檢驗(yàn)數(shù)行的數(shù)，當(dāng)目標(biāo)函數(shù)中含有基變量時(shí)，可采用另的數(shù)，當(dāng)目標(biāo)函數(shù)中含有基變量時(shí)，可采用另一種形式的單純形表。借助表的結(jié)構(gòu)，可直接一種形式的單純形表。借助表的結(jié)構(gòu)，可直接在表上運(yùn)算

41、就可得到目標(biāo)函數(shù)行的所有分量。在表上運(yùn)算就可得到目標(biāo)函數(shù)行的所有分量。 對(duì)于本例：對(duì)于本例：-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)在讓我們回過(guò)頭來(lái)考慮現(xiàn)在讓我們回過(guò)頭來(lái)考慮SMSM的第一階段的第

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

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

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

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

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

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

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

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

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

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

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

53、求解輔助輔助LPLP問題的過(guò)程如下表所示：?jiǎn)栴}的過(guò)程如下表所示：-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è)問題的一個(gè)基本可行解?；究尚薪狻＿@樣我們就可以構(gòu)造這樣我們就可以構(gòu)造原問題的初始單純形表，從而進(jìn)入第二階段求原問題的初始單純形表，從而進(jìn)入第二階段求解。解。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)于單純形法的計(jì)算效率關(guān)于單純形法的計(jì)算效率 許多從事數(shù)學(xué)規(guī)劃研究的人員都曾指出：許多從事數(shù)學(xué)規(guī)劃研究的人員都曾指出：SMSM從理論上看并不是有效的算法。因?yàn)檫@種算從理論上看并不是有效的算法。因?yàn)檫@種算法只是在相鄰基本可行解之間迭代。于是人們法只是在相鄰基本可行解之間迭代。于是人們產(chǎn)生這樣一種想法：要是使產(chǎn)生這樣一種想法：要是使SMSM能同時(shí)考察非相能同時(shí)考察非相鄰的基本可行解，那么達(dá)到最優(yōu)就會(huì)快些。但鄰的基本可行解，那么達(dá)到最優(yōu)就會(huì)快些。但是，對(duì)于單純形法改革的許多方案，在總的計(jì)是，對(duì)于單純形法改革的許多方案，在總的計(jì)算時(shí)間方面并未產(chǎn)生顯著的效果，所以上述的算時(shí)間方面并未產(chǎn)生顯著的

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

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

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

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