[經(jīng)濟(jì)學(xué)]第二章new對(duì)偶理論與靈敏度分析-文庫吧資料
2024-12-14 01:55本頁面
【正文】 0 1 0 1/4 Z′ 600 200 1600 0 0 300 600/2 200/1 1600/4 Chapter 2 靈敏度分析 cj 1200 800 1600 1200 0 0 cB xB b x1 x2 x3 x4 x5 x6 800 x2 2 2 1 4 0 1 0 1200 x4 1/4 1/2 0 2 1 1/2 1/4 Z′ 200 0 800 0 200 300 800/2 300/(1/4) Chapter 2 靈敏度分析 cj 1200 800 1600 1200 0 0 cB xB b x1 x2 x3 x4 x5 x6 800 X2 3/2 1 1 0 2 0 1/2 1200 x3 1/8 1/4 0 1 1/2 1/4 1/8 Z′ 1400 0 0 0 400 400 200 Chapter 2 靈敏度分析 所以， X*=（ 0， 3/2， 1/8， 0 . 0 . 0） Z′* =－ 1400， 原問題 Z* =1400 其對(duì)偶問題的最優(yōu)解為： Y*= (400， 200)， W*= 1400 58 一個(gè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題可由約束矩陣 Ａ ， 右端項(xiàng)向量 b， 和價(jià)值向量 Ｃ 完全確定 ， 假如一個(gè)線性規(guī)劃問題對(duì)于給定的數(shù)據(jù)集合 Ａ ， b， Ｃ 有最優(yōu)解 ， 則最優(yōu)解 。 因此，對(duì)偶單純形法一般不單獨(dú)使用。 4 對(duì)偶單純形法 對(duì)偶單純形法與原始單純形法內(nèi)在的對(duì)應(yīng)關(guān)系 原始單純形法 對(duì)偶單純形法 前提條件 所有 bi≥0 所有 bi≥0? 最優(yōu)性檢驗(yàn) 所有 0j? ?0?j? ?所有 換入、出基 變量的確定 先確定換入基變量 后確定換出基變量 先確定換出基變量 后確定換入基變量 原始基本解的進(jìn)化 可行 最優(yōu) 非可行 可行 (最優(yōu) ) ???????????????0,43232432m i n321321321321xxxxxxxxxxxxZ練習(xí)： ????????????????????????)( 04 323 2432m a x5153214321321jxxxxxxxxxxxxZcj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 3 1 2 1 1 0 0 x5 4 2 1 3 0 1 Z 2 3 4 0 0 i?cj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 1 0 5/2 1/2 1 1/2 2 x1 2 1 1/2 3/2 0 1/2 Z 0 4 1 0 1 i?cj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 3 x2 2/5 0 1 1/5 2/5 1/5 2 x1 11/5 1 0 7/5 1/5 2/5 Z 28/5 0 0 3/5 8/5 1/5 i?Y=（ 8/5 . 1/5） X=（ 2/5 . 11/5 . 0） Z =28/5 ?對(duì)偶單純形法的優(yōu)點(diǎn)： ? 不需要人工變量； ? 當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)； ? 在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。否則 ,若有akj’0 則選 ?=min{?j’ / akj’┃ akj’0}=?r’/akr’那么 xr為換入變量 ,轉(zhuǎn) 4； akr’為主元素 ,作矩陣行變換使其變?yōu)?1,該列其他元素變?yōu)?0,轉(zhuǎn) 2。 Chapter 2 靈敏度分析 對(duì)偶單純形法求解線性規(guī)劃問題過程： ,對(duì)應(yīng)一個(gè)基本解 ,所有檢驗(yàn)數(shù)均非正 ,轉(zhuǎn) 2； b’≥0, 則得到最優(yōu)解 ,停止 。 ?這樣的優(yōu)點(diǎn)在于 ， ?一是當(dāng)問題的模型中存在“ =”的約束條件時(shí)，不需要引入人工變量，只要在約束條件方程的兩邊乘以“ 1”后加入松弛變量，再按單純形法求解。 4 對(duì)偶單純形法 對(duì)偶單純形法的基本思路是： 在迭代過程中 ， 始終保持對(duì)偶問題解的可行性 ， 而原問題的解由不可行逐漸向可行性轉(zhuǎn)化 ， 一旦原 問題的解也滿足了可行性條件 ,也就達(dá)到了最優(yōu)解 。 同原始單純形求法一樣，求解對(duì)偶問題（ D），也可以從（ D）的一個(gè)基本可行解開始，從一個(gè)基本可行解（迭代）到另一個(gè)基本可行解，使目標(biāo)函數(shù)值減少。 對(duì)偶單純形法并不是求解對(duì)偶問題解的方法，而是利用對(duì)偶理論求解原問題的解的方法。 第二節(jié) 影子價(jià)格 Chapter 2 靈敏度分析 第三節(jié) 對(duì)偶單純形法 ?對(duì)偶單純形法是求解線性規(guī)劃的另一的基本方法。 ?????????????????????無約束321321321321321,0,04 16 3253234m a xxxxxxxxxxxxxxxxZChapter 2 靈敏度分析 ??????????????????????無約束321321321321321,0,03654 3 132 42m i nyyyyyyyyyyyyyyyW解 : 將 X* =（ 0 , 0 , 4）代入原問題中，有下式： Chapter 2 靈敏度分析 ??????????????????4 4 1 246 32 20532321321321xxxxxxxxx所以，根據(jù)互補(bǔ)松弛條件，必有 y*1= y*2=0，代入對(duì)偶問題 （ 3）式， y3 =3。因?yàn)槟膫€(gè)問題是原問題，哪個(gè)問題是對(duì)偶問題是相對(duì)而言的。 B此句為 A的逆否命題，所以也不對(duì)。 Chapter 2 靈敏度分析 ?解： A不對(duì)。（強(qiáng)對(duì)偶性） 性質(zhì) 6:互補(bǔ)松弛定理 設(shè) X*和 Y*分別是問題 P 和 D 的可行解，則它們分別是最優(yōu)解的充要條件是 剩余變量或或ssssYXXYXCAYXYAXbY.00)(00)( ????????????????? 同時(shí)成立 Chapter 2 靈敏度分析 例題判斷下例說法是否正確，為什么？ A 如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶 問題也一定存在可行解 B 如果線性規(guī)劃的對(duì)偶問題無可行解，則原問
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1