運(yùn)籌學(xué)課件lp對(duì)偶底色修改

第二章對(duì)偶理論第一節(jié)對(duì)偶問題的提出例：產(chǎn)品原材料工時(shí)定額單位產(chǎn)品收益A2210B31.512現(xiàn)有資源300180問1：如何生產(chǎn)使總收益最大？問2：若企業(yè)把資源出租(賣)，應(yīng)如何確定合理的價(jià)格？出租可獲得的收益不得低于自行生產(chǎn)的收益在滿足上述要求的前提下，所定的價(jià)格對(duì)方愿意接受目標(biāo)函數(shù)：約束條件：非負(fù)條件：產(chǎn)品原材料工時(shí)定額單位產(chǎn)品收益A2210B31.512現(xiàn)有資源300180LPDLP2、價(jià)值系數(shù)資源系數(shù)3、資源系數(shù)價(jià)值系數(shù)4、約束方程<=約束方程>=5、目標(biāo)函數(shù)max目標(biāo)函數(shù)min原始問題maxz=CXs.t. AX≤b X≥0對(duì)偶問題minw=Ybs.t.YA≥C Y≥0≥maxbACCTATb≤minmnmn(LP)(DLP)第二節(jié)LP與DLP的對(duì)偶關(guān)系一、對(duì)偶問題的標(biāo)準(zhǔn)形式二、非標(biāo)準(zhǔn)形式的對(duì)偶關(guān)系見表2-4

minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315≥=≤≥x1≥0,x2≤0,x3無非負(fù)要求例：對(duì)偶線性規(guī)劃minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始問題變量的個(gè)數(shù)(3)等于對(duì)偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對(duì)偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對(duì)偶問題約束條件的性質(zhì)，用表示原始問題約束條件的性質(zhì)影響對(duì)偶問題變量的性質(zhì)，用表示第三節(jié)對(duì)偶單純形法一、思路單純形法：迭代過程始終保持B的可行性（最小θ規(guī)則），逐步滿足最優(yōu)性。2.對(duì)偶單純形法：迭代過程始終保持最優(yōu)性（對(duì)偶可行性），再逐步滿足可行性。二、計(jì)算步驟→3、換基迭代1.化標(biāo)準(zhǔn)型,建立初始單純形表4、回到第2步(若所有aij≥0,則該LP無可行解）cj-1-2-3000bcBxBx1x2x3x4x5x6000x4x5x6-11-11001120100-11001-48-2

δj-1-2-3000

θj

→13↑x1x5x6-1001-11-100402111040-11001-2→δj0-3-2-100θj3↑c(diǎn)j-1-2-3000bcBxBx1x2x3x4x5x6-100x1x5x61-11-1000211100-1100144-2

δj0-3-2-100

θj

3

x1x5x2-10-2100-10-16003112001-100-12→δj00-5-10-3

↑練習(xí)cj-3-5-400bcBxBx1x2x3x4x500x4x5-3-1-210-2-3-101-60-b2δj-3-5-400θj→

152↑-30x1x511/32/3-1/300-7/31/3-2/31

2040-b2δj0-4-2-10→↑-30x1x413/21/20-1/207/2-1/21-3/2b2/2δj0-1/2-5/20-3/2*對(duì)偶單純形法的適用前提能解決形如以下的LP問題：判斷下列LP問題適合那種方法求解:（大M法）（大M法）

（對(duì)偶單純形法）

（單純形法）第四節(jié)對(duì)偶問題的經(jīng)濟(jì)解釋一、原始問題是利潤最大化的生產(chǎn)計(jì)劃問題單位產(chǎn)品的利潤產(chǎn)品產(chǎn)量總利潤資源限量單位產(chǎn)品消耗的資源剩余的資源消耗的資源二、對(duì)偶問題資源限量資源價(jià)格總利潤對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（ShadowPrice）原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤maxz=minw三、影子價(jià)格影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0如果資源的影子價(jià)格大于0，最優(yōu)生產(chǎn)計(jì)劃下該種資源全部用完例：下面是一張最優(yōu)單純形表（極大化問題，其中約束條件均為≦，x4,x5,x6為松弛變量）：xBx1x2x3x4x5x6bx1x3x5

11020100110