線性規(guī)劃的圖解法與單純形解法-閱讀頁(yè)
2024-08-20 17:27本頁(yè)面
【正文】 量以及新的基矩陣1B 。 42 線性規(guī)劃求解的人工變量法 ? 人工變量法 引用人工變量是用單純形法求解線性規(guī)劃問(wèn)題時(shí)解決可行解問(wèn)題的常用方法。 由于單位陣可以作為基陣，因此，可選加入的人工變量為基變量。如果在最終單純形表中還存在非零的人工變量，這表示無(wú)可行解。 ?由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到原問(wèn)題的一個(gè)可行基。 線性規(guī)劃求解的大 M法 46 線性規(guī)劃求解的大 M法 max z = c 1 x 1 + c 2 x 2 + … + c n x n M ( x n + 1 + … + x n + m ) 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 47 【 例 】 用大 M法解 下列線性規(guī)劃 ???????????????????????012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、線性規(guī)劃求解的大 M法舉例 48 【 解 】 首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj式中 x4， x5為松弛變量 ， x5可作為一個(gè)基變量 ， 第一 、 三約束中分別加入人工變量 x x7， 目標(biāo)函數(shù)中加入 ―M x6―M x7一項(xiàng) ， 得到人工變量單純形法數(shù)學(xué)模型 用前面介紹的單純形法求解，見(jiàn)下表。 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。 54 線性規(guī)劃求解的兩階段法 兩階段法的基本思路是： 第一階段 ，首先不考慮原問(wèn)題是否存在基可行解 ， 先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù) ( 一般取 1) ，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。 我們可以構(gòu)造如下輔助問(wèn)題 m in w = xn +1+ … + xn + m+0 x1+ … +0 xn a11 x1+ a12 x2+ … + a1 nxn+ xn +1 = b1 a21 x1+ a22 x2+ … + 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ō)明原問(wèn)題存在基可行解，可進(jìn)行第二步計(jì)算； 否則，原問(wèn)題無(wú)可行解，應(yīng)停止計(jì)算。 56 【 例 】 用兩階段單純形法求解例 【 】 的線性規(guī)劃 。 第一階段最后一張最優(yōu)表說(shuō)明找到了原問(wèn)題的一組基可行解 ， 將它作為初始基可行解 ，求原問(wèn)題的最優(yōu)解 ， 即第二階段問(wèn)題為 )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ī)劃。 64 解的判斷 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)小于零 ,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。無(wú)可行解的判斷： (1)當(dāng)用大 M單純形法計(jì)算得到最優(yōu)解并且存在 人工變量 i0時(shí) ， 則表明原線性規(guī)劃無(wú)可行解 。 65 單純形法計(jì)算可能的循環(huán)現(xiàn)象 ?在求解線性規(guī)劃單純形方法的計(jì)算過(guò)程循環(huán)極少出現(xiàn)，但還是可能的。 如：勃蘭特法； 字典序法； 攝動(dòng)法。 67 復(fù)習(xí)舉例 有兩個(gè)變量的線性規(guī)劃問(wèn)題 ?????????????0,1m ax2121211xxxxaxxxz （ 1 ） 證明本題當(dāng)且僅當(dāng)1?a 時(shí)為可行。 68 復(fù)習(xí)舉例 考慮如下的線性規(guī)劃問(wèn)題： 12121212m i n1240 , 0z x xxxxxxx???? ? ???? ? ?????? 試問(wèn)：當(dāng)?在什么范圍內(nèi)取值時(shí)，分別有下面的結(jié)論成立？ （ 1 ） 該問(wèn)題具有無(wú)窮多最優(yōu)解； （ 2 ） 該問(wèn)題是無(wú)界的； （ 3 ） 以T(2 , 3 )為唯一最優(yōu)解
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1