數(shù)據(jù)挖掘--對(duì)偶理論與靈敏度分析

1、燕山大學(xué)經(jīng)濟(jì)管理學(xué)院燕山大學(xué)經(jīng)濟(jì)管理學(xué)院運(yùn)籌學(xué)課程教學(xué)課題組編制運(yùn)籌學(xué)課程教學(xué)課題組編制2第二章第二章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論與靈敏度分析與靈敏度分析3第一節(jié)第一節(jié) LP 的對(duì)偶理論的對(duì)偶理論一、對(duì)偶問題的提出一、對(duì)偶問題的提出 每天可用能力每天可用能力 設(shè)備設(shè)備A 0 5 15 設(shè)備設(shè)備B 6 2 24 調(diào)試工序調(diào)試工序 1 1 5 利潤(rùn)利潤(rùn) 2 1兩種家電各生產(chǎn)多少兩種家電各生產(chǎn)多少, , 可獲最大利潤(rùn)可獲最大利潤(rùn)?4解解: :設(shè)兩種家電設(shè)兩種家電產(chǎn)量分別為變量產(chǎn)量分別為變量x1 ， x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2 0 max Z

2、= 2x1 +x25另一家公司至少應(yīng)付出多少代價(jià)才能使美佳公另一家公司至少應(yīng)付出多少代價(jià)才能使美佳公司愿意出讓自己的資源而不組織兩種產(chǎn)品的生產(chǎn)？司愿意出讓自己的資源而不組織兩種產(chǎn)品的生產(chǎn)？解：設(shè)解：設(shè) y1 , y2 , y3 分別為分別為A, B設(shè)備和調(diào)試工序工設(shè)備和調(diào)試工序工時(shí)出讓的單價(jià)。時(shí)出讓的單價(jià)。minW=15y1+24y2 +5y3 6y2 +y3 25y1 +2y2 +y3 1y1 y3 06二、對(duì)偶問題與原問題的關(guān)系二、對(duì)偶問題與原問題的關(guān)系1. “對(duì)稱型對(duì)稱型” (P)MaxZ=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn b b1 1a21X1+ a

3、22X2+ a2nXn b b2 2 am1X1+ am2X2+ amnXn b bm mXj j 0(0(j=1,n) )7MinW=b1Y1+ b2Y2+bnYna11Y1+ a21Y2+ am1Ym c c1 1a12Y1+ a22Y2+ am2Ym c c2 2 a1nY1+ a2nY2+ amnYm c cn nYi 0(0(i=1,m) )(D)8例例1 1：寫出下面問題的對(duì)偶規(guī)劃寫出下面問題的對(duì)偶規(guī)劃maxZ= 5X1 +6X2 3X1 -2X2 74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1, y2 09例例1 1：

4、寫出下面問題的對(duì)偶規(guī)劃寫出下面問題的對(duì)偶規(guī)劃maxZ= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 02. “非非對(duì)稱型對(duì)稱型” (P)10對(duì)偶問題對(duì)偶問題minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由自由 , y2 011例例2 2：寫對(duì)偶規(guī)劃：寫對(duì)偶規(guī)劃minZ= 4X1 +2X2 -3X3 -X1+2X2 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 012maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 ,

5、 y3自由自由13minZ= 4X1 +2X2 -3X3 X1 -2X2 - 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0或?qū)⒃瓎栴}變形為或?qū)⒃瓎栴}變形為14觀察結(jié)論觀察結(jié)論: 一對(duì)對(duì)偶問題都有最優(yōu)解，且目標(biāo)函數(shù)一對(duì)對(duì)偶問題都有最優(yōu)解，且目標(biāo)函數(shù)值相等。值相等。 最優(yōu)表中有兩個(gè)問題的最優(yōu)解。最優(yōu)表中有兩個(gè)問題的最優(yōu)解。15第二節(jié)第二節(jié) 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)一一、單純形法計(jì)算的矩陣描述單純形法計(jì)算的矩陣描述maxZ=CX AX b X 0(P)maxZ=CX AX+I+IXS = =b X, XS 016（初始單純形表）（初始單純形表）非基變量非

6、基變量基變量基變量XBXNXS0XSbBNICBCN017（迭代中的單純形表）（迭代中的單純形表）基變量基變量非基變量非基變量XBXNXS0XBB-1 bIB-1 NB-10CN- CB B-1 N- CB B-118二、對(duì)偶問題的基本性質(zhì)二、對(duì)偶問題的基本性質(zhì)1.1.對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題2.2.定理定理1 (1 (弱對(duì)偶定理弱對(duì)偶定理) )若若 , , 分別是分別是原問題和對(duì)偶問題的可行解，則存在原問題和對(duì)偶問題的可行解，則存在 推論：推論：1.1.原問題任一可行解的目標(biāo)函數(shù)原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界，反之，值是其

