王家榮-運籌學-資料下載頁

　　

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