運(yùn)籌學(xué)-(單純形法原理)-預(yù)覽頁
【正文】 ） T x3 = 6 – 2 3 =0 x4 = 16 – 4 3=4 x2 = 3 其對應(yīng)的目標(biāo)函數(shù)值： z1=2 3+3 3=15 （ 7）檢驗(yàn) X （ 2） 是否為最優(yōu)解 將約束方程組改為用非基變量 x3 、 x5來表示基變量 x x2 、 x4的表達(dá)式。 010 ZxZZnjjj ??? ???對于任意可行解 X， 對于基本可行解 X0， 0ZZ ?0 12X ( 0 , 0 , , 0 , , , , )mb b b? LL無窮多最優(yōu)解的判定 ? 若對于一 切非基變量的角指數(shù) j均有 ?j ≤0, 并且存在一個 ?j =0, 則線性規(guī)劃問題有無窮多最優(yōu)解 ； 無最優(yōu)解判別定理 ：若 是對應(yīng)于 B的基本可行解， 非基變量 x k的檢驗(yàn)數(shù) ?k 0 , 且對于 i=1,2,……,m 均有 aik ≤0, 則原問題沒有有限最優(yōu)解。 作業(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出基，換基過程 若 θ不存在 , 則 Z→∞ ，沒有有限最優(yōu)解。 總 結(jié) 通過以上例題的分析，可以歸納出單純形法的步驟： （ 1）建立實(shí)際問題的線性規(guī)劃數(shù)學(xué)模型； （ 2）把一般的線性規(guī)劃問題化為標(biāo)準(zhǔn)型； （ 3）確定初始基本可行解； （ 4）檢驗(yàn)所得到的基本可行解是否為最優(yōu)解； （ 5）迭代，求得新的基本可行解。 （ 6）第二次迭代 和第一次迭代同樣的道理，應(yīng)選取非基變量 x1使它成為基變量，而且讓它取盡可能大的值，同時， x5仍作為非基變量取值為零。從原來的基變量 x3 、 x4 、 x5中選出一個作為非基變量?？梢? X（ 0） 不是最優(yōu)解 （ 4）第一次迭代。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。復(fù)習(xí) 由圖解法得到的啟示： ，解的情況有：唯一解；無窮多最優(yōu)解；無界解；無可行解。 ，先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。由目標(biāo)函數(shù)的表達(dá)式： z =2x1 +3x2 可知，非基變量 x1 和 x2 的系數(shù)為正，如果把非基變量 x1 或 x2轉(zhuǎn)換為基變量，則會使目標(biāo)函數(shù)的值增加。 由于目標(biāo)函數(shù)中 x2的系數(shù)大于 x1的系數(shù)，因此，可以選擇 x2使它作為基變量，而且讓它取盡可能大的值，同時， x1仍作為非基變量取值為零?？梢?X （ 1） 不是最優(yōu)解?？捎酶咚瓜シǖ玫剑? x1 + 1/2 x3 – 1/5x5 = 3 – 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3 移項(xiàng)后得到： x1 = 3 – 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 – 4/5x5 x2 = 3 –1/5 x5 將上式代入目標(biāo)函數(shù)，得目標(biāo)函數(shù)用非基變量 x3 、 x5表示的表達(dá)式 z =15 – x3 – 1/5x5 這時 ,目標(biāo)函數(shù)中非基變量的系數(shù)都不大于零 ， 可見目標(biāo)函數(shù)的值不可能再繼續(xù)增大 ,目標(biāo)函數(shù)已經(jīng)取得最大值 15 ， 故為 X （ 2） 最優(yōu)解。 ( 0 ) 12( 0 , 0 , , 0 , , , , )mX b b b??? LL該證明留作課后練習(xí) 若 ?k 0， 則選 xk進(jìn)
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1