【正文】 線性規(guī)劃單純形法的改進(jìn)舉例 第一步迭代，計(jì)算 ?? 210. PB??????????402， 112014?????????????， E1=?????????? ?41000102101，10111?? ? BEB=1 0 1 20 1 00 0 1 4??????????? 非基變量檢驗(yàn)數(shù) ? ? ? ? ? ?1 1 11111 0 1 2 1 02 , 0 0 , 0 , 3 0 1 0 4 0 2 , 3 40 0 1 4 0 1N N BBNCC?????? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? 對(duì)應(yīng)的換入變量為1x，計(jì)算 111() 2 1 6m in ( ) 0 m in , , 214()ikik iBbBPBP???????? ??? ? ? ??? ???????? 對(duì)應(yīng)的換出變量為3x，由此得到新的基? ?2 1 4 2,B P P P?，? ?2 1 4 2,B x x xX ?，? ?2 2 , 0 , 3BC ?， ? ?2 0 , 0NC ?。 勃蘭特 (Bland)法 1974 年由勃蘭特 ( B l a n d ) 提出了一個(gè)避免出現(xiàn)循環(huán)現(xiàn)象的簡(jiǎn)便規(guī)則： （ 1 ）選取0?σ j 中下標(biāo)最小的非基變量x k為換入變量，即取m in( | 0)jkj ???； （ 2 ）按? 規(guī)則計(jì)算時(shí)，若出現(xiàn)兩個(gè)和兩個(gè)以上的最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。 第一階段的線性規(guī)劃問(wèn)題可寫(xiě)為： m i n w = x6+ x7 x1+ x2+ x3+ x4 = 4 2 x1+ x2 x3 x5+ x6=1 3 x2+ x3 + x7= 9 x1, x2, x3, x4, x5, x6, x7≥ 0 線性規(guī)劃求解兩階段法舉例 cj 0 0 0 0 0 1 1 CB XB x1 x2 x3 x4 x5 x6 x7 b θi 0 x4 1 1 1 1 0 0 0 4 4 1 x6 – 2 [ 1] – 1 0 – 1 1 0 1 1 1 x7 0 3 1 0 0 0 1 9 3 ?j – 2 4 0 0 – 1 0 0 0 x4 3 0 2 1 1 – 1 0 3 1 0 x2 – 2 1 – 1 0 – 1 1 0 1 –– 1 x7 [ 6] 0 4 0 3 – 3 1 6 1 ?j 6 0 4 0 3 – 4 0 0 x4 0 0 0 1 – 1/ 2 1/ 2 – 1/ 2 0 0 x2 0 1 1/ 3 0 0 0 1/ 3 3 0 x1 1 0 2/ 3 0 1/ 2 – 1/ 2 1/ 6 1 ?j 0 0 0 0 0 – 1 – 1 w =0 線性規(guī)劃求解兩階段法舉例 第二階段：在單純表中除去人工變量，變換目標(biāo)函數(shù)，繼續(xù)求解。 線性規(guī)劃求解的人工變量法 對(duì)于如下線性規(guī)劃問(wèn)題 m a x z =c1 x1+ c2 x2+ …+ cn xn a11 x1+ a12 x2+ …+ a1nxn = b1 a21 x1+ a22 x2+ …+ a2nxn = b2 … … am1 x1+ am2 x2+ …+ amnxn = bm x1, x2,…, xn ≥ 0 線性規(guī)劃求解的人工變量法 分別對(duì)每個(gè)約束方程中加入一個(gè)人工變量 x n + 1 … , x n + m 得到 m a x z = c 1 x 1 + c 2 x 2 + … + c n x n a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 ?為了使加入人工變量后線性規(guī)劃問(wèn)題的最優(yōu)目標(biāo)函數(shù)值不受影響，我們賦予人工變量一個(gè)很大的負(fù)價(jià)值系數(shù) M (M為任意大的正數(shù) )。 （ 3 ） 根據(jù)? ? kjjj??? ?? 0|m a x ，所對(duì)應(yīng)的非基變量kX 為換入變量，計(jì)算kPB1? ，若01 ?? kPB 那問(wèn)題無(wú)解，停止計(jì)算，否則進(jìn)行下一步。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 ? 我們希望：每變換一次，就得到一個(gè)新的基可行解，并且是盡可能使目標(biāo)函數(shù)值改進(jìn)的基可行解。方程右邊，得如下形式： 11 , 2 , ,ni i i j jjmx b a x i m????? ? ??最優(yōu)性檢驗(yàn)和解的判別 將上式代入目標(biāo)函數(shù)式中，整理得 jnmjmiijijmiii xaccbcz )(1 11? ???? ???????????miii bcz10 nmjaczmiijij ,1,1????? ??令 jnmjjj xzczz )(10 ??????最優(yōu)性檢驗(yàn)和解的判別 nmjzc jjj ,1 ??????再令 01njjjmz z x????? ?稱為檢驗(yàn)數(shù) 。 由圖解法得到的啟示 ? 線性規(guī)劃問(wèn)題求解的基本依據(jù)是：線性規(guī)劃問(wèn)題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。 線性規(guī)劃問(wèn)題的圖解法舉例 max z =2 x1+x2 3x1+x2 ≤12 x1+x2 ≤5 x2 ≤3 x1， x2 ≥0 1 2 3 4 5 1 2 3 4 x2x1Q13 x1+ x2= 1 2 x1+ x2= 5Q2 ( 3 . 5 , 1 . 5 )目 標(biāo) 函 數(shù) 線 z = 0 可 行 域 為O Q1 Q2 Q3 Q4x2 = 3Q4 Q3 ON線性規(guī)劃問(wèn)題求解的幾種可能結(jié)局 ? 存在唯一最優(yōu)解。如上例。尋找線性規(guī)劃問(wèn)題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 在線性規(guī)劃模型中，可以用檢驗(yàn)數(shù) 替代目標(biāo)函數(shù)中的價(jià)值系數(shù) cj。 換入變量的確定 jnmjj xzz ?????10 ?如果存在多個(gè) σj 0, 則取 0,?? km? 假定存在一個(gè) 我們?nèi)? kmx ?為換入變量。 單純形算法計(jì)算舉例 例：用單純形法求解線性規(guī)劃問(wèn)題 m a x z = 2 x1+ x2 x2 ≤ 3 3 x1+ x2≤ 12 x1+ x2≤ 5 x1， x2≥ 0 ， 解：先將上述問(wèn)題化為標(biāo)準(zhǔn)形式 m a x z = 2 x1+ x2+0 x3+0 x4+0 x5 x2 + x3=3 3 x1+ x2+ x4= 12 x1+ x2+ x5=5 x1， x2， x3， x4， x5≥ 0 單純形法計(jì)算