1、由圖解法的例可看出:線性規(guī)劃的最優(yōu)解在極點(diǎn)上（頂點(diǎn)）不是凸集線性規(guī)劃 問(wèn) 題基本定理定理一若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行 域是凸集。定理二線性規(guī)劃問(wèn)題的基本可行解X對(duì)應(yīng)線性規(guī)劃 問(wèn)題可行域（凸集）的頂點(diǎn)。定理三若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解（即最優(yōu)解一定在某頂點(diǎn)上）。從上述三個(gè)定理可以看出,要求線性規(guī)劃問(wèn)題的最優(yōu)解,只要比較可行域（凸集）各個(gè)§ 3.2單純形方法從一個(gè)基可行解（極點(diǎn)）出發(fā)（如何去找一個(gè)基可行解？），判斷其是否為最優(yōu)解,（如何判斷？），若不是，則轉(zhuǎn)換到相鄰的基可行解（另一個(gè)極點(diǎn)），并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解為止。單純形法：先找到

2、一個(gè)初始基可行解，如果不是最優(yōu)解，設(shè)法轉(zhuǎn)換到另一個(gè)基可行解（換基 迭代，即從極點(diǎn)到極點(diǎn)），并使目標(biāo)函數(shù)不斷 增大，一直到找到最優(yōu)解為止。xN=o X=(XB,XN)2.3.1單純形表單純形法的具體步驟：（一）確定初始基可行解在L.P問(wèn)題的標(biāo)準(zhǔn)型：maxiN = exr Ax = hs.t<1乂 > O中，不妨設(shè)B是一個(gè)可行基，于是A二（B,N）不失一般性假定B二（円，,Pm）,基變量Xb= （X，,Xm）TN =（Pm+i,Pn）,非基變量 Xn=（Xm+1，,XJT.則x= （ XB 5 XN ） T相應(yīng)有C=（Cb，Cn）于是，原問(wèn)題化為:Xb maxZ = CX=(qC)&#

3、39;-X NfXb(5N) v =bs.t.<X1V即 maxZ=CBXB+CwXN(1)BXb +NXN=bg)s.t.<xb,xn>0對(duì)式兩邊同時(shí)左乘B"1,得XB=B"b_E-'NXN0),并代入 式，得Z = CBB-b-(CBBN-CN)XN (4)令非基變量Xn=o,得Xb二E-%從而相應(yīng)基可行解為XB1 (BlbX= J = “初始(*)(二)最優(yōu)化檢驗(yàn)由上知道，目標(biāo)函數(shù)取值為Z = CbBF .由于CbB-B-Cb =0, 故有z = CbB" -(CrB-B -Cb)Xb -(CrB-N - Cn)Xn=CBBb -

4、(CbB'A - C)X(5)將(3)、(4)分別改寫(xiě)為如下形式:JXe+B-TVXn =B-%z + (C”N - CN )XN = CBBb令 crN=CBBiN-CNcr = C- C.BA則(5)式可以寫(xiě)成 乙二皿屯-兒 =CBB-lb-oX.©) b = (oQn )由(6)看到,要使Z取到更大的值必須a < 0,即b = C-C”450也就是說(shuō):當(dāng)b s o時(shí),(*)表示的基可行解是最fW (達(dá)到最優(yōu))，計(jì)算結(jié)束.否則另?yè)Q一個(gè)基可行解即:當(dāng)b A 0時(shí),(*)表示的基可行解還不是最優(yōu)解，Z可以繼續(xù)增大。越尢Z增大更明顯所以必須另 換一個(gè)基，尋找一個(gè)新的基可行

5、解（三）換基迭代：”為什么？換基:取b A 0中的最大者q對(duì)應(yīng)的非基變豊， 換成基變量把原初始基中基變量換出作為非基變量，這里耳的廠由下式?jīng)Q定min<糾幾0> =匕_V J玉稱為主元，這樣就得到一個(gè)新期'。（2）重復(fù)（一）、（二）對(duì)上面分析過(guò)程進(jìn)行總結(jié)：（1）在標(biāo)準(zhǔn)型中，找一個(gè)單位基矩陣并求 出該基對(duì)應(yīng)的基可行解。當(dāng)LP問(wèn)題的約束條件全部為 “V” 時(shí)，在變換為標(biāo)準(zhǔn)型的過(guò)程弓I進(jìn)松馳變量，就無(wú)得到 了 一單位矩陣初始可行簽和初始基可行解。（2）檢驗(yàn)該基可行解是否最優(yōu)？通過(guò)非基 變量的檢驗(yàn)數(shù)。（3）若不是最優(yōu)，則另找一個(gè)基產(chǎn)生一個(gè)基可行解換基迭代。直到最優(yōu)。對(duì)此原理，我們可以

