運(yùn)籌學(xué)-(單純形法原理)(參考版)
2024-08-16 17:07本頁(yè)面
【正文】 作業(yè)： P56 求解 (1) (書 ) ，特別是列表法 2. 掌握各種解的判定方法 。 用最小比值法確定 xk的最大值 θ， 使基變量 xl取 0值 ， 其它基變量非負(fù)； ??????????lklikikiabaab 0m i n0 1 , 2 , ,n i i i k kx b a x i m? ??? ? ? ? L即 xl出基，換基過(guò)程 若 θ不存在 , 則 Z→∞ ，沒(méi)有有限最優(yōu)解。 010 ZxZZnjjj ??? ???對(duì)于任意可行解 X， 對(duì)于基本可行解 X0， 0ZZ ?0 12X ( 0 , 0 , , 0 , , , , )mb b b? LL無(wú)窮多最優(yōu)解的判定 ? 若對(duì)于一 切非基變量的角指數(shù) j均有 ?j ≤0, 并且存在一個(gè) ?j =0, 則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解 ； 無(wú)最優(yōu)解判別定理 ：若 是對(duì)應(yīng)于 B的基本可行解， 非基變量 x k的檢驗(yàn)數(shù) ?k 0 , 且對(duì)于 i=1,2,……,m 均有 aik ≤0, 則原問(wèn)題沒(méi)有有限最優(yōu)解。 總 結(jié) 通過(guò)以上例題的分析，可以歸納出單純形法的步驟： （ 1）建立實(shí)際問(wèn)題的線性規(guī)劃數(shù)學(xué)模型； （ 2）把一般的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型； （ 3）確定初始基本可行解； （ 4）檢驗(yàn)所得到的基本可行解是否為最優(yōu)解； （ 5）迭代，求得新的基本可行解。 x1的取值也按同樣的方法確定： x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5 將 x1 = θ ， x5 = 0代入： x3 = 6 – 2 θ ≥0 x4 = 16 – 4 θ ≥0 x2 = 3 ≥0 即： x1 = θ =min{6/2， 16 /4 ， ~}=3 相應(yīng)地有： 可見(jiàn)，從原來(lái)的基變量 x2 、 x3 、 x4中選出 x3作為非基變量，得第二次迭代后的基本可行解： X （ 2） =（ 3， 3， 0， 4， 0） T x3 = 6 – 2 3 =0 x4 = 16 – 4 3=4 x2 = 3 其對(duì)應(yīng)的目標(biāo)函數(shù)值： z1=2 3+3 3=15 （ 7）檢驗(yàn) X （ 2） 是否為最優(yōu)解 將約束方程組改為用非基變量 x3 、 x5來(lái)表示基變量 x x2 、 x4的表達(dá)式。 （ 6）第二次迭代 和第一次迭代同樣的道理，應(yīng)選取非基變量 x1使它成為基變量，而且讓它取盡可能大的值，同時(shí)， x5仍作為非基變量取值為零?？捎酶咚瓜シǖ玫剑? 2x1 + x3 – 2 /5x5 = 6 4x1 + x4 = 16 x2 + 1 /5 x5 = 3 移項(xiàng)后得到： x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5 將上式代入目標(biāo)函數(shù)，得目標(biāo)函數(shù)用非基變量 x1 、 x5表示的表達(dá)式 z =9+2x1 – 3/5x5 由于非基變量 x1的系數(shù)是正數(shù)，如果把非基變量轉(zhuǎn)換為基變量， 則會(huì)使目標(biāo)函數(shù)的值增加。從原來(lái)的基變量 x3 、 x4 、 x5中選出一個(gè)作為非基變量。因此，哪些變量作為基變量，哪些非基變量，就要發(fā)生變化。可見(jiàn) X（ 0） 不是最優(yōu)解 （ 4）第一次迭代。從而有 x3 =12， x4 =16， x5 =15，于是得到初始基本可行解： ? ?????????????1000100015430 PPPBX （ 0） =（ 0， 0， 12， 16， 15） T 其對(duì)應(yīng)
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1