【正文】 2 0 5 0 0 5 4 0 5 5 0 1 10 0 5 0 4 5 0 0 5 4 0 3 0 2 4 3 0 0 0 12 10 15 20 * 22 16 ? ? ? ? ? ? ? ? 單純形法 線(xiàn)性規(guī)劃問(wèn)題求解思路 若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解 找出一個(gè)基可行解 是最優(yōu)解嗎？ 是 結(jié)束 否 找出新的 基可行解 ? 基礎(chǔ)知識(shí) 例七 x1 + 2x2 + x3 = 8 x1 + x4 = 4 x2 + x5 = 3 2x1 + x2 + + x6 = 4 0 2 1 1 0 0 4 1 0 0 1 0 0 4 0 1 0 0 1 0 3 0 1 0 2 0 1 12 A= _ X=（ 0， 0， 8， 4， 3， 4） X=（ 8， 0， 0， 4， 3， 20） X=（ 4， 0， 4， 0， 3， 12） I A= _ 1 2 1 0 0 0 8 0 2 1 1 0 0 4 0 1 0 0 1 0 3 0 5 2 0 0 1 20 ? ? ? 1 2 1 0 0 0 8 1 0 0 1 0 0 4 0 1 0 0 1 0 3 2 1 0 0 0 1 4 A= _ 變量要求為 非負(fù)呢 0 5/2 1 0 0 1/2 10 0 1/2 0 1 0 1/2 6 0 1 0 0 1 0 3 1 –1/2 0 0 0 –1/2 2 A= _ X=（ 2， 0， 10， 6， 3， 0） ? 單純形法 線(xiàn)性規(guī)劃問(wèn)題求解過(guò)程 相鄰基可行解 兩個(gè)基可行解稱(chēng)為相鄰的，如果它們之間變換僅變換一個(gè)基 變量。換句話(huà)，它們對(duì)應(yīng)的基之間僅有一個(gè)列向量不同。 6 2 1 0 0 180 4 10 0 1 0 400 3 5 0 0 1 210 A= _ 3 1 1/2 0 0 90 26 0 5 1 0 500 12 0 5/2 0 1 240 A= _ 26/5 0 1 1/10 0 10 2/5 1 0 1/10 0 40 1 0 0 1/2 1 10 A= _ 24/5 0 1 0 2/5 96 2 0 0 1 2 20 3/5 1 0 0 1/5 42 A= _ ? ? ? 1 0 … 0 a1m+1 … a1k … a1n 0 1 … 0 a2m+1 … a2k … a2n ┇ ┇ … ┇ ┇ … ┇ 0 0 … 1 amm+1 … amk … amn A= _ b1 b2 ┇ bm 單純形法 X=（ b1， b2， … ， bm ， 0， … ， 0） Z=c1b1+c2b2+… +cmbm 0 ┇0 令： θ j =bj/ajk b1/a1k b2 a2kb1/a1k ┇ bm amkb1 /a1k bj ajkb1 /a1k ≥ 0 θ kiki abikabi a 11}0|{m in ????bj/ajk ≥ b1 /a1k X=（ 0 ， b2θ a2k ， … ， bmθ amk ， 0， … ,θ , … ， 0） Z(1)= Z + θ (ck∑ (i從 1到 m)ciaik ) σ σ= (σ 1,σ 2,… σ n),其中 σ j = cj acijmi i??1原來(lái)的基變量對(duì)應(yīng)的價(jià)值系數(shù) 針對(duì)不同列變量對(duì)應(yīng)的價(jià)值系數(shù) θ σ 單純形法 重要結(jié)論 ?當(dāng)所有 σ j≤0 時(shí)，此時(shí)的基可行解就是最優(yōu)解。 ?當(dāng)所有 σ j≤0 時(shí)，且有一個(gè)非基變量對(duì)應(yīng)的 σ j=0， 且對(duì)應(yīng)的 Pj存在正數(shù)分量，則問(wèn)題有無(wú)數(shù)個(gè)最優(yōu)解； 否則，當(dāng)所有 σ j 0時(shí) ,問(wèn)題有唯一最優(yōu)解。 ?當(dāng)存在 σ j0，且對(duì)應(yīng)的 Pj ≤0 時(shí)，問(wèn)題的解無(wú)界。 ac ijmi i??1σ σ= (σ 1,σ 2,… σ n),其中 σ j = cj θ lkliki abikabi a ??? }0|{m in?Z(1) = Z(0) + θσ k, 其中 σ k = ck ac ikmi i??1其中： 增廣矩陣 單純形法 單純形表 1 0 … 0 a1,m+1 … a1k … a1n 0 1 … 0 a2,m+1 … a2k … a2n 0 0 … 1 amm+1 … amk … amn b1 b2 ┇ bm ┇ ┇ … ┇ ┇ … ┇ … ┇ A= _ θ 1 θ 2 ┇ θ m θ σ= (σ 1 σ 2 … σ m σ m+1 … σ k … σ n ) 其中 σ j = cj acijmi i??1= cj （ c1a1j + c2a2j + … + cmamj） 基所對(duì)應(yīng)的 C 記 CB 變量所對(duì)應(yīng)的 C C = ( c1 c2 … cm cm+1 … ck … ) CB C1 C2 ┇ Cm 單純形法 單純形表 C c1 c2 … cm cm+1 … ck … θ CB XB b x1 x2 … xm xm+1 … xk … xn c1 c2 ┇ cm x1 x2 ┇ xm b1 b2 ┇ bm 1 0 … 0 a1,m+1 … a1k … a1n 0 1 … 0 a2,m+1 … a2k … a2n ┇ ┇ … ┇ ┇ … ┇ … ┇ 0 0 … 1 am,m+1 … amk … amn θ 1 θ 2 ┇ θ m σ 0 0 … 0 σ m+1 … σ k … σ n 這兩列是對(duì)應(yīng)基變量及相應(yīng)價(jià)值系數(shù) 跟隨每次換基操作變化而變 單純形法 單純形表 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 = 5 x1， x2 ， x3 ， x4 ， x5 ≥ 0 約束條件 st . 利潤(rùn) max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 例一 C 2 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 15 24 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 σ 單位矩陣 X = (0 0 15 24 5) z = 0 x3 x4 x5 基變量及價(jià)值系數(shù) 0 0 0 2 1 0 0 0 4 5 ? 單純形法 單純形表 C 2 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 4 5 0 5 1 0 0 1 1/3 0 1/6 0 1 1 0 0 1 σ 2 1 0 0 0 基變量及價(jià)值系數(shù) 3 12 3/2 ? 1 0 2/3 0 1/6 1單位矩陣 1 0 2 0 0 1/3 1/3 0 C 2 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15/2 7/2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 1/2 0 1 0 1/4 3/2 σ 0 0 0 1/4 1/2 X*=(7/2,3/2,15/2,0,0) Z*= 17/2 B= 1 0 5 0 6 2 0 1 1 B1= 1 5/4 15/2 0 1/4 1/2 0 1/4 3/2 單純形法 單純形表 ?用單純形表求解步驟： 1) 求初始基可行解，列出單純形表 (存在單位矩陣 )。 2) 最優(yōu)解檢驗(yàn)。求出檢驗(yàn)數(shù) σ ， 利用判斷準(zhǔn)則進(jìn)行最優(yōu)解判斷； 3) 如果是無(wú)解、無(wú)限解和最優(yōu)解情況，求解結(jié)束。否則轉(zhuǎn) 4）； 4) 從一個(gè)基可行解轉(zhuǎn)移到相鄰的使得目標(biāo)函數(shù)值變得更大的基可行解，并列出新的單純形表，轉(zhuǎn) 2）。 在我們前面討論中，我們一直認(rèn)為存在一個(gè)單位矩陣的，因?yàn)橛锌尚薪獗卮嬖诳尚谢?，通過(guò)矩陣初等行變換總能得到一個(gè)單位矩陣。然而在實(shí)際使用單純形表求解問(wèn)題時(shí)，我們可以通過(guò)引入 松弛變量 、 人工變量 等得到一個(gè)單位矩陣。