運(yùn)籌學(xué)：C4單純形計(jì)算步驟

1、上節(jié)內(nèi)容回顧一線性規(guī)劃與單純形法單純形法找出一個(gè)初始可行解找出一個(gè)初始可行解是否最優(yōu)是否最優(yōu)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)（找更大的基本可行解（找更大的基本可行解）最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)直到找出為止，核心是：變量迭代直到找出為止，核心是：變量迭代結(jié)束結(jié)束單純形法步驟：?jiǎn)栴}1問(wèn)題2問(wèn)題31.3.2初始基可行解的確定u問(wèn)題1：找初始頂點(diǎn)？u問(wèn)題2：判斷最優(yōu)？u問(wèn)題3：轉(zhuǎn)換到另一頂點(diǎn)？11 max (1-20) (1-21() 01,21),njjjnjjjjZc xP xbxjn，u 找初始頂點(diǎn)分三種情況來(lái)進(jìn)行：123(1,2, )()1 0 0,0 1 00 0 1jPPjBP

2、Pn從中若能直接觀察到，由此得到初始基可行解。1.3.2初始基可行解的確定 (1,2,;1,2, )jijxa im jn對(duì)所有約束條件是“ ”形式的不等式，在每個(gè)約束條件的左端加一個(gè)松（2）弛變量。重新對(duì) 及進(jìn)行編號(hào)，得11,111122,1122,11 mmnnmmnnmm mmmnnmxaxa xbxaxa xbxaxaxb（1-23）轉(zhuǎn)化為第一種情況。得到其初始基可行解。T12( ,0,0)mXb bb1.3.2初始基可行解的確定對(duì)等式約束加上一個(gè)非負(fù)的人工變量；對(duì)不等式約束減去一個(gè)非負(fù)的剩余變量（變?yōu)榈仁郊s束），再加上一個(gè)非負(fù)的人工變量。 (3) 對(duì)所有約束條件是“ ”形式的不等式及

3、等式約束情況，若不存在單位矩陣時(shí)，采用人造基方法:詳細(xì)情況第五節(jié)討論。1.3.3最優(yōu)性檢驗(yàn)與解的判別u問(wèn)題1：找初始頂點(diǎn)？u問(wèn)題2：判斷最優(yōu)？u問(wèn)題3：轉(zhuǎn)換到另一頂點(diǎn)？對(duì)于這四種情況都要根據(jù)相應(yīng)準(zhǔn)則判斷出來(lái)。LPLP解的情況解的情況唯唯 一一 解解無(wú)無(wú) 窮窮 解解無(wú)無(wú) 界界 解解無(wú)可行解無(wú)可行解有最優(yōu)解有最優(yōu)解無(wú)最優(yōu)解無(wú)最優(yōu)解1.3.3最優(yōu)性檢驗(yàn)與解的判別將(1-24)代入(1-20),目標(biāo)函數(shù)變成1 (1,2,) (1-24)niiijjj mxba xim111() (1-25)mnmiijiijjij mizcbcc a x經(jīng)過(guò)迭代后，(1-23)式變成11001 1, mjjiijim

4、njiij miizcbjcc amnz zx令，則， (1-27)=1.3.3最優(yōu)性檢驗(yàn)與解的判別1mjjiijicc a為判斷解情況的依據(jù)！稱之為檢驗(yàn)數(shù)。(0)(0)T12( ,0,0)10,mjXb bbBjmnX若為對(duì)應(yīng)于基 的一個(gè)基可行解，且對(duì)于一切 ，(1)最優(yōu)解判別定理，則為有最優(yōu)解。(0)T1200,( ,0,0)1,mjm kXb bbjmn若為一個(gè)基可行解，對(duì)(2)無(wú)窮多最優(yōu)解判別定理，又存在某個(gè)非基變量于一切的檢驗(yàn)數(shù)則有無(wú)窮多 ，有最優(yōu)解。(0,)T120,1,2,0( ,0,0)mm ki m kimbaXbb若為一個(gè)基可行(3)無(wú)界解判別定理有一個(gè)且對(duì)于，有，那么無(wú)解

5、，有界解。1.3.45基變換（迭代、旋轉(zhuǎn)運(yùn)算）u問(wèn)題1：找初始頂點(diǎn)？u問(wèn)題2：判斷最優(yōu)？u問(wèn)題3：轉(zhuǎn)換到另一頂點(diǎn)？11,111,1122,112,22,11, mmkknnmmkknnll mml kklnnlxaxa xa xbxaxaxa xbxaxa xa xb考慮如下形式的方程組,11, mm mmm kkmnnmxaxaxaxb（1-33）1.3.45基變換（迭代、旋轉(zhuǎn)運(yùn)算）(0)0max(0),jjkkjXx（1）若基可行解不是最優(yōu)解，確定換入變量 由最優(yōu)解判別定理則：。存在設(shè)則對(duì)應(yīng)的 為換入變量。111,222,= kkkkklll kkmmm kkxxba xxbaxxba x

