運(yùn)籌學(xué)對偶靈敏ppt課件(存儲版)
【正文】 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換入。 ? minω = 2x1 + 3x2 + 4x3 ? x1+2x2 + x3 ≥3 ? 2x1 x2 +3x3 ≥4 ? x1, x2, x3 ≥0 ?上述 LP問題的對偶問題： ? max z = 3y1 + 4y2 ? y1+2y2 ≤2 ? 2y1 y2 ≤3 ? y1 +3y2≤4 ? y1, y2≥0 ?從求解過程可知， 對偶單純形法的優(yōu)點(diǎn) ： ? (1) 當(dāng)原問題的初始解是非可行解，且相應(yīng)的檢驗(yàn)數(shù)都是非正時(shí)，這時(shí)不需要引入人工變量，簡化計(jì)算。這時(shí)，檢驗(yàn)數(shù)的相反數(shù)即是對偶問題的一個基可行解。 企業(yè)內(nèi)部可以挖潛的方向。即y1*=3/2， y2*=1/8， y3*=0。 ? 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為可行解。 ?證明：（略） ? 從性質(zhì) 7可知，用單純形法求解 LP問題時(shí)，迭代的每一步在得到原問題的一個基可行解的同時(shí)，其 檢驗(yàn)數(shù)行的各檢驗(yàn)數(shù)對應(yīng)于對偶問題的一個基解，它們之間僅差一個負(fù)號。 ?證明：（略） ? (4). 最優(yōu)性： 設(shè) X、 Y分別是原問題和對偶問題的可行解，則當(dāng) CX=Yb時(shí)， X、 Y分別為原問題和對偶問題的最優(yōu)解 X*、 Y* 。第 3章 對偶理論和靈敏度分析 ?對偶理論 (Dual Theory) ?靈敏度分析 (Sensitivity Analysis) ? 用矩陣形式表示 ? 原問題： ? 對偶問題： minω = Y’b A’Y≥C Y≥0 max Z = CX AX≤b X≥0 項(xiàng)目 原問題 對偶問題 系數(shù)矩陣 A 約束系數(shù)矩陣 約束系數(shù)矩陣的轉(zhuǎn)置 右端常數(shù) b 約束條件的右端項(xiàng)向量 目標(biāo)函數(shù)中價(jià)格系數(shù)向量 系數(shù)列 C 目標(biāo)函數(shù)中價(jià)格系數(shù)向量 約束條件的右端項(xiàng)向量 目標(biāo)函數(shù) max Z = CX minω = Y’b 約束條件 AX≤b A’Y≥C’ 決策變量 X≥0 Y≥0 原問題 (或?qū)ε紗栴} ) 對偶問題 (或原問題 ) max Z minω 約束條件數(shù) m個 第 i個約束條件：“ ≤” “ ≥” “ = ” 對偶變量數(shù) m個 第 i個對偶變量：“ yi≥0” “yi≤0” yi為自由變量 決策變量數(shù) n個 第 j個對偶變量：“ xj≥0” “xj≤0” xj為自由變量 約束條件數(shù) n個 第 j個約束條件：“ ≥” “ ≤” “ = ” ?原問題與對偶問題的關(guān)系 在形式上可歸結(jié)為表 對偶問題的基本性質(zhì) ?原問題： ?對偶問題： minω = Yb AT Y≥CT Y≥0 max Z = CX AX≤b X≥0 ? (1). 對稱性： 對偶問題的對偶問題是原問題。 ?若對偶問題可行，但目標(biāo)函數(shù)無下界，則原問題無可行解。 ? (7). 對應(yīng)性： 原問題對應(yīng)其可行基的檢驗(yàn)數(shù)的相反數(shù)是對偶問題的一個基解。 原問題 對偶問題 有最優(yōu)解 有可行解，但目標(biāo)函數(shù)無界 無可行解 無可行解 有最優(yōu)解 無可行解 有可行解，但目標(biāo)函數(shù)無界 無可行解 ?例 34：求解下列 LP問題。 ? 第 2章例 1的最終單純形表 (P41) ? max z = 2x1 + 3x2 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 ?從最終單純形表可知，第 i種資源的影子價(jià)格就是對應(yīng)的原問題松弛變量的檢驗(yàn)數(shù)的相反數(shù)。 ? 以上可知， 資源的影子價(jià)格 是針對具體生產(chǎn)或具體企業(yè)而言的；它對于擁有資源的決策者有非常重要的作用： ? (1) 影子價(jià)格 ri 0，可 增加這種資源來收益，或降低這種資源的消耗來收益。 ?經(jīng)過迭代，當(dāng)原問題在 單純形表上的全部 檢驗(yàn)數(shù)變成非正時(shí)，得到原問題的最優(yōu)解。 ? minω = y1 + 3y2 . 1/3y1 + 1/3y2 ≥2 1/3y1 + 4/3y2 ≥3 1/3y1 + 7/3y2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1