運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格

第三節(jié)影子價(jià)格

對(duì)偶問(wèn)題解的經(jīng)濟(jì)解釋——影子價(jià)格我們已經(jīng)明白原始線(xiàn)性規(guī)劃與對(duì)偶線(xiàn)性規(guī)劃之間形式上的對(duì)偶以及他們解之間的關(guān)系，那么對(duì)偶問(wèn)題的解除了前面引例中提到的租金這種經(jīng)濟(jì)含義外其深刻的經(jīng)濟(jì)含義是什么呢？運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論

對(duì)偶問(wèn)題解的經(jīng)濟(jì)含義分析：從單純形法的矩陣描述中，目標(biāo)函數(shù)取值Z=CBB-1b

，和檢驗(yàn)數(shù)CN-CBB-1N中都有乘子Y=CBB-1。由強(qiáng)對(duì)偶定理知

Z*=CX*=CBB-1b=Y*b=W*由此Z*=

Y*b=b1y1+b1y2+…bmymZ*bi

Z*bi

（Y*b）bi

=CBB-1=Y*或==yi*運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論

對(duì)偶問(wèn)題解的經(jīng)濟(jì)含義：由上面分析——對(duì)偶問(wèn)題解中變量yi*的經(jīng)濟(jì)含義是在其他條件不變的情況下，單位第i種“資源”變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。所以，yi*

描述了原始線(xiàn)性規(guī)劃問(wèn)題達(dá)到最優(yōu)時(shí)（各種“資源”都處于最優(yōu)的配置時(shí)），第i種“資源”的某種“價(jià)值”，故稱(chēng)其為第i種“資源”的影子價(jià)格。

下面圖解闡述影子價(jià)格的直觀含義：運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論影子價(jià)格

我們首先采用單純形法求解得王老板的家具生產(chǎn)模型（P）的最優(yōu)解、最優(yōu)基矩陣如下（P）的最優(yōu)解為X*=（15，20，0，0）TB=（p2，p1）=412（D）的最優(yōu)解為Y*=CBB-1

=（5，15）CB=（C2，C1）

=（30，50）

B-1=1-2-1/23/2（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論影子價(jià)格的直觀含義：x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2

P可行域（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)2x1+x2=514x1+3x2=1211365=50x1+30x21355=50x1+30x2運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論

影子價(jià)格的特點(diǎn)：特點(diǎn)2、影子價(jià)格是一種邊際價(jià)值，其與經(jīng)濟(jì)學(xué)中的邊際成本的概念相同。因而，在經(jīng)濟(jì)管理有中十分重要的應(yīng)用價(jià)值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部的影子價(jià)格的大小決定企業(yè)的經(jīng)營(yíng)策略。影子價(jià)格yi相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，資源bi每增加一個(gè)單位，目標(biāo)函數(shù)z的增量。特點(diǎn)3、影子價(jià)格的大小客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。如果某種資源在系統(tǒng)內(nèi)供大于求，盡管它有實(shí)實(shí)在在的市場(chǎng)價(jià)格，但它在系統(tǒng)內(nèi)的影子價(jià)格卻為零，而影子價(jià)格越高，資源在系統(tǒng)內(nèi)越稀缺。當(dāng)影子價(jià)格高于市場(chǎng)價(jià)格，應(yīng)該買(mǎi)進(jìn)資源；當(dāng)影子價(jià)格低于市場(chǎng)價(jià)格，應(yīng)該賣(mài)出資源；

設(shè)備A:y1=0設(shè)備B:y2=0.25調(diào)試C:y3=0.5運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!特點(diǎn)5、從影子價(jià)格考察單純形表的計(jì)算。Cj代表第j種產(chǎn)品的產(chǎn)值，是生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品有利。當(dāng)產(chǎn)品產(chǎn)值小于隱含成本時(shí)，表明用資源生產(chǎn)別的產(chǎn)品有利。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!

1、單純形法求解

初始可行基（對(duì)應(yīng)一個(gè)初始基可行解）→迭代→另一個(gè)可行基（對(duì)應(yīng)另一個(gè)基可行解），直至所有檢驗(yàn)數(shù)≤0為止。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!單純形法的求解過(guò)程就是：

在保持原問(wèn)題可行的前提下（b列保持≥0），通過(guò)逐步迭代實(shí)現(xiàn)對(duì)偶可行（檢驗(yàn)數(shù)行≤0）。

2、

對(duì)偶單純形法思想：

換個(gè)角度考慮LP求解過(guò)程：保持對(duì)偶可行的前提下（檢驗(yàn)數(shù)行保持≤0），通過(guò)逐步迭代實(shí)現(xiàn)原問(wèn)題可行（b列≥0，從非可行解變成可行解）。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!二、對(duì)偶單純形法的計(jì)算步驟：

①建立初始單純形表，計(jì)算檢驗(yàn)數(shù)行。bi≥0——已得最優(yōu)解；bi至少一個(gè)元素<0,轉(zhuǎn)下步;bi≥0——原始單純形法；bi至少一個(gè)元素<0,另外處理；(原問(wèn)題、對(duì)偶問(wèn)題均無(wú)可行解，引進(jìn)人工變量)

