線性規(guī)劃的圖解法與單純形解法-文庫(kù)吧在線文庫(kù)
【正文】 + … + a2 nxn + xn +2= b2 … … am 1 x1+ am 2 x2+ … + amnxn+ xn + m = bm x1, x2, … , xn , xn +1, … , xn+ m≥ 0 ?????????55 線性規(guī)劃求解的兩階段法 然后用單純形法求解所構(gòu)造的新模型，若得到 w=0，這時(shí)，若基變量中不含人工變量，則說(shuō)明原問題存在基可行解，可進(jìn)行第二步計(jì)算； 否則，原問題無(wú)可行解，應(yīng)停止計(jì)算。無(wú)可行解的判斷： (1)當(dāng)用大 M單純形法計(jì)算得到最優(yōu)解并且存在 人工變量 i0時(shí) ， 則表明原線性規(guī)劃無(wú)可行解 。 68 復(fù)習(xí)舉例 考慮如下的線性規(guī)劃問題： 12121212m i n1240 , 0z x xxxxxxx???? ? ???? ? ?????? 試問：當(dāng)?在什么范圍內(nèi)取值時(shí)，分別有下面的結(jié)論成立？ （ 1 ） 該問題具有無(wú)窮多最優(yōu)解； （ 2 ） 該問題是無(wú)界的； （ 3 ） 以T(2 , 3 )為唯一最優(yōu)解。 如：勃蘭特法； 字典序法； 攝動(dòng)法。 第一階段最后一張最優(yōu)表說(shuō)明找到了原問題的一組基可行解 ， 將它作為初始基可行解 ，求原問題的最優(yōu)解 ， 即第二階段問題為 )5310,511,53,0(?X1 2 31 2 41 4 51 3 4m a x 3 26 1 35 5 53 3 315 5 52 2 115 5 50 , 1 , 2 , , 5jZ x x xx x xx x xx x xxj? ? ??? ? ? ????? ? ????? ? ? ???????60 56?5335233119325?Cj 3 2 1 0 0 b CB XB x1 x2 x3 x4 x5 2 0 － 1 x2 x5 x3 1 0 0 0 0 1 0 1 0 λj 5↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 13 λj 0 0 0 － 5 Cj 3 2 － 1 0 0 b CB XB x1 x2 x3 x4 x5 2 0 － 1 x2 x5 x3 － 6/5 [3/5] － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5 → 11/5 λj 5 ↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λj 0 0 0 － 5 － 25/3 用單純形法計(jì)算得到下表 最優(yōu)解 X＝（ 31/3， 13， 19/3， 0， 0)T；最優(yōu)值 Z＝ 152/3 61 【 例 】 用兩階段法求解例 【 】 的線性規(guī)劃。 Cj 5 － 8 0 0 M b CB XB x1 x2 x3 x4 x5 0 M x3 x5 [3] 1 1 － 2 1 0 0 － 1 0 1 6→ 4 λj 5－ M↑ － 8+2M 0 M 0 5 M x1 x5 1 0 1/3 － 7/3 1/3 － 1/3 0 － 1 0 1 2 2 λj 0 － 29/3+7/3M － 5/3+1/3M M 0 表中 λj≥0， j=1， 2， … ， 5， 從而得到最優(yōu)解 X=（ 2， 0， 0， 0，2） ， Z=10+2M。 由于單位陣可以作為基陣，因此，可選加入的人工變量為基變量。 j1?? （ 5 ） 當(dāng) B 為最優(yōu)基時(shí)，在上表中應(yīng)有 ?????????0011BCABCCBBN 因 X B的檢驗(yàn)數(shù)可寫作01 ?? ? BBCC BB 所以 有 ?????????0011BCABCCBB BC B 1?稱為單純形乘子，若令BC BY 1?? ，則有0, ?? YCYA成立。 ? 定理 2 有無(wú)窮多最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，對(duì)于一切 j = m +1, … , n , 有檢驗(yàn)數(shù) ? j ≤ 0, 且存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) ? m + k =0, 則該線性規(guī)劃問題有無(wú)窮多個(gè)最優(yōu)解。 23 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 24 【 例 】 用單純形法求解 421 22m i n xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj25 【 解 】 這是一個(gè)極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) σ j≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 ? 線性規(guī)劃問題求解時(shí)可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 、無(wú)窮多個(gè)最優(yōu)解 、 有無(wú)界解 、 無(wú)解或無(wú)可行解 。 ? 用圖解法求解實(shí)際線性規(guī)劃問題，一般按照如下基本步驟： Step1 畫直坐標(biāo)系； Step2 根據(jù)約束條件畫出可行域； Step3 畫過坐標(biāo)原
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1