運(yùn)籌學(xué)第二章ppt課件-閱讀頁(yè)
2025-05-27 13:31本頁(yè)面
【正文】 2 = 5 5 = 互補(bǔ)松弛性 ?當(dāng)原問(wèn)題約束 bi， xsi0,則yi=0 未充分利用。資源得到充分利用，即 xsi=0。 市場(chǎng)價(jià)格是已知數(shù)，相對(duì)穩(wěn)定。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等的變化而變化。 ■ 影子價(jià)格越小，說(shuō)明增加這種資源越帶來(lái)的 z增加越少， 該資源是相對(duì)不緊缺的。 隱含成本 利潤(rùn) 差額成本 1 1 2 21 1 1 2 1 2 1 1 11 2 1 2 2 2 2 2 21 1 2 21 2 1 2m i n. . y y y yy y y yy y y yy y y y y y 0mmm m mm m mn n m n m m n nm m m m ny b w b w b ws t a a a ca a a ca a a c???? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ??產(chǎn)品的差額成本（ Reduced Cost） 差額成本 =機(jī)會(huì)成本 利潤(rùn) 1 1 2 2 jy ( y y y ) Y Tm j j j m m j j j ja a a c a c ?? ? ? ? ? ? ? ? ? ?第四節(jié) 對(duì)偶單純形法 C CB CN 0 CB XB b X1 X2 Xs CB Xs B1b B1B B1N B1I σ 0 CNCBB1N CBB1 對(duì)于單純形法疊代過(guò)程本質(zhì) ： 1）確保 z變大； 2） B1b ≥0 由對(duì)偶理論知道，當(dāng)原問(wèn)題為最優(yōu)解時(shí)， σ ≥0 且 為對(duì)偶問(wèn)題的最優(yōu)解，因此人們提出對(duì) 偶單純形法。不失一般性，令 B=（ P1,P2,… ,Pm） ,它對(duì)應(yīng)的變量為 XB=(x1,x2,… ,xm) 當(dāng)非基變量都為 0時(shí)，可以得到 XB= B1b中至少有一個(gè)負(fù)分量，設(shè)（ B1b） I0,并且在單純形表的檢驗(yàn)數(shù)行中得檢驗(yàn)數(shù)都為非正，即對(duì)偶問(wèn)題保持可行解。 對(duì)偶單純形法的計(jì)算步驟： （ 1）根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表。停止計(jì)算。 （ 2） 確定換出變量按 對(duì)應(yīng)的基變量 xl為換出變量。 | b 39。iii ?? （ 3） 確定換出變量 在單純形表中檢查 xl所在行的各系數(shù) alj≥0, 則無(wú)可行解。 若存在 alj0(j=1,2,… ,n),計(jì)算 按 θ 規(guī)則所對(duì)應(yīng)的列的非基變量 xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍然為可行解。= 15 y1 24y2 5y3 max st . 6y2 + y3 – y4 = 2 5y1 + 2y2 + y3 – y5 1 = y1, y2, y3, y4, y5 = 0 C 15 24 5 0 0 M M θ CB YB b y1 y2 y3 y4 y5 y6 y7 M M y6 y7 2 1 0 6 1 1 0 1 0 5 2 1 0 1 0 1 Σ M15 8M24 2M5 M M 0 0 例一 6y2 + y3 ≥ 2 5y1 + 2y2 + y3 1 ≥ z= 15 y1 + 24y2 + 5y3 min y1 , y2 , y3 ≥ 0 st . z39。 當(dāng)變量個(gè)數(shù)多于約束條件個(gè)數(shù)，對(duì)這樣的線性規(guī)劃問(wèn)題，用對(duì)偶單純形法可以減少計(jì)算的工作量。 在靈敏度分析中 ,有時(shí)需要用對(duì)偶單純形法，可使問(wèn)題的處理簡(jiǎn)化。 第五節(jié) 靈敏度分析 靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度的分析。 一、目標(biāo)函數(shù)中價(jià)值系數(shù) cj的變化分析 可以分別就 cj時(shí)對(duì)應(yīng)的非基變量和基變量?jī)煞N情況來(lái)討論。 下面就各種情況分別進(jìn)行討論。因 cr∈C B,當(dāng) cr變化 Δcr時(shí)，就引起 CB的變化，這時(shí) ? (CB+ΔCB)B 1A=CB B1A+(0,… , Δcr, … ,0) B1A ? = CB B1A+Δcr(ar1,ar2, … ,arn) ? 可見(jiàn)當(dāng) cr變化 Δcr 時(shí)，最終表中的檢驗(yàn)數(shù)是 ? σj ’=cj CBB1AΔcjarj ’,j=1,2,… ,n ? 若要求原最優(yōu)解不變，即必需滿足 σ j’≤0 。這樣使原問(wèn)題的解變?yōu)? XB’=B1(b+Δb) 這里 Δb= （ 0， … ， Δb r， 0， … ， 0） XB’ ≥0 ，最終表的檢驗(yàn)數(shù)不變，則最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以 XB’為新的最優(yōu)解。 B1(b+Δb)= B1b+ B1Δb = B1b+ B1 ， B1 ?????????????????00??rb???????????????????????????????????????????????????????????????mrirrrrmrrirrrraaabbababab??????1100這時(shí)在最終表中求得的 b列的所有元素 ， 由此得 當(dāng) 例題見(jiàn) P65 mibab riri ,2,1,0 ?????mibba irir ,2,1, ?????于是得到時(shí)， 。/0 iririr abba ???? 時(shí)，}0|/{m i n}0|/{m a x ??????? iririiriririiaabbaab三、 技術(shù)系數(shù) aij的變化 分兩種情況來(lái)討論技術(shù)系數(shù) aij的變化
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1