【正文】 +x3163。18 x1+x2+x3163。24 x1x2x3≥0目標(biāo)函數(shù)轉(zhuǎn)化為極小化，引進(jìn)松弛變量，使約束條件轉(zhuǎn)變?yōu)榈仁剑簃inz’=x12x2x3 .x1+x2+x3+x3=12 2x1+3x2+x3+x4=18 x1+x2+x3+x5=24 x1x2x3x4x5x6≥0列出單純形表zx1x2x3x4x5x6RHSz11210000x401111001212/1x502[3]10101818/3x601110012424/1x2進(jìn)基，x5離基z’x1x2x3x4x5x6RHSz’11/301/302/3012x401/30[2/3]11/3066/2/3x202/311/301/3066/1/3x605/302/301/311818/2/3x3進(jìn)基，x4離基z’x1x2x3x4x5x6RHSz’11/2001/21/2015x301/2013/21/209x201/2101/21/203x6020010112最優(yōu)解為x1=0，x2=3，x3=9，x4=0，x5=0，x6=12，min z’=15，max z=15167。 初始基礎(chǔ)可行解—兩階段法在以上單純形算法描述中，沒有指明如何取得一個(gè)初始基礎(chǔ)可行解。對(duì)于簡單的問題，只要做一些試算就可以確定選定的一個(gè)基是否是可行基。但對(duì)于規(guī)模稍大的問題，用試算的方法就很困難了，必須有一個(gè)初始可行基的系統(tǒng)化方法。當(dāng)用系統(tǒng)的初始可行解方法不能求得任何初始基礎(chǔ)可行解時(shí)，就可以得出線性規(guī)劃問題無解的結(jié)論。對(duì)于標(biāo)準(zhǔn)形式的問題 min z=CTX . AX=b X≥0當(dāng)b179。0時(shí)，如果矩陣A中包含一個(gè)單位矩陣，則很自然地取該單位矩陣作為初始可行基，這時(shí)基變量XB=B1b≥0，因而必定是初始可行基。在以上的例子中，問題的約束條件全為“小于等于”約束，并且右邊常數(shù)全部大于等于0，對(duì)于這一類問題，化為標(biāo)準(zhǔn)問題時(shí)在每個(gè)約束中添加的松弛變量恰構(gòu)成一個(gè)單位矩陣，這個(gè)單位矩陣就可以作為初始可行基。當(dāng)標(biāo)準(zhǔn)形式問題的A矩陣中不含有單位矩陣或雖含有單位矩陣但b不全為非負(fù)時(shí)，無法獲得一個(gè)初始的可行基。 設(shè)一線性規(guī)劃問題的約束為x1+x2+x3≤62x1+3x2+2x3≥3x1,x2,x3≥0引進(jìn)松弛變量xx5≥0，得到x1+x2+x3+x4=62x1+3x2+2x3x5=3x1,x2,x3,x4,x5≥0基中不包含單位矩陣，因此無法直接獲得初始可行基。 設(shè)一線性規(guī)劃問題的約束為x1+x22x3≤32x1+x2+3x3≤7x1,x2,x3≥0引進(jìn)松弛變量xx5179。0，得到x1+x22x3+x4=32x1+x2+3x3+x5=7x1,x2,x3,x4,x5≥0其中雖然含有單位矩陣，但右邊常數(shù)中出現(xiàn)負(fù)值，因此也不能直接獲得初始可行基。對(duì)于不能直接獲得初始可行基的問題，可以用引進(jìn)人工變量（Artificial Variables）的方法構(gòu)造一個(gè)人工基作為初始可行基。設(shè)問題的約束條件為： AX=b X≥0 ()其中X=(x1,x2,…,xn)T。引進(jìn)人工變量Xa=(xn+1,xn+2,…,xn+m)T，約束()成為 AX+Xa=b X,Xa≥0 ()或?qū)憺? ()這樣，()的約束中就出現(xiàn)了一個(gè)單位矩陣，因而()有一個(gè)基礎(chǔ)可行解X=0，Xa=b。但X=0并不是()的可行解，即()和()并不等價(jià)。()的基礎(chǔ)可行解(X, Xa)T中的X要滿足()，當(dāng)且僅當(dāng)()的基全部包含在A矩陣中，即Xa=0全部成為非基變量。為了得到()的一個(gè)可行基，可以對(duì)()的初始可行基（人工基）進(jìn)行基變換，設(shè)法迫使人工基中的列向量離基，最終獲得全部包含在A矩陣中的一個(gè)基，從而也就獲得了()的一個(gè)可行基。根據(jù)以上思路，我們構(gòu)造以下的兩階段法：設(shè)線性規(guī)劃問題為 min z=CTX . AX=b () X≥0第一階段：引進(jìn)人工變量Xa=(xn+1，xn+2，…，xn+m)T，構(gòu)造輔助問題 ()求解輔助問題。若輔助問題的最優(yōu)基B全部在A中，即Xa全部是非基變量（min z’=0），則B為()的一個(gè)可行基。轉(zhuǎn)第二階段。若輔助問題的最優(yōu)目標(biāo)函數(shù)值min z’0，則至少有一個(gè)人工變量留在第一階段問題最優(yōu)解的基變量中，這時(shí)()無可行解（證明見167。）。第二階段：以第一階段()的最優(yōu)基B作為()的初始可行基，求解()，得到()的最優(yōu)基和最優(yōu)解。 求解以下線性規(guī)劃問題minz=x12x2.x1+x2≥2x1+x2≥1x2≤3x1,x2≥0引進(jìn)松弛變量x3，x4，x5179。0，得到minz=x12x2.x1+x2x3=2x1+x2x4=1x2+x5=3x1,x2x3,X4,x5≥0增加人工變量x6，x7≥0，構(gòu)造輔助問題，并進(jìn)入第一階段求解。minz’=x6+x7.x1+x2x3+x6=2x1+x2x4+x7=1x2+x5=3x1,x2，x3,x4,x5x6,x7≥0寫出輔助問題的系數(shù)矩陣表：z’x1x2x3x4x5x6x7RHSz’100000110x6011100102x7011010011x5001001003消去目標(biāo)函數(shù)中基變量xx7的系數(shù)，得到初始單純形表并進(jìn)行單純形變換：z’x1x2x3x4x5x6x7RHSz’102110003x60111001022/1x701[1]0100111/1x50010010033/1x2進(jìn)基，x7離基z’x1x2x3x4x5x6x7RHSz’120110021x60[2]01101111/2x2011010011x50100111122/1x1進(jìn)基，x6離基z’x1x2x3x4x5x6x7RHSz’100000110x10101/21/201/21/21/2x20011/21/201/21/23/2x50001/21/211/21/23/2至此，已獲得第一階段最優(yōu)解，z’=0，人工變量xx7均已離基，最優(yōu)基B=[a1，a2，a5]，因而可以轉(zhuǎn)入第二階段。在第一階段最優(yōu)單純形表換入原問題的目標(biāo)函數(shù)，去掉人工變量xx7以及相應(yīng)的列，得到第二階段的系數(shù)矩陣表：zx1x2x3x4x5RHSz1120000x10101/21/201/2x20011/21/203/2x50001/21/213/2消去基變量xx2在目標(biāo)函數(shù)中的系數(shù)，得到第二階段問題的單純形表：zx1x2x3x4x5RHSz1001/23/205/2x10101/2[1/2]01/21/2/1/2x20011/21/203/2x50001/21/213/23/2/1/2x4進(jìn)基，x1離基，得到：zx1x2x3x4x5RHSz1302004X40201101X20111002X501010111/1x3進(jìn)基，x5離基，得到：zx1x2x3x4x5RHSz1100026X40100112X20010013X30101011OABCD012123x1x2圖 原問題的最優(yōu)解為X=(x1,x2,x3,x4,x5)T=(0,3,1,2,0)T，min z=6。這個(gè)問題求解的兩個(gè)階段前后經(jīng)歷5個(gè)基O，A，B，C，D，經(jīng)過4次基變換O174。A，A174。B，B174。C，C174。D，基疊代經(jīng)過的路線如上圖所示。其中前兩次疊代O174。A，A174。B是在第一階段中完成的，后兩次疊代B174。C，C174。D是在第二階段中完成的。從上圖可以看出，第一階段是在原問題的可行域外部進(jìn)行基變換，第一階段結(jié)束后進(jìn)入可行域，第二階段則是從可行域內(nèi)部的的一個(gè)極點(diǎn)B（原問題的一個(gè)可行基）開始，在可行域內(nèi)部進(jìn)行基變換。第一章 線性規(guī)劃167。 退化和循環(huán) 退化的基礎(chǔ)可行解 設(shè)B是線性規(guī)劃的一個(gè)可行基， XB=B1b=(xB1,xB2,…,xBi,…,xBm)T是這個(gè)基礎(chǔ)解中的基變量。如果其中至少有一個(gè)分量xBi=0(i=1,2,…,m)，則稱此基礎(chǔ)可行解是退化的。 對(duì)于以下的線性規(guī)劃問題minz=2x1x2.x1+x2≤6x2≤3x1+2x2≤9x1,x2≥0引進(jìn)松弛變量x3，x4，x5≥0，得到minz=2x1x2.x1+x2+x3=6x2+x4=3x1+2x2+x5=9x1,x2,x3,x4,x5≥0其中 對(duì)于基 是一退化的基礎(chǔ)可行解，即 X1=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T。同樣，對(duì)于基 B2=[a1，a2，a4]相應(yīng)的基礎(chǔ)可行解為 即 X2=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T再看基 B3=[a1，a2，a5]相應(yīng)的基礎(chǔ)可行解為 即 X3=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T由此可見，以上三個(gè)不同的基對(duì)應(yīng)于可行域中同一個(gè)極點(diǎn)，退化的極點(diǎn)是由若干個(gè)不同的極點(diǎn)在特殊情況下合并成一個(gè)極點(diǎn)（圖中的極點(diǎn)B）而形成的。OABC069312457836退化的結(jié)構(gòu)對(duì)單純形疊代會(huì)有不利的影響。當(dāng)疊代進(jìn)入一個(gè)退化極點(diǎn)時(shí)，可能出現(xiàn)以下情況：進(jìn)行進(jìn)基、離基變換后，雖然改變了基，但沒有改變極點(diǎn)，目標(biāo)函數(shù)當(dāng)然也不會(huì)改進(jìn)。進(jìn)行若干次基變換后，才脫離退化極點(diǎn)，進(jìn)入其他極點(diǎn)。這種情況會(huì)增加疊代次數(shù)，使單純形法收斂的速度減慢。在十分特殊的情況下，退化會(huì)出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形疊代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無法求得最優(yōu)解。，說明退化對(duì)疊代的影響。minz=2x1x2.x1+x2≤6x2≤3x1+2x2≤9x1,x2≥0引進(jìn)松弛變量x3，x4，x5≥0，得到minz=2