6、通過(guò)單純形表來(lái)實(shí)現(xiàn)。單純形表一般假設(shè)當(dāng)前的基B =（片上，,PJ對(duì)應(yīng)的單純形表為CjCl-Cr -CmG"+l ° k C nCbXbb xmX7+l 總X”5xik11/77+1 5k C2 兀2br1ann+1 ark arn5Xmbn1amm+l Q ink ° mnZ=CBBb00.0b加+i6J說(shuō)明1、表中基變量所在位置并不一定正好在前m個(gè)位 置上，但總可以通過(guò)調(diào)換重新排成上表形式。2、表中最下一行稱為檢驗(yàn)數(shù)行，對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)為：（用于檢驗(yàn)是否還須繼續(xù)迭代）777-bj = cj CBB Pj = Cj 工q %（j = 12，i3、不難看出，基

7、變量x廠（巧,兀2，乂的檢驗(yàn) 數(shù)均為02.3.2單純形法的步驟引例：解L.P問(wèn)題maxZ = 4xr +3x22xr + 3x2 < 24s.t< 3xv + 2x2 < 26> 0解：引進(jìn)松馳變量兀4，化為標(biāo)準(zhǔn)型maxZ = 4xr + 3x2 + 0兀3 + 0x42xr + 3x2 + x3 = 24s.t< 3xv + 2x2+ £ = 26x3?x4 > 0第一步：把模型化為標(biāo)準(zhǔn)形式后找出初始可行基, 建立初始單純形表（見(jiàn)下表）。本例中取初始基B1NP3 , P4）=I，則X B =（兀3，兀4）7', Cbi = （0,0）=厶

8、 BlA = A. b = Blb = b(y = C-CB BA.Z=b0= CB= 0Cj4300XbbXix2x3X400x3X424262 3103 201z04300ci43000CbXbbXx2x3x400X3X424262 3103 201z04300J由表得基可行解：X =(Xlx2x3x4)T = (0,0,24,26)7 目標(biāo)函數(shù)値Z =0,但B是否為最 優(yōu)基需檢驗(yàn)，轉(zhuǎn)下一步（二）最優(yōu)檢驗(yàn)由于6=4, cr2 =3,（即壞全非正） 所以基可行解不是最優(yōu).第三步：換基迭代確定換入變豊門(mén)$ = min/| bj vO,O W j <« 確定換出變量按最小比值原則

9、求出五。9 = min =-耳>0*2,其中耳為主元。(3) 以盜為主元，在單純形表中進(jìn)行初等變換:第廠行同時(shí)將Xg中的石換為勺得到新的可行基B =兀衛(wèi)衛(wèi)此）和相應(yīng)的表T）.第四步重復(fù)第二、第三步，首到獲得最優(yōu)解，或判斷出有無(wú)界解，計(jì)算吉束。見(jiàn)下表:Cj4300XBbX1X2X3X4u0X3242310120X426320126/3z043000X320/305/31-2/344X126/312/301/313z104/301/30-4/33X24013/5-2/54X1610-2/53/5z3600-1/5-6/51.上第一表中，X為換入變量；又由于比值=min (24/2, 26/3

10、) =26/3,確定X4 為換出變量X所在列和X4所在行的交叉處 為圭元。進(jìn)行迭代后，X =(26/3, 0, 20/3, 0幾標(biāo)函數(shù)值為Z=104/3,優(yōu)值。2.第二次迭代X2為換入變畳，X3為換出變量。 進(jìn)行迭代石，X=(6, 4, 0, 0)T,因最后一 行的所有檢驗(yàn)數(shù)都 已是正數(shù)或零， 標(biāo)函數(shù)值為ZZ=36處最優(yōu)值。max Z = 3兀+ x2H +x2 < 4 -x+x2< 2sl< 6x +2x2 <18> 0解：引進(jìn)松馳變量兀,兀，x5,化為標(biāo)準(zhǔn)型max Z = 3兀+心+ 0兀+ °兀+ °兀X + 3兀2 + 兀3 = 4X + 兀2+ 兀4 = 2s.t<6x +2冷 +x5=18兀兀2，兀3'兀4，兀5»0Cj31000eCb XbbX1X2X3X4X50 x341110040 x42-110100 x518620013z031000J 60 X3102/310-1/60 x4504/3011/63 X311/3001/6Z90000-1/2該問(wèn)題的最優(yōu)解X怙(3, 0, 1, 5, 0) T最