6、xbax確定換（2）確定 為換入變量后，在(1-33)中令其它非基變出量為零,得變量,=min(), kiii kkilii kl klxxba xbbaax考慮到變量的非負(fù)性要求，即在在由零開(kāi)始增大時(shí)，應(yīng)始終保持非負(fù)。第一個(gè)達(dá)到零的變量即為換出變量。若則 為換出變量。1.3.45基變換（迭代、旋轉(zhuǎn)運(yùn)算）1,11,112,12,22,1,1, 1 1 1 1 mknmknl ml klnnlm mm kaaabaaabaaa x baa對(duì)增廣矩陣 mnmab（1-34）進(jìn)行初等行變換，得到新的增廣矩陣，繼而得到新的基可行解，最后得到新的目標(biāo)函數(shù)及檢驗(yàn)數(shù)。以上過(guò)程反復(fù)進(jìn)行。本節(jié)內(nèi)容摘要一一線性規(guī)

7、劃與單純形法線性規(guī)劃與單純形法1.單純形法的計(jì)算步驟單純形法的計(jì)算步驟單純形表單純形表計(jì)算步驟計(jì)算步驟2.單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論人工變量法人工變量法jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Z0 04.1 單純形表，其中ijijjacc 1 mn min(0)ikjkjbaa1miiicb4.1 單純形表例例1 1 試列出下面LP的初始單純型表0,124 16 482. .32 max21212121xxxxxxtsxxz12345123142512345max 230002 84 16

8、. . 4 12,0zxxxxxxxxxxstxxx x x x x jc0 0 0 3 2BcBXb000543xxx1216854321 xxxxxi3 4Z03 24.1 單純形表，其中ijijjacc 0 0 0min(0)ikjkjbaa1 2 1 0 04 0 0 1 00 4 0 0 1 12345123142512345max 230002 84 16. . 4 12,0zxxxxxxxxxxstxxx x x x x4.2 標(biāo)準(zhǔn)LP的單純形計(jì)算步驟1.找初始基礎(chǔ)可行基找初始基礎(chǔ)可行基 對(duì)于對(duì)于(max, )，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣2.檢

9、驗(yàn)當(dāng)前基可行解是否為最優(yōu)解檢驗(yàn)當(dāng)前基可行解是否為最優(yōu)解 若所有非基變量檢驗(yàn)數(shù)都若所有非基變量檢驗(yàn)數(shù)都 0，則為最優(yōu)解，否則轉(zhuǎn)下一步；，則為最優(yōu)解，否則轉(zhuǎn)下一步；3.確定改善方向確定改善方向 從正的檢驗(yàn)數(shù)中找最大，選中者稱為入基變量，所在列稱為主列從正的檢驗(yàn)數(shù)中找最大，選中者稱為入基變量，所在列稱為主列4 確定出基變量確定出基變量 最小比例原則；所在行稱為主行最小比例原則；所在行稱為主行5.迭代過(guò)程迭代過(guò)程 主行與主行與主列主列相交的元素稱為主元，迭代以主元為中心進(jìn)行初等行相交的元素稱為主元，迭代以主元為中心進(jìn)行初等行變換，將主元變?yōu)樽儞Q，將主元變?yōu)?，主列主列上其它元素變?yōu)樯掀渌刈優(yōu)?。6

10、. 此時(shí)，得到一個(gè)新的單純形表，重復(fù)此時(shí)，得到一個(gè)新的單純形表，重復(fù)25。4.2 標(biāo)準(zhǔn)LP的單純形計(jì)算步驟例2 請(qǐng)用單純型表求解下LP0,124 16 482. .32 max21212121xxxxxxtsxxz12345123142512345max 230002 84 16. . 4 12,0zxxxxxxxxxxstxxx x x x x-4i-42124-3/40002-91/400103301004160-1/20101203x4x2xjjcz1/40-200-131/400103321-40080-1/20101221x4x2xjjcz3000320100401200100416

11、0001218000032jc BCBXb1x2x3x4x5xjjcz3x4x5x0-1/8-3/200-140-1/81/2102311/2-2004001/400142jjcz1x2x5x練習(xí)：利用單純形法求解 0,24261553221212121 xxxxxxxxMaxZ 0,24 2615 532432142132121 xxxxxxxxxxxxMaxZ 0 0 -1/12 -7/24-33/4-Z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cji15/43/4011/4-1/810 -1/125/24本節(jié)內(nèi)容摘要一一線性規(guī)劃與單純形法線性規(guī)劃與單純形法1.單純形

