對(duì)偶線性規(guī)劃ppt課件(已修改)
2024-11-15 20:15 本頁(yè)面
【正文】 第二章 線性規(guī)劃的對(duì)偶理論及其應(yīng)用 窗含西嶺千秋雪，門(mén)泊東吳萬(wàn)里船 對(duì)偶是一種普遍現(xiàn)象 2 線性規(guī)劃的對(duì)偶理論 線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)形式 ? 任何線性規(guī)劃問(wèn)題都有其對(duì)偶問(wèn)題 ? 對(duì)偶問(wèn)題有其明顯的經(jīng)濟(jì)含義 ??????????????????0, B15232A 25322..432)(m a x 4321432143214321xxxxxxxxxxxxtsxxxxxf資源資源例 假設(shè)有商人要向廠方購(gòu)買(mǎi)資源 A和 B，問(wèn)他們談判原料 價(jià)格的模型是怎樣的？ 3 例 – 設(shè) A、 B資源的出售價(jià)格分別為 y1 和 y2 – 顯然商人希望總的收購(gòu)價(jià)越小越好 – 工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少 ????????????????????0, 4 423 3 332 2 22 1 12..2121212121yyyyyyyyyyts的所得產(chǎn)品的所得產(chǎn)品的所得產(chǎn)品的所得產(chǎn)品目標(biāo)函數(shù) min g(y)=25y1+15y2 ??????????????????0, B15232A 25322..432)(m a x4321432143214321xxxxxxxxxxxxtsxxxxxf資源資源4 線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)形式 ??????0XbAXCX..)(m a x :tsxf原問(wèn)題??????0YCYAYb..)(m i n :tsyg對(duì)偶問(wèn)題TmnmTnbbbcccyyyxxx),(),(),(),(21212121????????bCYX上兩式中???????????????mnmmnnaaaaaaaaaA???????2122221112115 線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)形式 ??????????????????????????0,..)(m i n21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybybyg??????把對(duì)偶問(wèn)題展開(kāi)??????0YCYAYbYTTTTTtsg..)(m i n :對(duì)偶問(wèn)題習(xí)慣寫(xiě)為6 (max,?)標(biāo)準(zhǔn)型的對(duì)偶變換 ? 目標(biāo)函數(shù)由 max 型變?yōu)? min 型 ? 對(duì)應(yīng)原問(wèn)題每個(gè)約束行有一個(gè)對(duì)偶變量 yi， i=1,2,…, m ? 對(duì)偶問(wèn)題約束為 ? 型，有 n 行 ? 原問(wèn)題的價(jià)值系數(shù) C 變換為對(duì)偶問(wèn)題的右端項(xiàng) ? 原問(wèn)題的 右端項(xiàng) b 變換為對(duì)偶問(wèn)題的 價(jià)值系數(shù) ? 原問(wèn)題的技術(shù)系數(shù)矩陣 A 轉(zhuǎn)置后成為對(duì)偶問(wèn)題的技術(shù)系數(shù)矩陣矩陣 ? 原問(wèn)題與對(duì)偶問(wèn)題互為對(duì)偶 – 對(duì)偶問(wèn)題可能比原問(wèn)題容易求解 – 對(duì)偶問(wèn)題還有很多理論和實(shí)際應(yīng)用的意義 7 非標(biāo)準(zhǔn)型的對(duì)偶變換 ?????????????????0,510342023..54)(m a x 1221212121xxxxxxxxtsxxxf不限原線性規(guī)劃問(wèn)題例????????????????????????????????????????????????0, 551033420223..554)(m a x)( m a x , 221221221221221221xxxxxxxxxxxxxxxtsxxxxf型標(biāo)準(zhǔn)問(wèn)題化為??????????????????????????0,532532443..551020)(m i n 43214321432143214321wwwwtswwh則應(yīng)用標(biāo)準(zhǔn)型對(duì)偶變換規(guī)???????????????????????不限經(jīng)整理得令32143213213214332211,0,0532443..51020)(m i n:, yyywyyyyyytsyyyygwwywywy8 表 對(duì)偶變換的規(guī)則 ? 約束條件的類(lèi)型與非負(fù)條件對(duì)偶 ? 非標(biāo)準(zhǔn)的約束條件類(lèi)型對(duì)應(yīng)非正常的非負(fù)條件 ? 對(duì)偶變換是一一對(duì)應(yīng)的 原問(wèn)題 ( m a x , ? ) 對(duì)偶問(wèn)題 ( m i n , ? )技術(shù)系數(shù)矩陣 A ? 技術(shù)系數(shù)矩陣 AT價(jià)值系數(shù) C ? 右端項(xiàng) b右端項(xiàng) b ? 價(jià)值系數(shù) C第 i 行約束條件為 ? 型 ? 對(duì)偶變量 yi ? 0第 i 行約束條件為 ? 型 ? 對(duì)偶變量 yi ? 0第 i 行約束條件為 = 型 ? 對(duì)偶變量 yi ? 不限決策變量 xj ? 0 ? 第 j 行約束條件為 ? 型決策變量 xj ? 0 ? 第 j 行約束條件為 ? 型決策變量 xj ? 不限 ? 第 j 行約束條件為 = 型9 弱 對(duì)偶定理推論 ? max問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶 min問(wèn)題目標(biāo)函數(shù)值的下限； min問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶 max問(wèn)題目標(biāo)函數(shù)值的上限 ? 如果原 max(min)問(wèn)題為無(wú)界解，則其對(duì)偶 min (max)問(wèn)題無(wú)可行解 ? 如果原 max(min)問(wèn)題有可行解，其對(duì)偶 min (max)問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解 10 最優(yōu)解判別 定理 定理 若原問(wèn)題的某個(gè)可行解 X0的目標(biāo)函數(shù)值與對(duì)偶問(wèn)題某個(gè)可行解 Y0的目標(biāo)函數(shù)值相等，則 X0, Y0分別是相應(yīng)問(wèn)題的最優(yōu)解 證 ：由弱對(duì)偶定理推論 1，結(jié)論是顯然的。 即 CX0 = Y0b ? CX, Y0b = CX0 ? Yb 。 證畢 。 主對(duì)偶 定理 定理 如果原問(wèn)題和對(duì)偶問(wèn)題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。 證 ：由弱對(duì)偶定理推論 1可知，原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)有界，故一定存在最優(yōu)解。 現(xiàn)證明定理的后一句話。 11 主對(duì)偶 定理的證明 證 ：現(xiàn)證明定理的后一句話。 設(shè) X0 為原問(wèn)題的最優(yōu)解，它所對(duì)應(yīng)的基矩陣是 B， X0= B?1 b，則其檢驗(yàn)數(shù)滿足 C ? CBB?1A ? 0 令 Y0= CBB?1，則有 Y0 A ? C。 顯然 Y0為對(duì)偶問(wèn)題的可行解。因此有對(duì)偶問(wèn)題目標(biāo)函數(shù)值， g(Y0)=Y0b= CBB?1 b 而原問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值為 f(X0)=CX0= CBB?1 b 故由最優(yōu)解判別定理可知 Y0 為對(duì)偶問(wèn)題的最優(yōu)解。 證畢 。 –該定理的證明告訴我們一個(gè)非常重要的概念： 對(duì)偶變量的最優(yōu)解等于原問(wèn)題松弛變量的機(jī)會(huì)成本 。 –即對(duì)偶變量的最優(yōu)解是原問(wèn)題資源的 影子價(jià)格 12 互補(bǔ)松弛 定理 定理 設(shè) X0, Y0分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解， U0為原問(wèn)題的松弛變量的值、 V0為對(duì)偶問(wèn)題剩余變量的值。 X0, Y0分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分必要條件是 Y0 U
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1