運(yùn)籌學(xué)對(duì)偶靈敏ppt課件(完整版)
【正文】 4 0 0 2 2 1/2 1 2 3 x2 2 0 1 1/4 1/2 1/8 0 8 z 14 0 0 5/4 3/2 1/8 0 2 x1 1 1 0 0 4/3 1/8 3/4 0 x3’ 2 0 0 1 1 1/4 1/2 3 x2 3/2 0 1 0 3/4 3/16 1/8 z 0 0 0 1/4 7/16 5/8 x3’換入， x5換出。 ?例 8： 第 1章例 1的最終單純形表 (P32) ? 討論基變量的價(jià)值系數(shù) c2在什么范圍內(nèi)變化，可以保持最優(yōu)解不變。 因此， 要使現(xiàn)行最優(yōu)基 B仍為最優(yōu)基， 只需使 改變后的 cj仍滿足 σj≤ 0。 當(dāng) aij， bi， cj這些參數(shù)中的某一個(gè)發(fā)生變化時(shí)，問(wèn)題的最優(yōu)解會(huì)有什么變化呢？ 第 7節(jié) 靈敏度分析 (Sensitivity Analysis) max z = c1x1 + c2x2 +…+ c nxn . a11x1+a12x2+…+ a1n xn =b1 a21x1+a22x2+…+ a2n xn = b2 … … … … am1x1+am2x2+…+ amn xn = bm x1, x2, …, x n≥0 ? 靈敏度分析 (Sensitivity Analysis)是對(duì)系統(tǒng)因環(huán)境變化顯示出來(lái)的敏感程度 的分析。 2. 但是，當(dāng)原問(wèn)題所獲得的基解為可行解時(shí)，則這個(gè)基可行解就是原問(wèn)題最優(yōu)解。否則，可出售這種資源，從而在生產(chǎn)上獲得利潤(rùn)。 。 ?因此，原問(wèn)題 (1)不可能有最優(yōu)解，但是，原問(wèn)題 (1)有可行解， ?所以原問(wèn)題 (1)無(wú)有限最優(yōu)解，即目標(biāo)函數(shù)無(wú)上界。 原問(wèn)題的變量 基變量 XB 非基變量 XN 松弛變量 Xs 對(duì)應(yīng)于可行基 B的檢驗(yàn)數(shù) 0 CNCBB1N CBB1 對(duì)偶問(wèn)題的變量 Ys1 Ys2 Y ? 表 35的進(jìn)一步說(shuō)明：用單純形法求解 LP問(wèn)題時(shí)，原問(wèn)題的 檢驗(yàn)數(shù)行的各檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)基解，它們之間僅差一個(gè)負(fù)號(hào)。 ?另外，原問(wèn)題獲得最優(yōu)解時(shí)，其松弛變量對(duì)應(yīng)的檢驗(yàn)數(shù)的相反數(shù) CBB1 ，就是對(duì)偶問(wèn)題的最優(yōu)解。 ?證明：（略） ?從弱對(duì)偶性可知，原問(wèn)題 (極大化問(wèn)題 )的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)下界。 ?對(duì)偶問(wèn)題 (極小化問(wèn)題 )的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其原問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界。該性質(zhì)常被稱為 主對(duì)偶定理 。 ? 在單純形表中， 原問(wèn)題的松弛變量 (Xs)對(duì)應(yīng)于對(duì)偶問(wèn)題的變量 (Y)， 對(duì)偶問(wèn)題的剩余變量 (Ys Ys2)分別對(duì)應(yīng)于原問(wèn)題的變量 (XB、 XN) — 利用這種對(duì)應(yīng)關(guān)系， 只需求解其中一個(gè)問(wèn)題，就可以 從 原問(wèn)題 最終單純形表中同時(shí)得到其對(duì)偶問(wèn)題的最優(yōu)解 ，而不須求解過(guò)程。 ? 對(duì)偶問(wèn)題的解在經(jīng)濟(jì)學(xué)上稱為原問(wèn)題的資源的影子價(jià)格，為什么呢？ ? 單純形表中目標(biāo)值為： z = CBB1b ? 檢驗(yàn)數(shù)為： σN= CN－ CBB1N ? 其中都有乘子 Y=CBB1， Y的經(jīng)濟(jì)學(xué)意義是什么？ 第 5節(jié) 影子價(jià)格（ shadow price） ? 假設(shè) X*和 Y*分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，由主對(duì)偶定理，相應(yīng)的目標(biāo)函數(shù)值相等，即： ? z*=CX*=Y*b=ω* ),...,(*2*1***mi bzbzbzzgr ady????????),...,2,1(1** miBCbzyB ????? ??因此， y*i實(shí)際上表示原問(wèn)題約束條件中第 i種資源增加一個(gè)單位時(shí)，目標(biāo)函數(shù)最優(yōu)值的改變量。 max Z = 2x1 + 3x2 x1 + 2x2 ≤8 4x1 ≤16 4x2 ≤12 x1≥0， x2 ≥ 0 . x2 x1 O 1 1 2 2 3 3 4 4 x1+2x2=8 4x1=16 4x1=12 Q1 Q2 Q3 Q4 ? 圖 31， y1*=3/2， y2*=1/8， y3*=0。 第 6節(jié) 對(duì)偶單純形法 ?對(duì)偶單純形法并不是解對(duì)偶問(wèn)題的單純形法，而是根據(jù)對(duì)偶問(wèn)題的特點(diǎn)和對(duì)稱性，設(shè)計(jì)出的一種解法。 ? 在具體求解過(guò)程中， 對(duì)偶單純形法是在原問(wèn)題的單純形表上進(jìn)行對(duì)偶處理的 。 ? 在線性規(guī)劃中討論靈敏度分析，目的是描述一種能確定模型結(jié)構(gòu)中元素變化對(duì)問(wèn)題最優(yōu)解影響的分析方法。 目標(biāo)函數(shù)中價(jià)值系數(shù) cj發(fā)生改變 ?即 cjCBB1pj≤0 ?或 cj≤ CBB1pj ?其中， cj為改變后的目標(biāo)函數(shù)中的非基變量?jī)r(jià)值系數(shù)。 cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 2 1/2 1 3 x2 2 0 1 1/2 1/8 0 z 14 0 0 3/2 1/8 0 max z = 2x1 + 3x2 x1 + 2x2 ≤8 4x1 ≤16 4x2 ≤12 x1≥0， x2 ≥ 0 ?∵ c2為基變量 x2的價(jià)值系數(shù)， ∴ 若要保持最優(yōu)解不變，只要滿足 σN≤0即可。 ? 用單純形法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1