7、對(duì)偶問題目標(biāo)函數(shù)值的下界，反之，對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。問題目標(biāo)函數(shù)值的上界。 XYbYXC19 推論：推論：2.2.若原問題有可行解且目標(biāo)函數(shù)若原問題有可行解且目標(biāo)函數(shù)值無(wú)界，則其對(duì)偶問題無(wú)可行解；反之，值無(wú)界，則其對(duì)偶問題無(wú)可行解；反之，對(duì)偶問題有無(wú)界解，原問題無(wú)可行解。對(duì)偶問題有無(wú)界解，原問題無(wú)可行解。（但逆向不成立）（但逆向不成立） 推論：推論：3.3.若原問題有可行解，對(duì)偶問題若原問題有可行解，對(duì)偶問題無(wú)可行解，則原問題目標(biāo)函數(shù)值無(wú)界；反無(wú)可行解，則原問題目標(biāo)函數(shù)值無(wú)界；反之，對(duì)偶問題有可行解，而原問題無(wú)可行之，對(duì)

8、偶問題有可行解，而原問題無(wú)可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無(wú)界。解，則對(duì)偶問題的目標(biāo)函數(shù)值無(wú)界。203.3.定理定理2 2 yX,分別為分別為(P), (D)(P), (D)的可行解，且的可行解，且X yC=b , 則它們是則它們是(P), (D)(P), (D) 的最優(yōu)解。的最優(yōu)解。4.4.定理定理3 3（對(duì)偶定理）若原問題有最優(yōu)解，對(duì)偶（對(duì)偶定理）若原問題有最優(yōu)解，對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等?；騿栴}也有最優(yōu)解，且目標(biāo)函數(shù)值相等。或若原問若原問題與對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)題與對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。解，且它們最優(yōu)解的目標(biāo)函

9、數(shù)值相等。5.5.互補(bǔ)松弛性：互補(bǔ)松弛性： ， 分別是原問題和對(duì)偶分別是原問題和對(duì)偶問題的可行解，則問題的可行解，則 當(dāng)且當(dāng)且僅當(dāng)僅當(dāng) 為最優(yōu)解。為最優(yōu)解。XY0,0SSXYXYXY21例例： min = 2x1+3x2+5x3+2x4+3x5 其對(duì)偶解其對(duì)偶解 y1 =4/5 y2 =3/5 Z =5 用對(duì)偶理論求用對(duì)偶理論求(P)的最優(yōu)解的最優(yōu)解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)在線性規(guī)劃問題的最優(yōu)解中，若對(duì)應(yīng)某一約束條在線性規(guī)劃問題的最優(yōu)解中，若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，該約束條件取嚴(yán)格等式。件的對(duì)偶

10、變量值為非零，該約束條件取嚴(yán)格等式。反之，若約束條件取嚴(yán)格不等式，則其所對(duì)應(yīng)的反之，若約束條件取嚴(yán)格不等式，則其所對(duì)應(yīng)的對(duì)偶變量一定為對(duì)偶變量一定為0。22 第四節(jié)第四節(jié) 對(duì)偶單純形法對(duì)偶單純形法minZ=2X1 +3X2 +4X3 X1+2X2 + X3 32X1 - X2 +3X3 4X1 , X2 , X3 023初始單純形表為初始單純形表為CBXBbx1x2x3x4x5-2-3-4000 x4-3-1-2-1100 x5-4-21-301-2-3-40024思路：思路：( (maxmax型型) )單純形法：找基單純形法：找基B B，滿足滿足B-1b 0，即先找到基可即先找到基可行解，當(dāng)

11、行解，當(dāng) C - CBB-1 A不全不全 0 0，（，（即檢驗(yàn)數(shù)）即檢驗(yàn)數(shù)）。迭代迭代保持保持B-1b 0，使使C -CBB-1 A 0，即即CBB-1 A C，（保持原問題保持原問題的為基可行解，尋找對(duì)偶問的為基可行解，尋找對(duì)偶問題的可行解題的可行解）25一、對(duì)偶單純形法的基本思路：一、對(duì)偶單純形法的基本思路： 找基找基B，滿足，滿足C - CBB-1 A 0（檢驗(yàn)數(shù)）（檢驗(yàn)數(shù)），即找到對(duì)偶問題的可行解。即找到對(duì)偶問題的可行解。 如果如果B-1b不全不全 0 0，即原問題的基解為非即原問題的基解為非可行解，則可行解，則迭代迭代保持保持C -CBB-1 A 0，使使B-1b 0。即保持對(duì)偶問題

12、的解為可行即保持對(duì)偶問題的解為可行解，使原問題的基解逐漸轉(zhuǎn)解，使原問題的基解逐漸轉(zhuǎn)換為基可行解。換為基可行解。26二、對(duì)偶單純形法基本步驟二、對(duì)偶單純形法基本步驟 maxmax型型( (minmin型型) )(1) 作初始表，要求全部作初始表，要求全部j 0 ( 0)(2) 判定判定： B-1 b全全 0，停停。否則，取否則，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l為換出變量為換出變量. .27(3)確定換入變量確定換入變量 若若Xi l行的行的alj 全全 0 ，停停，原問題無(wú)可行解原問題無(wú)可行解。 若若Xi l行的行的alj 有有alj 0 ,則求則求j k =min =aljalkalj 12,原最優(yōu)