【正文】 29 【 例 】 求解線性規(guī)劃 21 42m a x xxZ ?????????????????0,21024221212121xxxxxxxx【 解 】 :化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如下表所示 30 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 x5 － 1 1 1 [2] 2 － 1 1 0 0 0 1 0 0 0 1 4→ 10 2 2 5 — λj 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λj 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λj 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λj 0 0 0 － 2 0 31 表 (3)中 λj全部非正 ,則最優(yōu)解為 : 20,)25,0,0,27,3()1( ?? ZX T 表 (3)表明 ,非基變量 x3的檢驗(yàn)數(shù) λ3=0, x3若增加 ,目標(biāo)函數(shù)值不變 , 即當(dāng) x3進(jìn)基時(shí) Z仍 等于 20。 13 【 例 】 用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ14 【 解 】 化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 系數(shù)矩陣 A及可行基 B1 r(B1)=2， B1是一個(gè)初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T ??????????????0,30340243m a x432142132121xxxxxxxxxxxxZ???????10310112A???????10011B15 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。 ? 線性規(guī)劃問(wèn)題求解時(shí)可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 、無(wú)窮多個(gè)最優(yōu)解 、 有無(wú)界解 、 無(wú)解或無(wú)可行解 。 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ī)劃問(wèn)題 ,可以將其化為極大化問(wèn)題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。 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成立。 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。 如：勃蘭特法； 字典序法； 攝動(dòng)法。無(wú)可行解的判斷： (1)當(dāng)用大 M單純形法計(jì)算得到最優(yōu)解并且存在 人工變量 i0時(shí) ， 則表明原線性規(guī)劃無(wú)可行解 。 ?由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到原問(wèn)題的一個(gè)可行基。 無(wú)界解的判斷 : 某個(gè) λk0且 aik≤０（ i=1， 2,…,m ）則線性規(guī)劃具有無(wú)界解 35 單純形法計(jì)算的矩陣描述 對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題 m a x0z C XAX bX????=≥ 假定存在基 B ，基變量為BX，非基變量為NX，則有 111111()()BNB B N N B N N NB N B NX B b B N Xz C X C X C B b B N X C XC B b C C B N X????????? ? ? ? ?? ? ? 36 單純形法計(jì)算的矩陣描述 與前面檢驗(yàn)數(shù)計(jì)算公式對(duì)照，可得非基變量檢驗(yàn)數(shù)計(jì)算公式 1N N BC C B N???? 另外，基變（向）量 XB的檢驗(yàn)數(shù)可寫作 1 0B B BC C B B??? ? ? 所以可得標(biāo)準(zhǔn)形式的線性規(guī)劃模型檢驗(yàn)數(shù)計(jì)算的一般計(jì)算公式 1BC C B A???? 37 單純形法計(jì)算的矩陣描述 再考慮下列線性規(guī)劃問(wèn)題 m a x0z C XAX bX????≤≥ 上式加上松弛變量后為 m a x 00 , 0SSSz C X XA X I X bXX???????≥ ≥ 38 單純形法計(jì)算的矩陣描述 ? ?m a x z | 0SXCX??? ???? ? ??????????????0,|XXbXXIASS