12、法的計(jì)算步驟單純形法的計(jì)算步驟單純形表單純形表計(jì)算步驟計(jì)算步驟2.單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論人工變量法人工變量法退化退化單純形法小結(jié)單純形法小結(jié)人工變量法人工變量法當(dāng)約束條件為當(dāng)約束條件為“ ”或或“”型，引入剩余變量或人工變量型，引入剩余變量或人工變量0,46 2.32132121xxxxxxxxts0,4 6 2.65432153216421xxxxxxxxxxxxxxts1241235123452 6. . 4,0 xxxstxxxxx x x x x人工變量法人工變量法一一 由于所添加的剩余變量的系數(shù)為由于所添加的剩余變量的系數(shù)為 1，不能構(gòu)成，不能構(gòu)成初始初始可行可行基

13、變量，為此引入一個(gè)人為的變量基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為（注意，此時(shí)約束條件已為“=”型），型），以便取以便取得初始基變量，故稱為人工變量；得初始基變量，故稱為人工變量；二二 由于人工變量加在等式約束中，故如果原問(wèn)題由于人工變量加在等式約束中，故如果原問(wèn)題有解的話，人工變量必須為零才能保證原等式有解的話，人工變量必須為零才能保證原等式約束成立。也就是說(shuō)，人工變量在原問(wèn)題的解約束成立。也就是說(shuō)，人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快被迭代出去。中是不能存在的，應(yīng)盡快被迭代出去。三三 大大M法法 與與 兩階段法兩階段法 兩種方法都是逼迫人工變量為零。兩種方法都是逼迫人

14、工變量為零。 例例1 大大M法的求解過(guò)程法的求解過(guò)程0,4 6 2. .)007810max(max0,46 2. .7810min6543215321642165432132132121321xxxxxxxxxxxxxxtsMxxxxxxzxxxxxxxxtsxxxz例例1 單純型表迭代過(guò)程單純型表迭代過(guò)程10 x1 3 1 1/2 0 1/2 0 1/2 6 7 x3 1 0 (1/2) 1 1/2 1 1/2 (2) II cjzj 0 1/2 0 3/2 7 M+3/2 10 x1 2 1 0 1 1 1 1 8 x2 2 0 1 2 1 2 1 III 最優(yōu)解 cjzj 0 0 1

15、2 6 M+2 答：最優(yōu)解為 x1=2, x2=2, x3=0, OBJ=36 大大M M法的一些說(shuō)明法的一些說(shuō)明一一 大大M M法實(shí)質(zhì)上與原單純型法一樣，法實(shí)質(zhì)上與原單純型法一樣，M M可看成一個(gè)很可看成一個(gè)很大的常數(shù)；大的常數(shù)；二二 人工變量被迭代出去后就不會(huì)再成為基變量；人工變量被迭代出去后就不會(huì)再成為基變量；三三 當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說(shuō)明原線性規(guī)劃問(wèn)題無(wú)可行解；變量，說(shuō)明原線性規(guī)劃問(wèn)題無(wú)可行解；四四 大大M M法手算很不方便，但是計(jì)算機(jī)中常用大法手算很不方便，但是計(jì)算機(jī)中常用大M M法用法用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很

16、大的數(shù)代替計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M,M,可能可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。二階造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。二階段法手算可能容易。段法手算可能容易。兩階段法兩階段法第二階段：以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型表求解。第一階段：不考慮原問(wèn)題是否存在基可行解；給原線性規(guī)劃問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和約束, 實(shí)現(xiàn)最小化。 然后用單純形求解，若目標(biāo)值為0，說(shuō)明原問(wèn)題存在基可行解，轉(zhuǎn)第二階段；否則原問(wèn)題無(wú)可行解，停止。 兩階段法兩階段法 為了簡(jiǎn)化計(jì)算，在第一階段重新定義價(jià)值系數(shù)如下：不是人工變量時(shí)當(dāng)為人工變量時(shí)當(dāng)時(shí)目標(biāo)函數(shù)為不是人工變量時(shí)當(dāng)為人工變量時(shí)當(dāng)時(shí)目標(biāo)函數(shù)為jjjjjjjjxcxcxcxc01max01min用二階段法求解用二階段法求解例例1 1的第一階段的第一階段 x1 x2 x3 x4 x5 x6 序號(hào) CB XB b 0 0 0 0 0 1 bi/aij* 1 x6 6 (2) 1 0 1 0 1 (3) 0 x3 4 1 1 1 0 1 0 4 I cjzj 2 1 0 1 0 0 0 x1 3 1 1/2 0 1/2 0 1/