第二章-對偶理論與靈敏度分析課件

1、第二章 對偶理論與靈敏度分析第二章 對偶理論與靈敏度分析第一節(jié) 單純形法的矩陣描述對于標(biāo)準(zhǔn)形式的線性規(guī)劃模型：Max z CX AX b X 0 設(shè)B為一個(gè)基，它占據(jù)了A的m列，其它nm列用N表示，A =（B，N）。對X和C做對應(yīng)的分塊：第一節(jié) 單純形法的矩陣描述對于標(biāo)準(zhǔn)形式的線性規(guī)劃模型：MC =（ CB，CN ）XBXNX =則：AX =（B，N）XBXN= BXB NXN = b得：XB = B b B NXN （2.1）-1-1C =（ CB，CN ）XBX =則：AX =（B，N）XBz = CX = （ CB，CN ）XBXN= CBXB CN XN = CB（B b B NXN）

2、 CNXN -1-1= CBB b （CN CBB N）XN （2.2）-1-1 式（2.1）、（2.2）分別為基變量和目標(biāo)函數(shù)用非基變量的表達(dá)式，稱為關(guān)于B的典則形式，簡稱典式。 設(shè)B為可行基，令XN = 0， XB = B b 0，于是有基可行解：X1 =（B b ，0），對應(yīng)的目標(biāo)函數(shù)值：z1 = CBB b 。 由（2.2）可知非基變量的檢驗(yàn)數(shù)為：-1-1-1Tz = CX = （ CB，CN ）XB= CBXB N = CN CBB N 對于基變量XB ，檢驗(yàn)數(shù)B = CB CBB B = 0；故所有變量的檢驗(yàn)數(shù)可統(tǒng)一為： = C CBB A 寫成分量形式，任意變量xj的檢驗(yàn)數(shù)為：

3、j = cj CBB Pj 當(dāng)所有j 0時(shí)，X1 =（B b ，0）是最優(yōu)解，z1 = CBB b 是最優(yōu)值。 考慮線性規(guī)劃的規(guī)范形式，其初始基變量是松弛變量，此時(shí)， A =（B，N，I） ，C =（ CB，CN ，0），用-1-1-1-1-1-1 N = CN CBB N-1-1-1典式表示，寫于單純形表相應(yīng)位置：表2-1CBXBB bCBCN0XBXNXS0XSbBNIz0CBCN0CBXBB bIB NBzCBB b0CNCBB NCBB-1-1-1-1-1-1-1典式表示，寫于單純形表相應(yīng)位置：CBXBB bCBCN0 從表2-1可以看到，以B為基的單純形表中的增廣矩陣，是以B 左乘初

4、始表的增廣矩陣的結(jié)果。因此，在B為基的表中，與初始表單位矩陣相同位置處即為B的逆矩陣B 。-1-1 從表2-1可以看到，以B為基的單純形表中的增第二節(jié) 對偶問題的概念一、對偶問題的提出1、舉例：說明對偶問題的經(jīng)濟(jì)意義。2、規(guī)范形式的對偶問題LP（DP）：Max z = CX DP（LP）：Min w = Yb AXb YAC X0 Y0第二節(jié) 對偶問題的概念一、對偶問題的提出 二、一般形式的對偶問題 一般形式對偶問題之間的對應(yīng)規(guī)律： 目標(biāo)函數(shù)：max與min相互對應(yīng)； 目標(biāo)函數(shù)系數(shù)與約束條件右端項(xiàng)相互對應(yīng)； 約束條件：技術(shù)約束與變量符號(hào)約束相互對應(yīng)。 若規(guī)定線性規(guī)劃問題兩種規(guī)范形式的技術(shù)約束方

5、向及變量符號(hào)約束方向?yàn)檎虻模c之方向相反為反向的，等式技術(shù)約束和變量符號(hào)約束無限制為雙向的，則一個(gè)問題中的正向、反向和雙向約束，對應(yīng)于另一個(gè)問題的正向、反向和雙向約束，即兩個(gè)對應(yīng)的約束總屬于同樣的類型。 二、一般形式的對偶問題第三節(jié) 對偶問題的基本性質(zhì) 定理2.1 對偶問題的對偶是原問題。（對稱性定理） 定理2.2 設(shè)X、Y分別為原問題與對偶問題的可行解，則CXYb。（弱對偶定理） 定理2.3 若X、Y分別為原問題與對偶問題的可行解，且CX=Yb，則兩者均為最優(yōu)解。（最優(yōu)性判定定理） 定理2.4 若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解。設(shè)前者的最優(yōu)基為B，則對偶最優(yōu)解為Y=CBB ，且兩者的

6、最優(yōu)值相等。（強(qiáng)對偶定理）-1第三節(jié) 對偶問題的基本性質(zhì) 定理2.1 定理2.5 若X、Y分別為原問題與對偶問題的可行解，則它們都是最優(yōu)解的充要條件是：YXS = 0和YSX= 0。（互補(bǔ)松弛定理） 定理2.5 若X、Y分別為原問題與對第四節(jié) 影子價(jià)格 一、影子價(jià)格的概念 設(shè)Y*=（y1*，y2*，ym*）為對偶問題的最優(yōu)解，則稱 yi*為原問題第i個(gè)約束對應(yīng)的影子價(jià)格（Shadow Price）。 z* = w* = Y*b = biyi* 上式表示企業(yè)按照最優(yōu)計(jì)劃安排生產(chǎn)，最大產(chǎn)值等于各種資源的數(shù)量與對應(yīng)的影子價(jià)格乘積的總和。上式對bi求偏導(dǎo)，得：i=1m第四節(jié) 影子價(jià)格 一、影子價(jià)格的概

