《運(yùn)籌學(xué)對(duì)偶靈敏》ppt課件(文件)
【正文】 “ ≤” “ = ” ?原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系 在形式上可歸結(jié)為表 對(duì)偶問(wèn)題的基本性質(zhì) ?原問(wèn)題： ?對(duì)偶問(wèn)題： minω = Yb AT Y≥CT Y≥0 max Z = CX AX≤b X≥0 ? (1). 對(duì)稱性： 對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題。 ?對(duì)偶問(wèn)題 (極小化問(wèn)題 )的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其原問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界。 ?證明：（略） ? (4). 最優(yōu)性： 設(shè) X、 Y分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則當(dāng) CX=Yb時(shí)， X、 Y分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解 X*、 Y* 。該性質(zhì)常被稱為 主對(duì)偶定理 。 ?證明：（略） ? 從性質(zhì) 7可知，用單純形法求解 LP問(wèn)題時(shí)，迭代的每一步在得到原問(wèn)題的一個(gè)基可行解的同時(shí)，其 檢驗(yàn)數(shù)行的各檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)基解，它們之間僅差一個(gè)負(fù)號(hào)。 ? 在單純形表中， 原問(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ò)程。 ? max Z = x1 + x2 . x1 + x2 + x3 ≤2 2x1 + x2 x3 ≤ 1 x1， x2 ， x3 ≥ 0 ?解：由于 X=(0,0,0)T滿足 .，所以 X=(0,0,0)T為可行解。 ? 對(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)值的改變量。即y1*=3/2， y2*=1/8， y3*=0。 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。 企業(yè)內(nèi)部可以挖潛的方向。 第 6節(jié) 對(duì)偶單純形法 ?對(duì)偶單純形法并不是解對(duì)偶問(wèn)題的單純形法，而是根據(jù)對(duì)偶問(wèn)題的特點(diǎn)和對(duì)稱性，設(shè)計(jì)出的一種解法。這時(shí)，檢驗(yàn)數(shù)的相反數(shù)即是對(duì)偶問(wèn)題的一個(gè)基可行解。 ? 在具體求解過(guò)程中， 對(duì)偶單純形法是在原問(wèn)題的單純形表上進(jìn)行對(duì)偶處理的 。 ? minω = 2x1 + 3x2 + 4x3 ? x1+2x2 + x3 ≥3 ? 2x1 x2 +3x3 ≥4 ? x1, x2, x3 ≥0 ?上述 LP問(wèn)題的對(duì)偶問(wèn)題： ? max z = 3y1 + 4y2 ? y1+2y2 ≤2 ? 2y1 y2 ≤3 ? y1 +3y2≤4 ? y1, y2≥0 ?從求解過(guò)程可知， 對(duì)偶單純形法的優(yōu)點(diǎn) ： ? (1) 當(dāng)原問(wèn)題的初始解是非可行解，且相應(yīng)的檢驗(yàn)數(shù)都是非正時(shí)，這時(shí)不需要引入人工變量，簡(jiǎn)化計(jì)算。 ? 在線性規(guī)劃中討論靈敏度分析，目的是描述一種能確定模型結(jié)構(gòu)中元素變化對(duì)問(wèn)題最優(yōu)解影響的分析方法。 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 4 0 1 1/2 1/8 0 z 14 0 0 3/2 1/8 0 比值 θ 3/4 — 2 x1 4 1 0 0 1/4 0 0 x3 2 0 0 1 1/4 1/2 3 x2 3 0 1 0 0 1/4 z 17 0 0 0 1/2 3/4 ?x5換出， x4換入。 目標(biāo)函數(shù)中價(jià)值系數(shù) cj發(fā)生改變 ?即 cjCBB1pj≤0 ?或 cj≤ CBB1pj ?其中， cj為改變后的目標(biāo)函數(shù)中的非基變量?jī)r(jià)值系數(shù)。因此， 要使現(xiàn)行最優(yōu)基 B仍為最優(yōu)基，只需使改變后的 cj仍滿足 σN≤ 0。 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1