運籌學——對偶問題(編輯修改稿)
2025-08-28 15:22 本頁面
【文章內(nèi)容簡介】 偶問題 ??????????????),2,1( 0),2,1( bas t .M a x Zi1ij1njxmixxcjnjjnjjj????????????????),2,1( 0),2,1( cas t .M i n Wj1ij1miynjyybimiimiii??第三節(jié) 影子價格 影子價格： yi*是資源 bi的價值一種度量，即對第 i種資源的的估價，這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為 “ 影子價格 ” ?影子價格是不穩(wěn)定的，它隨企業(yè)的產(chǎn)品結(jié)構(gòu)、技術(shù)狀況的變化而變化。 ?影子價格是一種邊際成本。 yi的值相當于在給定的生產(chǎn)條件下， bi每增加一個單位時目標函數(shù) Z的增量。 ?資源的影子價格實際上又是一種機會成本。 ?若生產(chǎn)過程中某種資源未得到充分利用 ,則該種資源的影子價格為零；又當某種資源的影子價格不為零時，表明該種資源在生產(chǎn)過程中已耗費完畢。 1x2xO A B C D E F G 164x 1 ?124 2 ?x82 21 ?? xx??????????????0x,x124x 16 4x82x xs t .3x2xMax Z21212121XB XN CB CN B1N CNCBB1N CB XB CBT XB Cj Xj b δj(cjzj) B1b 0 E ABCC 1Bj ??δB1B CBCBB1B XB xm+1 CB cm+1 0 E B1Pm+1 Cm+1CBB1Pm+1 CB XB CBT XB Cj Xj b δj(cjzj) B1b xn B1Pn … … … … CnCBB1Pn 第四節(jié) 對偶單純形法 第四節(jié) 對偶單純形法 ??????0XbAXs t .CXM ax Z??????0YCYAs t .YbM in WTTTABCC 1Bj ??δ≤0 CABC 1B ?? TT1BT C)B(CA ?? 0BC 1B ??又是對偶問題的可行解T)BC( 1B ??第四節(jié) 對偶單純形法 可行基： 當基 B對應的基本解是可行解時，稱基 B為可行基。 最優(yōu)基： 當基 B對應的基本可行解是最優(yōu)解時，稱基 B為最優(yōu)基。 對偶可行基： 若 CBB1是對偶問題的可行解時，則稱 B為對偶可行基。 對偶單純形法思路： 先找到一個對偶可行基，然后保持基的對偶可行性，逐步迭代直至最終達到基的可行性。 x3 x4 x1 x2 x5 3 0 2 3 0 XB CB b 1 7 1 0 1 1 1 4 0 1 3 9 x4 x5 0 0 3 0 2 3 0 3/4 7/4 1 0 3/4 1/4 0 1 1/4 1/4 9/4 0 5/4 0 3/4 3/4 9/4 x4 x2 0 3 1 2 4/3 1/3 1 0 0 1 1/3 1/3 1 5/3 0 0 1/3 1 2 x1 x2 2 3 3 9/4 [ ] 1 9 [ ] θ Cjzj Cjzj Cjzj B1＝（ P4， P5） B2＝（ P4， P2） B3＝（ P1， P2） 是可行基，不是對偶可行基 是可行基，不是對偶可行基 是可行基，也是對偶可行基 是最優(yōu)基 1 1 1 0 1 4 0 1 2 3 x3 x4 0 0 3 9 0 0 3 9 0 0 x1 x2 x3 x4 3 9/4 3/4 0 1 1/4 1/4 1 0 1/4 5/4 3/4 x3 x2 0 9 3/4 0 0 9/4 1 9 1 0 4/3 1/3 0 1 1/3 1/3 5/3 1/3 x1 x2 3 9 0 0 1 2 CB XB b cjzj [ ] cjzj [ ] cjzj ????????????0x,x34xx2 xxs t .9x3xM in W21212121???????????????0x,x,x,x3x 4xx2 x xxs t .9x3xM i n W43214213212139。?????????????????0x,x,x,x3x 4xx2 x xxs t .9x3xM in W43214213212139。第四節(jié) 靈敏度分析 一、什么是靈敏度分析 第一類： 當系數(shù) A、 b、 C發(fā)后改變時，目前最優(yōu)基是否還是最優(yōu)。 第二類： 為保持目前最優(yōu)基還是最優(yōu)，系數(shù) A、 b、 C的允許變化范圍是什么。 A：代表企業(yè)的技術(shù)狀況 b：代表企業(yè)的資源狀況 C：代表企業(yè)產(chǎn)品的市場狀況 ??????0XbAXs t .CXM ax Z第四節(jié) 靈敏度分析 二、靈敏度分析的類型： ?目標函數(shù)中價值系數(shù) C的變化（基變量價值系數(shù)變化；非基變量價值系數(shù)變化） ?右端資源常數(shù) b變化 ?增加一個變量 ?增加一個約束 ?技術(shù)系數(shù) A發(fā)生變化 第四節(jié) 靈敏度分析 XB XN CB CN CBCBB1B B1B B1N CNCBB1N CB XB CBT XB Cj Xj b δj(cjzj) B1b XB xm+1 CB cm+1 CBCBB1B B1B B1Pm+1 Cm+1CBB1Pm+1 CB XB CBT XB Cj Xj b δj(cjzj) B1b xn B1Pn CnCBB1Pn … … … … 第四節(jié) 靈敏度分析 價值系數(shù) C發(fā)生改變 CN中某個 Cj發(fā)生變化時，只影響 xj的檢驗數(shù)，且 δj＝ cjCBB1Pj，若cj的變化滿足 δj(cjzj)≤0，則目前解還是最優(yōu)；否則就不是最優(yōu)，繼續(xù)單純形迭代就可以求得新的最優(yōu)解。 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4/3 1/3 0 1 2 1/3 1/3 1 2 x1 x2 2 3 0 0 1 5/3 1/3 CB XB b δj(cjzj) 例：對于下例問題，討論 c3范圍
試題試卷相關(guān)推薦
鄂ICP備17016276號-1