運籌學0903對偶規(guī)劃.ppt

1、管理運籌學-管理科學方法,中國人民大學出版社,2,第3 章 對偶規(guī)劃,Sub title,學習要點,理解線性規(guī)劃問題的對偶問題 構(gòu)建線性規(guī)劃問題的對偶模型 正確理解對偶規(guī)劃的基本性質(zhì) 掌握影子價值的涵義及其應(yīng)用 資源總存量和分配量增減決策,3,第一節(jié) 對偶規(guī)劃的數(shù)學模型,一、對偶問題的提出,若例1中該廠的產(chǎn)品平銷，現(xiàn)有另一企業(yè)想租賃其設(shè)備。廠方為了在談判時心中有數(shù)，需掌握設(shè)備臺時費用的最低價碼，以便衡量對方出價，對出租與否做出抉擇。 在這個問題上廠長面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備。首先要弄清兩個問題： 合理安排生產(chǎn)能取得多大利潤? 為保持利潤水平不降低，資源轉(zhuǎn)讓的最低價格是多少？ 問題 的

2、最優(yōu)解：x1=4，x2=5，Z*=37。,4,第一節(jié) 對偶規(guī)劃的數(shù)學模型,一、對偶問題的提出,出讓定價,假設(shè)出讓A、B、C設(shè)備所得利潤分別為y1、y2、y3 原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺時，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤，否則寧愿自己生產(chǎn)。于是有 2y1+0y2+3y3 3 同理，對乙產(chǎn)品而言，則有 0y1+2y2+4y3 5 設(shè)備臺時出讓的收益（希望出讓的收益最少值） min 16y1+10y2+32y3 顯然還有 y1，y2，y30,5,第一節(jié) 對偶規(guī)劃的數(shù)學模型,一、對偶問題的提出,例1的對偶問題的數(shù)學模型,對偶問題的最優(yōu)解： y1=0，y2=1/2，y3=1，W* =37 兩個問題

3、的目標函數(shù)值相等并非偶然 前者稱為線性規(guī)劃原問題，則后者為對偶問題，反之亦然。 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗數(shù)的負值。,6,7,8,9,例：寫出線性規(guī)劃問題的對偶規(guī)劃,10,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),1、對稱性定理 對偶問題的對偶問題是原問題。 根據(jù)對偶規(guī)劃，很容易寫出對偶問題的對偶問題模型。 2、 最優(yōu)性定理 設(shè) ， 分別為原問題和對偶問題的可行解，且 則 ， 分別為各自的最優(yōu)解。 3. 對偶性定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且 兩者的目標函數(shù)值相等。 4. 互補松弛性 最優(yōu)解的充分必要條件是 ，,11,12,13,1

4、4,15,16,17,18,19,20,21,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,左邊是資源bi每增加一個單位對目標函數(shù)Z的貢獻； 對偶變量 yi在經(jīng)濟上表示原問題第i種資源的邊際價值。 對偶變量的值 yi*表示第i種資源的邊際價值，稱為影子價值。 若原問題價值系數(shù)Cj表示單位產(chǎn)值，則yi 稱為影子價格。 若原問題價值系數(shù)Cj表示單位利潤，則yi 稱為影子利潤。,22,23,24,25,生產(chǎn)計劃問題,例2. 某廠生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)工藝路線為：各自的零部件分別在設(shè)備A、B加工，最后都需在設(shè)備C上裝配。經(jīng)測算得到相關(guān)數(shù)據(jù)如表所示。應(yīng)如何制定生產(chǎn)計劃，使總利潤為最大。 據(jù)市場分析，單

5、位甲乙產(chǎn)品的銷售價格分別為73和75元，試確定獲利最大的產(chǎn)品生產(chǎn)計劃。,26,27,對偶問題,28,原問題是以利潤為目標，對偶變量 yi則定義為資源bi每增加一個單位對利潤的貢獻程度，稱為資源的 影子利潤； Y1=0, 說明設(shè)備A的工時增加并不影響利潤 Y2=0.5說明設(shè)備 B的工時每增加1小時，則使利潤增加0.5元。,最優(yōu)解,哪些是非瓶頸資源和瓶頸資源？,29,影子價格=資源成本+影子利潤,影子價格并不是資源的實際價格，而是企業(yè)內(nèi)部資源的配比價格，是由企業(yè)內(nèi)部資源的配置狀況決定的，并不是由市場來決定的,影子價格的應(yīng)用,1.影子價格與市場價格對比： 成本：A：20元/小時 B：15 C：10

6、市場：A:21;B:15;C:12,30,影子價格的應(yīng)用,2.增加哪一種資源對增加經(jīng)濟效益有利,3.告訴經(jīng)營者一怎樣的代價去取得稀缺資源,4.是一種機會成本，提示企業(yè)設(shè)備出租或原材料的轉(zhuǎn)讓的基價,5.知道新產(chǎn)品的定價與投產(chǎn)決策,6.分析工藝改變后對資源節(jié)約的收益,7.分析現(xiàn)有產(chǎn)品價格變動時對資源緊缺的影響,31,最優(yōu)解,32,maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32,33,最優(yōu)解 :X*=(4,5,8,0,0)T，Z*=37,34,35,36,37,38,39,40,41,42

7、,43,二、右端常量的變動分析,參數(shù)bi的變化范圍 第r個約束的右端項為br，增量br，其它數(shù)據(jù)不變。新的基解為,只要XB0 ，則可保持最優(yōu)基不變。,44,二、約束方程中常數(shù)項的靈敏度分析 從上表我們可以發(fā)現(xiàn)各個松弛變量的值，正好等于相應(yīng)變量的對偶價格。在最 優(yōu)解中S2 =50是基變量，即為，原料A有50千克沒用完，再增加A原料是不會增 加利潤的， A的對偶價格為0。對于任何為基變量的松弛變量所對應(yīng)的約束條件的 對偶價格為0。,45,46,47,48,49,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,影子價格不是資源的實際價格，反映了資源配置結(jié)構(gòu)， 其它數(shù)據(jù)固定，某資源增加一單位導致目標函

8、數(shù)的增量。 對資源i總存量的評估：購進 or 出讓 對資源i當前分配量的評估：增加 or 減少 第一，影子利潤說明增加哪種資源對經(jīng)濟效益最有利 第二，影子價格告知以怎樣的代價去取得緊缺資源 第三，影子價格是機會成本，提示資源出租/轉(zhuǎn)讓的基價 第四，利用影子價格分析新品的資源效果：定價決策 第五，利用影子價格分析現(xiàn)有產(chǎn)品價格變動的資源緊性 第六，可以幫助分析工藝改變后對資源節(jié)約的收益 第七，可以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺,50,51,52,53,54,55,第三節(jié) 資源定價的決策方案,例：某廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品的資源消耗如下表所示。 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使每周的利潤為最大。如果企業(yè)可以不生產(chǎn)，那資源出讓如何定價,56,第三節(jié) 資源定價的決策方案,一、最優(yōu)生產(chǎn)決策,決策變量：要確定甲、乙兩種產(chǎn)品的產(chǎn)量，我們設(shè)每周生產(chǎn)的甲產(chǎn)品的產(chǎn)量x1，每周生產(chǎn)的乙產(chǎn)品的產(chǎn)量 x2。 由上表計算單位甲產(chǎn)品的成本為383元，單位乙產(chǎn)品的成本為340元，則它們的盈利能力分別為7和12。 生產(chǎn)計劃的線性規(guī)劃模型：,57,第三節(jié) 資源定價的決策方案,二、資源獲利決策,