運籌學(xué)二章對偶線性規(guī)-在線瀏覽
2025-07-13 15:18本頁面
【正文】 1 1/3 15 y1 1/5 1 2/5 1/5 0 1/5 0 5/2 σj 0 6M18 M2 M 3 0 24 y2 1/3 0 1 1/6 1/6 0 1/6 2 15 y1 1/5 1 0 2/15 1/15 1/5 1/15 1/2 σj 0 0 1 3 3 M+8 24 y2 1/4 5/4 1 0 1/4 1/4 1/2 5 y3 1/2 15/2 0 1 1/2 3/2 3 σj 15/2 0 0 7/2 3/2 M3 ① ② Z*= W*= 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 6 二、對偶問題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取 Max時均取 “ ≤” 號；當(dāng)目標(biāo)函數(shù)求 Min值時均取“ ≥“ 號。2021/6/16 1 第二章 對偶理論與靈敏度分析 線性規(guī)劃的對偶問題 對偶問題的基本性質(zhì) 影子價格 對偶單純形法 靈敏度分析 DUAL 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 2 本章學(xué)習(xí)要求 ?掌握對偶理論及其性質(zhì) ?掌握影子價格的應(yīng)用 ?掌握對偶單純形法 ?熟悉靈敏度分析的概念和內(nèi)容 ?掌握右側(cè)常數(shù)，價值系數(shù)，工藝系數(shù)的變換對原最優(yōu)解的影響 ?掌握增加新變量和增加新約束條件對原最優(yōu)解的影響，并求出相應(yīng)因素的靈敏度范圍 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 3 ?問題的提出 ?對稱形式下對偶問題的一般形式 ?非對稱形式下的原問題與對偶問題的關(guān)系 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 4 一、對偶問題的提出 每一個 LP問題，都伴隨著另一個 LP，而且二者有密切關(guān)系，互為對偶，另其中一個問題為原問題，另一個問題為對偶問題，只要得到了其中一個問題的解（目標(biāo)值），也得到另一問題的解，因此通常只求解一個問題就可以了。 例 1：（美佳公司） ① 美佳公司應(yīng)如何生產(chǎn)安排，使已有資源利潤最大化。則稱這些線性規(guī)劃問題具有對稱性。兩個問題中的任一個都可以作為原始問題。 根據(jù)定義寫出對偶問題 根據(jù)定義寫出對偶問題 max u=6w1+9w2 . w1+2w2≤2 2w1 3w2≤3 w1+2w2≤1 w1, w2≥0 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 11 對偶問題的性質(zhì)總結(jié) 對偶的對偶就是原始問題 max z=CX . AX≤b X ≥0 min w=Y’b . ATY ≥ C’ Y≥0 對偶的定義 max u=CW . AW≤C W ≥0 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 12 maxZ=x1+4x2+2x3 . 5x1x2+2x3≤8 x1+3x23x3≤5 x1,x2,x3≥0 minw=8y1+5y2 . 5y1+y2≥1 y1+3y2≥4 2y13y2 ≥2 y1,y2≥0 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 13 三、非對稱形式的原 — 對偶問題 minz=2x1+3x25x3+x4 . x1+x23x3+x4≥5 2x1 +2x3x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0 minz=2x1’+3x25x3+(x4’x4”) ’+x23x3+(x4’x4”)≥5 2x1’ 2x3+(x4’x4”)≥4 x2+x3 +(x4’x4”) ≥6 x2x3(x4’x4”) ≥6 x1’,x2,x3 ,x4’,x4” ≥0 變?yōu)閷ΨQ形式 y1 y2’ y3’ y3” maxw=5y14y2’+6(y3’y3”) +2y2’ ≤2 y1 +(y3’y3”) ≤3 3y12y2’+(y3’y3”) ≤ 5 y1+y2’+(y3’y3”) ≤ 1 y1y2’(y3’y3”) ≤ 1 y1,y2’ ,y3’,y3”≥0 寫出對偶問題 maxw=5y1+4y2+6y3 . y1+2y2 ≥2 y1 +y3 ≤3 3y1+2y2+y3 ≤ 5 y1 y2 +y3 = 1 y1≥0 ,y2≤0,y3無約束 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 14 結(jié)論 LP(LD) Max X≥0 X≤0 X無約束 St ≤ st ≥ St= LD(LP) Min st ≥ St ≤ St= Y≥0 Y≤0 Y無約束 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 15 min z= 2x1+4x2x3 . 3x1 x2+2x3 6 x1+2x23x3 12 2x1+x2+2x3 8 x1+3x2x3 15 max w=6y1+12y2+8y3+15y4 . 3y1 y2+2y3+ y4 2 y1+2y2+ y3+3y4 4 2y1 3y2+2y3 y4 1 y1 0,y2 ,y3 0,y4 0 ≤≥ = ≥ Free ≤ ≥ ≥ = ≤ ≥ x1≥0 x2≤0 x3: Free ?原始問題變量的個數(shù) (3)等于對偶問題約束條件的個數(shù) (3)； ?原始問題約束條件的個數(shù) (4)等于對偶問題變量的個數(shù) (4)。 ?原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。 0)PB()PB( )bB(m i n ik1ik1i1?? ????j1Bjj PBcc ????當(dāng) B為最優(yōu)基時 MaxZ=CBB1b＋（ CNCBB1N)XNCBB1XS ??????????????????????????????????????????????0BC0AB0BC0N)( B ,B0BC0N)BC,()C,(00BC0NBCC1B11B11B1BN1B1BNBBBBBBCCC
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1