運籌學課件第三節(jié)影子價格

第三節(jié)影子價格

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

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

，和檢驗數(shù)CN-CBB-1N中都有乘子Y=CBB-1。由強對偶定理知

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

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

Z*bi

（Y*b）bi

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

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

描述了原始線性規(guī)劃問題達到最優(yōu)時（各種“資源”都處于最優(yōu)的配置時），第i種“資源”的某種“價值”，故稱其為第i種“資源”的影子價格。

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

我們首先采用單純形法求解得王老板的家具生產(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)運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第4頁!線性規(guī)劃的對偶理論影子價格的直觀含義：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運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第5頁!線性規(guī)劃的對偶理論

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

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

1、單純形法求解

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

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

2、

對偶單純形法思想：

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

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

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

按主元素進行換基迭代，將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解。運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第12頁!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運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第13頁!練習:使用對偶單純形法求解運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第14頁!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=17運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第15頁!線性規(guī)劃的對偶理論影子價格王老板的家具生產(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運籌學課件第三節(jié)影子價格共27頁，您現(xiàn)在瀏覽的是第16頁!線性規(guī)劃的對偶理論

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

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

第四節(jié)

對偶單純形法

一、對偶單純形法的基本思路

對偶單純形法是應用對偶原理求解線性規(guī)劃的一種方法——在原問題的單純形表上進行對偶處理。

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

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

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

基變換：

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

化為標準型→

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