運(yùn)籌學(xué)基礎(chǔ)-線性規(guī)劃(3)精彩ppt

1、1單純形法(Simplex Method)是美國(guó)人丹捷格(G.Dantzig)1947年創(chuàng)建的這種方法簡(jiǎn)捷、規(guī)范，是舉世公認(rèn)的解決線性規(guī)劃問(wèn)題行之有效的方法。 表格法 矩陣法改良的單純形法 單純形法的矩陣計(jì)算線性規(guī)劃2Cj比值CBXBb檢驗(yàn)數(shù)j檢驗(yàn)數(shù)：初始時(shí)是目標(biāo)函數(shù)的系數(shù)（隨基的調(diào)整變化）變量符號(hào)基變量符號(hào)（隨基的調(diào)整變化）基變量在目標(biāo)函數(shù)中的系數(shù)（變化）約束方程的常數(shù)項(xiàng)約束方程的變量系數(shù)有一個(gè)檢驗(yàn)數(shù)j=0，此時(shí)基解不是最優(yōu)；所有檢驗(yàn)數(shù)j0 )= k ,則確定xk入基檢驗(yàn)數(shù)j=Cj Ciaij如果對(duì)j，j 0則最優(yōu)，否則到下一步第四步：基變換=min (bi / aik 0 )= bl /

2、alk ,則確定xn+l 出基第五步：以alk為主元素進(jìn)行迭代，將xn+l換為xk，求新可行解第六步：繼續(xù)判定是否最優(yōu)，如果不是最優(yōu)再求求新可行解第二步：找初始可行基，確定初始可行解第一步：將線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)化，求出增廣矩陣線性規(guī)劃20 x1 x2 x3 x4x5x6b Max z=2x1+3x2 2x1+2x2+x3 =12 x1+2x2+x4 =8 4x1 +x5 =16 4x2 +x6=12標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型Max z=2x1+3x2 2x1+2x2 12x1+2x2 8 4x1 16 4x2 12 x1, x2, x3 000003216100048010211200122000012000

3、401線性規(guī)劃21x1 x2 x3 x4x5x6b00003216100048010211200122000012000401線性規(guī)劃2200003216100048010211200122000012000401-9000021610004201001600102-3/4 0-1/2-1/23000101/4-130-200081-400020100120-21001/4 2-1/21/23000101/4-14-1/8-3/200041/2-200041/400010-1/4-11000 1002-1/81/20100令非基變量x4=0, x5=0,得到最優(yōu)解：線性規(guī)劃23=0,16242

4、04451021212121xxxxxxxxZMax000510161024200144x1 x2 x3 x4 b化為標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形線性規(guī)劃=0,16242044510432142132121xxxxxxxxxxxxZMax24=0,122316423421212121xxxxxxxxZMin=122316420034max4213214321xxxxxxxxxxZ000-3-412-1023160-142x1 x2 x3 x4 b化為標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形線性規(guī)劃25maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x

5、2 , x3 0S.t.02134 1216323x1 x2 x3 b已經(jīng)是標(biāo)準(zhǔn)型，不需再劃為標(biāo)準(zhǔn)型線性規(guī)劃26n 用單純形法解題時(shí)，需要有一個(gè)單位矩陣作為。n 當(dāng)約束條件都是“”時(shí)，加入就形成了。n 但如果存在“”或“”型的約束，就的。 采用人造基的辦法：采用人造基的辦法： 處理方法有兩種：處理方法有兩種：線性規(guī)劃27maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t.沒(méi)有單位矩陣，不符合構(gòu)造初始基的條件，沒(méi)有單位矩陣，不符合構(gòu)造初始基的條件， 。 maxZ= 3x1 - x2 -2 x3

6、-M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0 人工變量最終必須等于0才能保持原問(wèn)題性質(zhì)不變。 為保證人工變量為0，在。 M為無(wú)限大的正數(shù)，這是一個(gè)懲罰項(xiàng)，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須逐步從基變量中。 如若到，那么這個(gè)問(wèn)題就沒(méi)有可行解，當(dāng)然亦。 線性規(guī)劃28按大按大M法構(gòu)造人造基，引入人工變量法構(gòu)造人造基，引入人工變量x4 , x5 的輔助問(wèn)題如下：的輔助問(wèn)題如下： 【例例】 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3

7、x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t. maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0線性規(guī)劃290-M-2-13411-2160-323-M0110M0-2-2M-13+4M4 11-216 0-3230 0 1 3+3M -1+2M -2-3M 0 -M 6Mx1 x2 x3 x4 x5 b10M0-2-2M-13+4M411-2160-323001 3+4M -1 -2-2M 0

8、0 10M線性規(guī)劃3010M0-2-2M-13+4M411-2160-323001-6+2M0 1+2M-3-8M/30212-8/3020-12/31-1-4M/3-1/31/3-7-M-1/20-5/3011/21-4/3031/20-2/31-M-5/6-1/61/6線性規(guī)劃31劃為標(biāo)準(zhǔn)型，并按大劃為標(biāo)準(zhǔn)型，并按大M法引入人工變量法引入人工變量x4 , x5 的輔助問(wèn)題如下：的輔助問(wèn)題如下：=0,12324112332131321321321xxxxxxxxxxxxxxZMin=0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxx

9、xxZMax松馳變量松馳變量剩余變量剩余變量人工變量人工變量懲罰項(xiàng)懲罰項(xiàng)線性規(guī)劃320-M0-1-1311010-230021-411011-2100-10-M0104M00 -1+3M-1+M3-6M11010-230021-411011-21-M0-10 0010 x1 x2 x3 x4 x5 x6 x7 bx1 x2 x3 x4 x5 x6 x7 b=0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax線性規(guī)劃33M+1-3M+10 0-1+M11100-21-2001010-110-23-M0-1000102-M-10 00111010-21-20001