運(yùn)籌學(xué)課件第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析-wenkub.com
2025-05-10 22:15 本頁面
【正文】 運(yùn)籌學(xué)教程 ? 小結(jié) ? 對(duì)偶問題的基本性質(zhì)。y10 ?????????????????0142232.1610m i n2121212121yyyyyyystyyW運(yùn)籌學(xué)教程 ?????????????????0142232.1610m i n2121212121yyyyyyystyyWx1=60。 X’,Y’分別為原問題和對(duì)偶問題的可行解 CX’ ≤ CX* ≤ Y*b≤Y’ b=CX’ CX’ =CX* = Y*b=Y’ b 運(yùn)籌學(xué)教程 強(qiáng)對(duì)偶性 若原問題和對(duì)偶問題兩者均具有可行解，則兩者均有最優(yōu)解，且此時(shí)目標(biāo)函數(shù)值相同。 ?關(guān)于最優(yōu)解無界情況與對(duì)偶問題的關(guān)系； 推論 2 若原問題可行，則其目標(biāo)函數(shù)無界的充要條件是對(duì)偶問題沒有可行解。 定理 1 弱對(duì)偶定理 —— 若一對(duì)對(duì)稱形式的對(duì)偶線性規(guī)劃 ??????0..XbAXtsCXM a x Z（ L） ??????0..YCYAtsbYM in W和 （ D） 均有可行解 ， 分別為 和 ， 則 C ≤ b。 1/2 DUAL 剩余變量 DUAL 變量 y4 y5 y1 y2 y3 項(xiàng)目 dual變量 dual剩余變量 y1 y2 y3 y4 y5 y2 1/4 y3 1/2 5/4 1 0 15/2 0 1 1 /4 188。 令 :CBCBI=0 (2) (1)+(2)得到 CNCB B1 N +CBCBI= CNCB B1 N +CBCBB1B =CB+CNCBB1(B+N)=CCBB1A ≤0 CB B1 ≤0。332239。33222239。33322339。3339。33239。 設(shè) y1,y2， y3為代表單位時(shí)間這三種資源的出讓價(jià)格，為了使工廠出讓資源合算，顯然應(yīng)該使出讓原來生產(chǎn)一件產(chǎn)品 Ⅰ的資源所得收入不低于自己生產(chǎn)產(chǎn)品 Ⅰ 的利潤，即 0y1+6y2+1y3 ≥2 對(duì)于產(chǎn)品 Ⅱ ，同樣可以建立類似的約束條件 5y1+2y2+1y3≥1 項(xiàng)目 產(chǎn)品 Ⅰ 產(chǎn)品 Ⅱ 每天可用能力 設(shè)備 A(h) 設(shè)備 B(h) 調(diào)試工序 (h) 0 6 1 5 2 1 15 24 5 利潤 (元 ) 2 1 y1 y2 y3 運(yùn)籌學(xué)教程 當(dāng)原問題和對(duì)偶問題都取得最優(yōu)解時(shí)，這一對(duì)線性規(guī)劃對(duì)應(yīng)的目標(biāo)函數(shù)值是相等的： Zmax=Wmin 顯然在滿足這兩個(gè)約束的前提下，價(jià)格越高，該工廠越合算，但價(jià)格太高，投資人方面又不會(huì)愿意購買。 min W =120y1 + 50y2 . 4y1+2y2 ≥ 50 3y1+ y2 ≥ 30 y1， y2 ≥ 0 對(duì)偶線性規(guī)劃問題，記為（ D） 桌子 椅子 能力 木工 4 3 120 漆工 2 1 50 價(jià)格 50 30 運(yùn)籌學(xué)教程 線性規(guī)劃的對(duì)偶理論 王老板按（ D） 的解 y1 、 y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金 W最少）。只是 …... 家具 王 總 李 總 桌子 椅子 能力 木工 4 3 120 漆工 2 1 50 價(jià)格 50 30 運(yùn)籌學(xué)教程 線性規(guī)劃的對(duì)偶理論 王老板的 家具生產(chǎn)模型 ： x1 、 x2是桌、椅生產(chǎn)量。咋樣？價(jià)格嘛 …… 好說， 肯定不會(huì)讓您兄弟吃虧訕。運(yùn)籌學(xué)教程 第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析 運(yùn)籌學(xué)教程 一、對(duì)偶問題的提出 對(duì)偶思想舉例 周長一定的矩形中 ， 以正方形面積最大；面積一定的矩形中 ， 以正方形周長最??； 第一節(jié) LP的 對(duì)偶問題 運(yùn)籌學(xué)教程 3 對(duì)偶 理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎(chǔ)。 王老板做家具賺了 大錢，可惜我老李有 高科技產(chǎn)品，卻苦于沒有 足夠的木工和油漆工 咋辦？只有租咯。 Z是家具銷售總收入（總利潤）。 按時(shí)下最流行的一個(gè)詞，叫什么來著 ———— 運(yùn)籌學(xué)教程 對(duì)偶問題 Min w=YbT=YTb . ATY ≥ CT Y ≥0 原始問題 max z=CX . AX ≤ b X ≥0 ≤ max b A C CT AT bT ≥ min m n m n 運(yùn)籌學(xué)教程 換個(gè)角度審視生產(chǎn)計(jì)劃問題 例 要求制定一個(gè)生產(chǎn)計(jì)劃方案，在設(shè)備A,B和調(diào)試三種資源限制下，使
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1