7、念i=1m z*/bi = yi* 表示第i種資源的影子價(jià)格yi*是z*對資源bi的變化率，即第i種資源變化一個(gè)單位時(shí)，最大產(chǎn)值的變化量。 二、影子價(jià)格的經(jīng)濟(jì)意義 1.影子價(jià)格是對系統(tǒng)資源的一種最優(yōu)估價(jià)，只有系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)才能賦予該資源這種價(jià)值。 2.影子價(jià)格是一種動(dòng)態(tài)價(jià)格，當(dāng)系統(tǒng)的狀態(tài)發(fā)生變化時(shí)，影子價(jià)格也會(huì)發(fā)生變化。 3.影子價(jià)格反映資源在系統(tǒng)內(nèi)的稀缺程度。決策者可對比該資源的市場價(jià)格做出合理決策。 z*/bi = yi* 4.影子價(jià)格反映系統(tǒng)對資源的利用水平。影子價(jià)格越高，說明系統(tǒng)的資源利用水平越高，因此，影子價(jià)格可作為考核和比較企業(yè)經(jīng)營水平的重要指標(biāo)。 4.影子價(jià)格反映系統(tǒng)對資源的

8、利用水平。影子價(jià)第五節(jié) 對偶單純形法 一、對偶單純形法的基本思路 原問題最優(yōu)單純形表檢驗(yàn)數(shù)行的相反數(shù)對應(yīng)于對偶問題的最優(yōu)解，其中對偶決策變量的值與原問題松弛變量的檢驗(yàn)數(shù)對應(yīng)，對偶松弛變量的值與原問題決策變量的檢驗(yàn)數(shù)對應(yīng)，不僅如此，原問題每張單純形表檢驗(yàn)數(shù)的相反數(shù)，都按上述規(guī)律對應(yīng)于對偶問題的一個(gè)“基本解”。 利用上述規(guī)律，可以從對偶理論的角度來認(rèn)識(shí)單純形法，同時(shí)得出對偶單純形法的求解思路。第五節(jié) 對偶單純形法 一、對偶單純形法的基單純形法和對偶單純形法的比較分析單純形法對偶單純形法從原問題的一個(gè)基可行解出發(fā)（b列非負(fù)） 對應(yīng)于對偶問題的一個(gè)基本解（檢驗(yàn)數(shù)行）換基迭代使對偶基本解負(fù)分量逐漸減少當(dāng)

9、對偶基本解達(dá)到可行（0），原問題與對偶問題同時(shí)得到最優(yōu)解從對偶問題的一個(gè)基可行解出發(fā)（檢驗(yàn)數(shù)行非正） 對應(yīng)于原問題的一個(gè)基本解（b列）換基迭代使原問題基本解負(fù)分量逐漸減少當(dāng)原問題基本解達(dá)到可行（b 0 ），對偶問題與原問題同時(shí)得到最優(yōu)解單純形法和對偶單純形法的比較分析單純形法對偶單純形法從原問 二、對偶單純形法的步驟 1、建立初始單純形表，所有檢驗(yàn)數(shù)j 0； 2、檢查b列元素，如果所有bi0，則已得到最優(yōu)解，結(jié)束。否則，轉(zhuǎn)入下一步； 3、確定出基變量：設(shè)minbi| bi0 = bl ，則其對應(yīng)的基變量為出基變量，l行為主元行； 4、確定入基變量：若l行所有alj 0，則問題無可行解，結(jié)束。否

10、則，計(jì)算= min j /alj| alj 0 = k/alk，則xk為入基變量，k列為主元列； 5、以alk為主元進(jìn)行換基迭代，方法與單純形法相同，得到新的單純形表，返回步驟2。 二、對偶單純形法的步驟第六節(jié) 靈敏度分析 一、靈敏度分析的意義 在前面的討論中，線性規(guī)劃模型的參數(shù)A、b、C都是當(dāng)作已知常數(shù)來處理的。但在實(shí)踐中，它們往往是根據(jù)統(tǒng)計(jì)數(shù)據(jù)測算的，不可能完全準(zhǔn)確，而且實(shí)際情況是在經(jīng)常變化的，某些參數(shù)會(huì)隨之改變。因此有必要研究參數(shù)的變化對最優(yōu)解的影響，這就是靈敏度分析（Sensitivity Analysis），具體來講，主要討論下列兩類問題： 1、在最優(yōu)解（或最優(yōu)基）不變的前提下，確定

11、參數(shù)的變化范圍；第六節(jié) 靈敏度分析 一、靈敏度分析的意義 2、當(dāng)參數(shù)或系數(shù)矩陣發(fā)生變化時(shí)，確定最優(yōu)解的變化。 當(dāng)參數(shù)發(fā)生變化時(shí)，利用新的數(shù)據(jù)，重新建立模型，從頭開始計(jì)算，固然可以解決問題，但這樣做顯然是不經(jīng)濟(jì)的，而且也得不到更多有用的信息。靈敏度分析是在原問題最優(yōu)解（最優(yōu)單純形表）上直接進(jìn)行分析計(jì)算，得出需要的答案。因此，靈敏度分析也稱為優(yōu)化后分析。 2、當(dāng)參數(shù)或系數(shù)矩陣發(fā)生變化時(shí)，確定最優(yōu)解的 二、靈敏度分析 參數(shù)變化會(huì)影響原最優(yōu)解的最優(yōu)性和可行性，最優(yōu)性由j = cj CBB Pj確定 ，可行性由B b 確定。 1、目標(biāo)函數(shù)系數(shù)cj的變化分析 目標(biāo)函數(shù)系數(shù)的變化會(huì)引起檢驗(yàn)數(shù)j 的變化，從而影響解的最優(yōu)性。 非基變量的目標(biāo)函數(shù)系數(shù) 若非基