檢驗(yàn)數(shù)全部≤0（非基變量檢驗(yàn)數(shù)<0）至少一個(gè)檢驗(yàn)數(shù)>0運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!然后確定換入變量——原則是：在保持對(duì)偶可行的前提下，減少原問(wèn)題的不可行性。如果（最小比值原則），則選為換入變量，相應(yīng)的列為主元列，主元行和主元列交叉處的元素為主元素。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!

按主元素進(jìn)行換基迭代，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!Cj-15-24-500CB

基by1y2y3y4y50y4-20y5-10[-6]-110-5-2-101Cj-Zj-15-24-500-24y21/30y5-1/3011/6-1/60-50[-2/3]-1/31Cj-Zj-150-1-40-24y21/4-5y31/2-5/410-1/41/415/2011/2-3/2Cj-Zj-15/200-7/2-3/2運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!練習(xí):使用對(duì)偶單純形法求解運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!Cj-4-1-300CB基bx1x2x3x4x5-4x21015/2-1/21/2-1x1410-3/2-1/2-1/2Cj-zj00-13/2-5/2-3/2X=(4,1,0)T,最優(yōu)值z(mì)=17運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論影子價(jià)格王老板的家具生產(chǎn)模型的圖解：

x1x2P可行域1350=50x1+30x2（15，20）

（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)2x1+x2=504x1+3x2=120L0：50x1+30x2運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!線(xiàn)性規(guī)劃的對(duì)偶理論

影子價(jià)格的特點(diǎn)：影子價(jià)格是對(duì)偶解的一個(gè)十分形象的名稱(chēng)，它既表明對(duì)偶解是對(duì)系統(tǒng)內(nèi)部資源在當(dāng)前的最優(yōu)利用配置下的一種客觀估價(jià)，又表明它是一種虛擬的價(jià)格（或價(jià)值的影象）而不是真實(shí)的價(jià)格。特點(diǎn)1、影子價(jià)格是對(duì)系統(tǒng)資源的一種內(nèi)部最優(yōu)估價(jià)，只有當(dāng)系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)才可能賦予資源這種價(jià)值。

系統(tǒng)資源的一種動(dòng)態(tài)價(jià)格體系，影子價(jià)格的大小與系統(tǒng)的價(jià)值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。系統(tǒng)環(huán)境的任何變化都可能會(huì)引起影子價(jià)格的變化。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!特點(diǎn)4、表明生產(chǎn)過(guò)程中該種資源的影子價(jià)格不等于0，表明生產(chǎn)過(guò)程中資源得到充分利用。如果某種資源未得到充分利用，該種資源的影子價(jià)格=0；運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!

第四節(jié)

對(duì)偶單純形法

一、對(duì)偶單純形法的基本思路

對(duì)偶單純形法是應(yīng)用對(duì)偶原理求解線(xiàn)性規(guī)劃的一種方法——在原問(wèn)題的單純形表上進(jìn)行對(duì)偶處理。

注意：不是解對(duì)偶問(wèn)題的單純形法！運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!

所有檢驗(yàn)數(shù)≤0意味著，說(shuō)明原問(wèn)題的最優(yōu)基也是對(duì)偶問(wèn)題的可行基。換言之，當(dāng)原問(wèn)題的基B既是原可行基又是對(duì)偶可行基時(shí)，B成為最優(yōu)基。補(bǔ)充定理B是線(xiàn)性規(guī)劃的最優(yōu)基的充要條件是，B是可行基，同時(shí)也是對(duì)偶可行基。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!3、對(duì)偶單純形法的實(shí)施（1）使用條件：

①檢驗(yàn)數(shù)全部≤0；②解答列bi至少一個(gè)元素<0；（2）實(shí)施對(duì)偶單純形法的基本原則：在保持對(duì)偶可行的前提下進(jìn)行基變換——每一次迭代過(guò)程中取出基變量中的一個(gè)負(fù)分量作為換出變量去替換某個(gè)非基變量（作為換入變量），使原問(wèn)題的非可行解向可行解靠近。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!

基變換：

先確定換出變量——bi中的負(fù)元素（一般選最小的負(fù)元素）對(duì)應(yīng)的基變量出基；即相應(yīng)的行為主元行。運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!舉例——用對(duì)偶單純形法求解LP：

化為標(biāo)準(zhǔn)型→

將2個(gè)等式約束兩邊分別乘以-1，然后列表求解如下：運(yùn)籌學(xué)課件第三節(jié)影子價(jià)格共27頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題時(shí)，當(dāng)使用約束條件為“大于等于”，不必引進(jìn)人工變量，計(jì)算簡(jiǎn)化。注意：在初始單純形表其對(duì)偶問(wèn)題應(yīng)該是基可行解，對(duì)多數(shù)線(xiàn)性規(guī)劃問(wèn)題難實(shí)現(xiàn)。主要應(yīng)