管理運籌學講義第3章對偶規(guī)劃.ppt

管理運籌學-管理科學方法,中山大學南方學院工商管理系,演講：王甜源,2,第3 章 對偶規(guī)劃,Sub title,學習要點,理解線性規(guī)劃問題的對偶問題 構(gòu)建線性規(guī)劃問題的對偶模型 正確理解對偶規(guī)劃的基本性質(zhì) 掌握影子價值的涵義及其應(yīng)用 資源總存量和分配量增減決策,3,設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時數(shù)列于下表 ：,產(chǎn)品數(shù)據(jù)表,問：充分利用設(shè)備機時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？,一、對偶問題的提出,第一節(jié) 對偶規(guī)劃的數(shù)學模型,4,解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學模型為：,反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么種機器的機時如何定價才是最佳決策？,第一節(jié) 對偶規(guī)劃的數(shù)學模型,5,在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條： （1）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。 （2）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。,設(shè)A、B、C、D設(shè)備的機時價分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學模型為：,第一節(jié) 對偶規(guī)劃的數(shù)學模型,6,把同種問題的兩種提法所獲得的數(shù)學模型用表2表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象。,原問題與對偶問題對比表,第一節(jié) 對偶規(guī)劃的數(shù)學模型,7,2. 原問題與對偶問題的對應(yīng)關(guān)系,原問題 （對偶問題）,對偶問題 （原問題）,第一節(jié) 對偶規(guī)劃的數(shù)學模型,8,生產(chǎn)計劃問題,例. 某廠生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)工藝路線為：各自的零部件分別在設(shè)備A、B加工，最后都需在設(shè)備C上裝配。經(jīng)測算得到相關(guān)數(shù)據(jù)如表所示。應(yīng)如何制定生產(chǎn)計劃，使總利潤為最大。 據(jù)市場分析，單位甲乙產(chǎn)品的銷售價格分別為73和75元，試確定獲利最大的產(chǎn)品生產(chǎn)計劃。,第一節(jié) 對偶規(guī)劃的數(shù)學模型,一、對偶問題的提出,9,第一節(jié) 線性規(guī)劃的一般模型,(1)決策變量：設(shè)x1為甲產(chǎn)品的產(chǎn)量，x2為乙產(chǎn)品的產(chǎn)量。 (2)約束條件：生產(chǎn)受設(shè)備能力制約，能力需求不能突破有效供給量。 設(shè)備A的約束條件表達為 2 x1 16 同理，設(shè)備B的加工能力約束條件表達為 2x2 10 設(shè)備C的裝配能力也有限，其約束條件為 3x1+ 4x2 32 (3)目標函數(shù)：目標是企業(yè)利潤最大化 max Z= 3x1 +5x2 (4)非負約束：甲乙產(chǎn)品的產(chǎn)量為非負 x1 0， x2 0,綜上的LP模型：,10,第一節(jié) 對偶規(guī)劃的數(shù)學模型,若該廠的產(chǎn)品平銷，現(xiàn)有另一企業(yè)想租賃其設(shè)備。廠方為了在談判時心中有數(shù)，需掌握設(shè)備臺時費用的最低價碼，以便衡量對方出價，對出租與否做出抉擇。 在這個問題上廠長面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備。首先要弄清兩個問題： 合理安排生產(chǎn)能取得多大利潤? 為保持利潤水平不降低，資源轉(zhuǎn)讓的最低價格是多少？ 問題 的最優(yōu)解：x1=4，x2=5，Z*=37。,一、對偶問題的提出,11,第一節(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è)備臺時出讓的價格（希望出讓的價格最少值以獲得市場優(yōu)勢） min 16y1+10y2+32y3 顯然還有 y1，y2，y30,12,第一節(jié) 對偶規(guī)劃的數(shù)學模型,一、對偶問題的提出,例1的對偶問題的數(shù)學模型,對偶問題的最優(yōu)解： y1=0，y2=1/2，y3=1，W* =37 兩個問題的目標函數(shù)值相等并非偶然 前者稱為線性規(guī)劃原問題，則后者為對偶問題，反之亦然。 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗數(shù)的負值。,13,（1）對稱形式,特點：目標函數(shù)求極大值時，所有約束條件為號，變量非負;目標函數(shù)求極小值時，所有約束條件為號，變量非負.,已知P，寫出D,第一節(jié) 對偶規(guī)劃的數(shù)學模型,14,例2.1 寫出線性規(guī)劃問題的對偶問題,解：首先將原問題變形為對稱形式,第一節(jié) 對偶規(guī)劃的數(shù)學模型,15,第一節(jié) 對偶規(guī)劃的數(shù)學模型,16,(2) 非對稱型對偶問題,若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。,第一節(jié) 對偶規(guī)劃的數(shù)學模型,17,第一節(jié) 對偶規(guī)劃的數(shù)學模型,18,課堂練習：寫出下列線性規(guī)劃問題的對偶問題.,解：原問題的對偶問題為,第一節(jié) 對偶規(guī)劃的數(shù)學模型,19,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),例2.3 分別求解下列2個互為對偶關(guān)系的線性規(guī)劃問題,分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：,20,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),原問題最優(yōu)表,對偶問題最優(yōu)表,21,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),原問題與其對偶問題的變量與解的對應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量。,22,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),性質(zhì)1 對稱性定理：對偶問題的對偶是原問題,23,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),性質(zhì)2 最優(yōu)性定理：如果 是原問題的可行解， 是其對偶問題的可行解，并且:,則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。,性質(zhì)3 對偶性定理：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。,還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。,24,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),性質(zhì)4 互補松弛性：設(shè)X*和Y*分別是P問題 和 D問題 的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量,25,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),性質(zhì)4的應(yīng)用： 該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y求X或已知X求Y,互補松弛條件,由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系： 若Y0，則Xs必為0；若X0，則Ys必為0 利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。,26,第一節(jié) 對偶規(guī)劃的數(shù)學模型,例2.4 已知線性規(guī)劃,的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解Y。,解：寫出原問題的對偶問題，即,標準化,27,第一節(jié) 對偶規(guī)劃的數(shù)學模型,設(shè)對偶問題最優(yōu)解為Y(y1，y2),由互補松弛性定理可知，X和 Y滿足：,即：,因為X10，X20，所以對偶問題的第一、二個約束的松弛變量等于零，即y30，y40，帶入方程中：,解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為： Y=(1,1)，最優(yōu)值w=26。,28,第一節(jié) 對偶規(guī)劃的數(shù)學模型,課堂練習： 已知線性規(guī)劃,的對偶問題的最優(yōu)解為Y=(0,-2)，求原問題的最優(yōu)解。,解: 對偶問題是,標準化,29,第一節(jié) 對偶規(guī)劃的數(shù)學模型,設(shè)對偶問題最優(yōu)解為X(x1，x2 ，x3)T ,由互補松弛性定理可知，X和 Y滿足：,將Y帶入由方程可知，y3y50，y41。,y2=-20 x50 又y4=10 x20,將x2，x5分別帶入原問題約束方程中，得：,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X=(-5,0,-1)，最優(yōu)值z=-12,30,第一節(jié) 對偶規(guī)劃的數(shù)學模型,二、對偶規(guī)劃的性質(zhì),原問題與對偶問題解的對應(yīng)關(guān)系小結(jié),31,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,yi是資源bi每增加一個單位對目標函數(shù)Z的貢獻； 對偶變量 yi在經(jīng)濟上表示原問題第i種資源的邊際價值。 對偶變量的值 yi*表示第i種資源的邊際價值，稱為影子價值。 若原問題價值系數(shù)Cj表示單位產(chǎn)值，則yi 稱為影子價格。 若原問題價值系數(shù)Cj表示單位利潤，則yi 稱為影子利潤。 影子價格=資源成本+影子利潤,32,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,影子價格不是資源的實際價格，反映了資源配置結(jié)構(gòu)， 其它數(shù)據(jù)固定，某資源增加一單位導致目標函數(shù)的增量。 對資源i總存量的評估：購進 or 出讓 對資源i當前分配量的評估：增加 or 減少 第一，影子利潤說明增加哪種資源對經(jīng)濟效益最有利 第二，影子價格告知以怎樣的代價去取得緊缺資源 第三，影子價格是機會成本，提示資源出租/轉(zhuǎn)讓的基價 第四，利用影子價格分析新品的資源效果：定價決策 第五，利用影子價格分析現(xiàn)有產(chǎn)品價格變動的資源緊性 第六，可以幫助分析工藝改變后對資源節(jié)約的收益 第七，可以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺,33,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,此理論應(yīng)用PPT 第8頁的例子 根據(jù)原問題最優(yōu)解（X2，X1）=（5，4）可求出對偶問題最優(yōu)解（Y1，Y2，Y3）=（0，0.5，1）， Y1=0設(shè)備A的工時增加不影響利潤增加非瓶頸資源 Y2=0.5設(shè)備B的工時增加1小時可帶來0.5的利潤增加瓶頸資源 Y3=1設(shè)備C的工時增加1小時可帶來1的利潤增加瓶頸資源 X3=8是代表A設(shè)備剩余的工時,34,第二節(jié) 對偶規(guī)劃的經(jīng)濟解釋,一、影子價值的內(nèi)涵,一般情況，市場價格小于影子價格，則說明自己生產(chǎn)比賣出去更能獲利；市場價格大于影子價格，則說明與其自己生產(chǎn)不如賣給別人更賺錢。 若本例中三個設(shè)備A，B，C工時成本分別為20，15，10，則影子價格為20+0，15+0.5，10+1，即20，15.5，11。 如果三種設(shè)備工時市場價格為21，15，12，則A設(shè)備工時可出讓，B設(shè)備工時購進，C設(shè)備工時雖然是瓶頸資源，但是因為市場價格大于影子價格而暫時不能購買。,35,第三節(jié) 資源定價的決策方案,例：某廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品的資源消耗如下表所示。 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使每周的利潤為最大。如果企業(yè)可以不生產(chǎn)，那資源出讓如何定價,36,第三節(jié) 資源定價的決策方案,一、最優(yōu)生產(chǎn)決策,決策變量：要確定甲、乙兩種產(chǎn)品的產(chǎn)量，我們設(shè)每周生產(chǎn)的甲產(chǎn)品的產(chǎn)量x1，每周生產(chǎn)的乙產(chǎn)品的產(chǎn)量 x2。 由上