對(duì)偶問題的分析.ppt

《對(duì)偶問題的分析.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第三章線性規(guī)劃問題的對(duì)偶與靈敏度分析3.1線性規(guī)劃的對(duì)偶問題概念、理論及經(jīng)濟(jì)意義3.2線性規(guī)劃的對(duì)偶單純形法3.3線性規(guī)劃的靈敏度分析本章內(nèi)容重點(diǎn)1線性規(guī)劃原問題例2.1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示。求獲最大利潤(rùn)的方案。產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）150025002一、對(duì)偶問題：它的對(duì)偶問題就是一個(gè)價(jià)格系統(tǒng)，使在平衡了勞動(dòng)力和原材料的直接成本后，所確定的價(jià)格系統(tǒng)最具有競(jìng)爭(zhēng)力若另外一個(gè)工廠要求租用該廠的設(shè)備A、B

2、、C，那么該廠應(yīng)如何確定合理的租金。設(shè)y1，y2，y3分別為每工時(shí)設(shè)備A、B、C的租金。3.1線性規(guī)劃對(duì)偶問題3設(shè)備的租金收入不能低于自己組織生產(chǎn)時(shí)的獲利收入：3y1+2y2≥1500（不少于甲產(chǎn)品的利潤(rùn)）2y1+y2+3y3≥2500（不少于乙產(chǎn)品的利潤(rùn)）用于生產(chǎn)第i種產(chǎn)品的資源轉(zhuǎn)讓收益不小于生產(chǎn)該種產(chǎn)品時(shí)獲得的利潤(rùn)租方希望在滿足上述條件下盡量要求全部設(shè)備的總租金越少越好，即MinW=65y1+40y2+75y34對(duì)偶變量的經(jīng)濟(jì)意義可以解釋為對(duì)工時(shí)及原材料的單位定價(jià)若工廠自己不生產(chǎn)產(chǎn)品A、B和C，將現(xiàn)有的工時(shí)及原材料轉(zhuǎn)而接受外來加工時(shí)，那么上述的價(jià)格系統(tǒng)能保證不虧本又最富有競(jìng)爭(zhēng)力（包工及

3、原材料的總價(jià)格最低）當(dāng)原問題和對(duì)偶問題都取得最優(yōu)解時(shí)，這一對(duì)線性規(guī)劃對(duì)應(yīng)的目標(biāo)函數(shù)值是相等的：Zmax=Wmin=85原問題的對(duì)偶問題DP：MinW=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥06Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤40原問題3x2≤75x1,x2≥0MinW=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500對(duì)偶問題y1,y2,y3≥07原問題求極大化，對(duì)偶問題求極小化從約束系數(shù)矩陣看：一個(gè)模型中為Ａ，則另一個(gè)模型中為AT。一個(gè)

4、模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量。從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換。8對(duì)偶問題與原問題的對(duì)比原問題（對(duì)偶問題）對(duì)偶問題（原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min不同≤0≥約束≥0變量≤不同條件=無約束≥0≥變量≤0約束≤相同無約束條件=9原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinF約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量約束條件數(shù)：n第i

5、個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“=”10例3.1寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型11Maxz=x1-x2+5x3-7x4s.t.x1+3x2-2x3+x4=252x1+7x3+2x4≥-602x1+2x2-4x3≤30x4≥-5x4≤10x1,x2,≥0x3,x4取值無約束12Minf=25y1–60y2+30y3-5y4+10y5s.t.y1+2y2+2y3≥13y1+2y3≥-60-2y1+7y2-4y3=5y1+2y2+y4+y5=-7y1取值無約束y3,y5≥0y2,y4≤013Ⅰ對(duì)稱性定理對(duì)偶問題的對(duì)偶是原問題。Ⅱ主對(duì)偶定理若(LP)和(DP)均

6、可行，那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。如果原問題有最優(yōu)解，則其對(duì)偶問題也一樣具有最優(yōu)解，且有maxz=minw。二、對(duì)偶問題的基本性質(zhì)14Ⅲ弱對(duì)偶定理若x,y分別為（LP)和（DP）的可行解，那么cTx≤bTy。推論①若LP（或DP）可行，那么LP（或DP）無有限最優(yōu)解(有無界解)的充分必要條件是DP（或LP）無可行解。？？當(dāng)LP（或DP）無可行解時(shí)，則DP（或LP）具有無界解。②極大化問題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的一個(gè)下界。③極小化問題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問題最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界。15Ⅳ最優(yōu)性準(zhǔn)則定理若x,y分別

7、(LP)，(DP)的可行解,且cTx=bTy，那么x,y分別為(LP)和(DP)的最優(yōu)解。16三、影子價(jià)格市場(chǎng)價(jià)格影子價(jià)格，確切的定義是：一個(gè)線性規(guī)劃對(duì)偶問題的最優(yōu)解（簡(jiǎn)稱為“對(duì)偶最優(yōu)解”）。對(duì)偶變量yi：代表對(duì)一個(gè)單位第i種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià)。bi是線性規(guī)劃原問題約束條件右端項(xiàng)，它代表第i種資源的擁有量。17影子價(jià)格是一個(gè)向量，它的分量表示最優(yōu)目