運(yùn)籌學(xué)教程老師課件第2對(duì)偶理論

1、第三章 線性規(guī)劃的對(duì)偶理論 與靈敏度分析 n線性規(guī)劃的對(duì)偶問(wèn)題 n對(duì)偶問(wèn)題的基本性質(zhì)n影子價(jià)格n對(duì)偶單純形法n靈敏度分析n參數(shù)線性規(guī)劃窗含西嶺千秋雪，門(mén)泊東吳萬(wàn)里船對(duì)偶是一種普遍現(xiàn)象Dual Simplex Method，1954年美國(guó)數(shù)學(xué)家C.萊姆基提出對(duì)偶單純形法。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。 設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按種設(shè)備按A，B，C，D順

2、序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表 ：產(chǎn)品數(shù)據(jù)表產(chǎn)品數(shù)據(jù)表 設(shè)備設(shè)備產(chǎn)品產(chǎn)品ABCD產(chǎn)品利潤(rùn)產(chǎn)品利潤(rùn)（元件）（元件） 甲甲 21402乙乙 22043設(shè)備可利用設(shè)備可利用機(jī)時(shí)數(shù)（時(shí)）機(jī)時(shí)數(shù)（時(shí)） 1281612問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？能獲得最大利潤(rùn)？1. 解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為： 0,124164821222.32max212121212

3、1xxxxxxxxtsxxz反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么種機(jī)器的機(jī)時(shí)如何定用于接受外加工，只收加工費(fèi)，那么種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？?jī)r(jià)才是最佳決策？在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于自己加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。 （2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。或者說(shuō)租借方希望總的收購(gòu)價(jià)越小越好(目標(biāo))設(shè)設(shè)A、B、C、D 設(shè)備的機(jī)時(shí)價(jià)分別為設(shè)備的機(jī)時(shí)價(jià)

4、分別為y1、y2、y3、y4，則新的線，則新的線性規(guī)劃數(shù)學(xué)模型為：性規(guī)劃數(shù)學(xué)模型為： 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 2. 0,124164821222.32max2121212121xxxxxxxxtsxxz1234123412341234min12816122402s.t 22043,0

5、yyyyyyyyyyyyy yyy原問(wèn)題原問(wèn)題（對(duì)偶問(wèn)題）（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題對(duì)偶問(wèn)題（原問(wèn)題）（原問(wèn)題）從上例來(lái)看從上例來(lái)看, ,對(duì)偶問(wèn)題有其明顯的經(jīng)濟(jì)含義對(duì)偶問(wèn)題有其明顯的經(jīng)濟(jì)含義. .（1）對(duì)稱形式特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為號(hào)，變量非負(fù); 目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為號(hào)，變量非負(fù). max Z 0 PCXAXbX： : min 0DWY bA YCY已知P，寫(xiě)出Dn 任何線性規(guī)劃問(wèn)題都有其對(duì)偶問(wèn)題任何線性規(guī)劃問(wèn)題都有其對(duì)偶問(wèn)題. .列向量行向量n個(gè)變量n個(gè)約束例如：(P) 2x 2 206038045060212112121 xxyxyxxxxz,max 121212

6、12min8060. . 2360 4250 ,0yystyyyyyy例2.1 寫(xiě)出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先將原問(wèn)題變形為對(duì)稱形式,再寫(xiě)出對(duì)偶式123123123123123m ax2342352 3 7 3 465,0Zxxxxxxxxxxxxxxx 123123123123123min23523 23 43 576 4,0wyyyyyyyyyyyyyyy (2) 非對(duì)稱型對(duì)偶問(wèn)題 若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式再寫(xiě)對(duì)偶問(wèn)題。也可直接按教材表2-2中的對(duì)應(yīng)關(guān)系寫(xiě)出

7、非對(duì)稱形式的對(duì)偶問(wèn)題。原問(wèn)題（或?qū)ε紗?wèn)題）原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)目標(biāo)函數(shù) max目標(biāo)函數(shù)目標(biāo)函數(shù) min約約束束條條件件m個(gè)個(gè)m個(gè)個(gè)變變量量00=無(wú)約束無(wú)約束變變量量n個(gè)個(gè)n個(gè)個(gè)約約束束條條件件00無(wú)約束無(wú)約束=例2.2 寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題. 無(wú)無(wú)約約束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解：原問(wèn)題的對(duì)偶問(wèn)題

8、為 無(wú)無(wú)約約束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW第三章 線性規(guī)劃的對(duì)偶理論與靈敏度分析 n線性規(guī)劃的對(duì)偶問(wèn)題 n對(duì)偶問(wèn)題的基本性質(zhì)n影子價(jià)格n對(duì)偶單純形法n靈敏度分析n 參數(shù)線性規(guī)劃第二節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)為了便于討論，下面不妨總是假設(shè)針對(duì)對(duì)稱形式：: maxs.t.0ZCXAXbX原問(wèn)題: mins.t.0WY bA YCY對(duì)偶問(wèn)題原線性規(guī)劃問(wèn)題的矩陣表達(dá)式加上松弛變量后為： 一、單純形法的矩陣描述上式中上式中 Xs 為松弛變量，為松弛變量， ，I 為為mm單位矩陣。單位矩陣。 0,00maxss

9、sXXbIXAXXCXz),(21mnnnsxxxX令非基變量令非基變量 XN =0, XS =0 則得到一個(gè)基可行解。則得到一個(gè)基可行解。 XB = B-1 b ， Z =CB B-1 b XB XN XS(A，I) X XS =(B，N，I) =(B XB+N XN +I XS)=b以 B B-1-1 左乘上式得左乘上式得： B B-1-1 B XB+ B B-1-1 N XN + B B-1-1 I XS= B B-1-1 bXB= B B-1-1 b B B-1-1 N XN B B-1-1 XS代入目標(biāo)函數(shù)代入目標(biāo)函數(shù)得：得：Z= CX+0Xs =(CB， CN)XB XN+0Xs=

10、 CBXB + CNXN +0Xs= CB(B-1 b B-1 N XN B-1 XS ) + CNXN +0Xs= CBB-1 b CBB-1 N XN CB B-1 XS + CNXN +0Xs= CBB-1 b + (CN CB B-1 N) XN CB B-1 XS 單純形法計(jì)算時(shí)，總選取單純形法計(jì)算時(shí)，總選取 I 為為初始基初始基，對(duì)應(yīng)基變量為對(duì)應(yīng)基變量為 Xs。假假設(shè)迭設(shè)迭代若干步后，基變量變?yōu)榇舾刹胶螅兞孔優(yōu)閄B，在初始單純形表中對(duì)應(yīng)的，在初始單純形表中對(duì)應(yīng)的系數(shù)矩陣為系數(shù)矩陣為B。B將在初始單純形表中單獨(dú)列出，而將在初始單純形表中單獨(dú)列出，而A中去掉若干列后剩下的列組成矩

11、中去掉若干列后剩下的列組成矩陣陣N，這樣初始單純形表可列成如下形式。，這樣初始單純形表可列成如下形式。 非基變量非基變量基變量基變量XB XNXS0 XS bB NIcj-zjCB CN0 當(dāng)?shù)舾刹胶?，基變量為?dāng)?shù)舾刹胶?，基變量為X XB B時(shí)，則該步的單純形表中由時(shí)，則該步的單純形表中由X XB B系數(shù)系數(shù)組成的矩陣為組成的矩陣為I I。又因單純形法的迭代是對(duì)約束增廣矩陣進(jìn)行的又因單純形法的迭代是對(duì)約束增廣矩陣進(jìn)行的行初行初等變換等變換，對(duì)應(yīng)對(duì)應(yīng)X XS S的系數(shù)矩陣在新表中應(yīng)為的系數(shù)矩陣在新表中應(yīng)為B B-1-1。故當(dāng)基變量為故當(dāng)基變量為X XB B時(shí)，新時(shí)，新的單純形表具有如下形

12、式。的單純形表具有如下形式。 基變量基變量非基變量非基變量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 cj-zj0CN CB B B-1-1 N CB B B-1-1 當(dāng)?shù)蠡兞繛楫?dāng)?shù)蠡兞繛閄B時(shí)時(shí)，其在初始單純形表中的系數(shù)矩陣為其在初始單純形表中的系數(shù)矩陣為B B，則有：，則有：（1 1）對(duì)應(yīng)初始單純形表中的單位矩陣對(duì)應(yīng)初始單純形表中的單位矩陣I I，迭代后的單純形表中為，迭代后的單純形表中為B B-1-1 （2）初始單純形表中基變量初始單純形表中基變量Xs=bXs=b，迭代后的表，迭代后的表中中 XB= B B-1-1 b（3）初始單純形表中

13、約束系數(shù)矩陣為初始單純形表中約束系數(shù)矩陣為 ，迭代后的，迭代后的 表中約束系數(shù)矩陣為表中約束系數(shù)矩陣為(B(B-1-1 左乘左乘) ) :INBIA, 1111111,BNBIIBNBBBIBAB非基變量非基變量基變基變量量XB XNXS0 XS bB NIcj-zjCB CN0基變基變量量非基變量非基變量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 cj-zj0CN CB B B-1-1 N CB B B-1-1 （4）若初始矩陣中變量若初始矩陣中變量Xj的系數(shù)向量為的系數(shù)向量為Pj ，迭代后為，迭代后為 ，則有，則有:jPjjPBP1（5）當(dāng)當(dāng)B B為最

14、優(yōu)基時(shí)，應(yīng)有為最優(yōu)基時(shí)，應(yīng)有: : 01NBCCBN01BCB這時(shí)從檢驗(yàn)數(shù)行看出，若取其這時(shí)從檢驗(yàn)數(shù)行看出，若取其相反數(shù)相反數(shù)恰好是其對(duì)偶問(wèn)題的一個(gè)可行解。恰好是其對(duì)偶問(wèn)題的一個(gè)可行解。將這個(gè)解代入對(duì)偶問(wèn)題的目標(biāo)函數(shù)值，且有將這個(gè)解代入對(duì)偶問(wèn)題的目標(biāo)函數(shù)值，且有： 因因XB的檢驗(yàn)數(shù)可寫(xiě)為的檢驗(yàn)數(shù)可寫(xiě)為: zbBCbYwB11BCYB0YCYA則有則有稱為稱為單純形乘子單純形乘子，若令若令1BCB基變量基變量非基變量非基變量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN CB B B-1-1 N CB B B-1-1 XN的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) XS

15、的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 0ICCBBXB的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 01ABCCB所以XA的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 二、原規(guī)劃與對(duì)偶問(wèn)題的變量及解之間的對(duì)應(yīng)關(guān)系二、原規(guī)劃與對(duì)偶問(wèn)題的變量及解之間的對(duì)應(yīng)關(guān)系對(duì)偶(min型)變量的最優(yōu)解等于原問(wèn)題松弛變量的機(jī)會(huì)成本，或者說(shuō)原問(wèn)題松弛變量檢驗(yàn)數(shù)的絕對(duì)值。 容易證明，對(duì)偶問(wèn)題最優(yōu)解的剩余變量解值等于原問(wèn)題對(duì)應(yīng)變量的檢驗(yàn)數(shù)的絕對(duì)值。 由于原問(wèn)題和對(duì)偶問(wèn)題是相互對(duì)偶的，因此對(duì)偶問(wèn)題的檢驗(yàn)數(shù)與原問(wèn)題的解也有類(lèi)似上述關(guān)系。 更一般地講，不管原問(wèn)題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原問(wèn)題虛變量(松弛或剩余) 的機(jī)會(huì)成本對(duì)應(yīng)其對(duì)偶問(wèn)題實(shí)變量 (對(duì)偶變量)的最優(yōu)解，原問(wèn)題實(shí)變量(決策變量

16、) 的檢驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問(wèn)題虛變量 (松弛或剩余變量)的最優(yōu)解。因此，原問(wèn)題或?qū)ε紗?wèn)題只需求解其中之一就可以了。 例3.4 兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題，兩者分別加上松弛和剩余變量后為： 543210002maxxxxxxz)5 ,.1(05242615552142132jxxxxxxxxxj543210052415minyyyyyw) 5 , 1(0125265321432iyyyyyyyyi兩個(gè)問(wèn)題的最終單純形表見(jiàn)下頁(yè)： jjzc 原問(wèn)題變量松弛變量 x1x2x3x4x5x315/20015/415/2x17/21001/41/2x23/20101/43/2000-1/4-1/2 對(duì)偶問(wèn)題的剩

17、余變量對(duì)偶問(wèn)題變量y4y5y1y2y3jjzc 對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題的剩余變量 y1y2y3y4y5y21/4 5/410 1/41/4y31/215/2011/23/215/2007/23/2 原問(wèn)題松弛變量x3x4x5原問(wèn)題變量x1x2三、線性規(guī)劃的對(duì)偶定理1. 弱對(duì)偶定理定理 對(duì)偶問(wèn)題(min)的任何可行解 Y0，其目標(biāo)函數(shù)值總是不小于原問(wèn)題(max)任何可行解 X0 的目標(biāo)函數(shù)值。00000000000000000: ,00 0, .0 .XYAXbY ACXYY AC XY AXCXAXbYY bY AXCX證由于分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解 故有因，因此另外，因， 因此弱對(duì)偶定理

18、推論弱對(duì)偶定理推論: :nmax問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶 min問(wèn)題目標(biāo)函數(shù)值的下限； min問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶max問(wèn)題目標(biāo)函數(shù)值的上限。n 如果原max(min)問(wèn)題為無(wú)界解，則其對(duì)偶 min (max)問(wèn)題無(wú)可行解。n 如果原max(min)問(wèn)題有可行解，其對(duì)偶 min (max)問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解。2. 最優(yōu)解判別定理定理 若原問(wèn)題的某個(gè)可行解X0的目標(biāo)函數(shù)值與對(duì)偶問(wèn)題某個(gè)可行解Y0的目標(biāo)函數(shù)值相等，則X0, Y0分別是相應(yīng)問(wèn)題的最優(yōu)解證：由弱對(duì)偶定理推論1，結(jié)論是顯然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 證畢。定理(對(duì)

19、偶定理) 如果原問(wèn)題和對(duì)偶問(wèn)題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證：由弱對(duì)偶定理推論1可知，原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)有界，故一定存在最優(yōu)解。現(xiàn)證明定理的后一句話。 設(shè) X0 為原問(wèn)題的最優(yōu)解，它所對(duì)應(yīng)的基矩陣是 B， X0= B1 b，則其檢驗(yàn)數(shù)滿足 C CBB1A 0 令 Y0= CBB1，則有 Y0 A C ；而對(duì)原問(wèn)題松弛變量的檢驗(yàn)數(shù)有 0 CBB1I 0，即 Y0 0 。 顯然Y0為對(duì)偶問(wèn)題的可行解。因此有對(duì)偶問(wèn)題目標(biāo)函數(shù)值， W(Y0)=Y0b= CBB1 b 而原問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值為 Z(X0)=CX0= CBB1 b 故由最優(yōu)解判別定理可知Y0

20、為對(duì)偶問(wèn)題的最優(yōu)解。證畢。該定理的證明告訴我們一個(gè)非常重要的概念：對(duì)偶變量的最優(yōu)解等于原問(wèn)題松弛變量的機(jī)會(huì)成本即對(duì)偶變量的最優(yōu)解是原問(wèn)題資源的影子價(jià)格4. 互補(bǔ)松弛互補(bǔ)松弛定理定理定理 設(shè)X0, Y0分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，U0為原問(wèn)題的松弛變量的值、V0為對(duì)偶問(wèn)題剩余變量的值。X0, Y0分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分必要條件是 Y0 U0 + V0 X0 = 0. 證：由定理所設(shè)，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分別以Y0左乘(1)式，以X0右乘(2)式后，兩式相減，得 Y0 U0 + V0 X0 =

21、 Y0 b C X0若 Y0 U0 + V0 X0 = 0，根據(jù)最優(yōu)解判別定理， X0, Y0分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解。反之亦然。 證畢。Y0 U 0 + V 0 X 0 = 0 有什么應(yīng)用u 若(Y 0 )i 0，則 (U 0 )i =0，意味著原問(wèn)題第 i 約束行必須為 = 約束；對(duì)(X0 )i 0 亦如此.miuynjxviijj, 2 , 10, 2 , 100000因 Y0 ，U0 ， V0 ，X0 0 則有：在線性規(guī)劃問(wèn)題的最優(yōu)解在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為件的對(duì)偶變量值為非非0，則，則該約束條件取嚴(yán)格等式；該約束條件取嚴(yán)格

22、等式；反之如果約束條件反之如果約束條件取嚴(yán)格取嚴(yán)格不等式不等式，則，則 對(duì)應(yīng)的對(duì)偶變對(duì)應(yīng)的對(duì)偶變量值為量值為0。第三章 線性規(guī)劃的對(duì)偶理論 與靈敏度分析 n線性規(guī)劃的對(duì)偶問(wèn)題 n對(duì)偶問(wèn)題的基本性質(zhì)n影子價(jià)格n對(duì)偶單純形法n靈敏度分析n參數(shù)線性規(guī)劃第三節(jié) 影子價(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格 1. 影子價(jià)格的數(shù)學(xué)解釋：影子價(jià)格的數(shù)學(xué)解釋：由對(duì)偶問(wèn)題得基本性質(zhì)可得：當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解由對(duì)偶問(wèn)題得基本性質(zhì)可得：當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解xj*(j=1, n), 其對(duì)偶問(wèn)題也獲得最優(yōu)解其對(duì)偶問(wèn)題也獲得最優(yōu)解 yi* (i=1, m), 且有且有11nmjjiijizc xb y 定義：在一對(duì)定義

23、：在一對(duì) P 和和 D 中，若中，若 P 的某個(gè)約束條件的右端項(xiàng)的某個(gè)約束條件的右端項(xiàng)常數(shù)常數(shù)bi （第（第i種資源的擁有量）增加一個(gè)單位時(shí)，所引起種資源的擁有量）增加一個(gè)單位時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值目標(biāo)函數(shù)最優(yōu)值 z* 的改變量稱為第的改變量稱為第 i 種資源的影子價(jià)格，種資源的影子價(jià)格，其值等于其值等于D問(wèn)題中對(duì)偶變量問(wèn)題中對(duì)偶變量 yi*。361）影子價(jià)格是一種）影子價(jià)格是一種邊際價(jià)格邊際價(jià)格在其它條件不變的情況下，單位資源數(shù)量的變化所引起在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對(duì)偶變量的目標(biāo)函數(shù)最優(yōu)值的變化。即對(duì)偶變量 yi 就是第就是第 i 種資源種

24、資源的影子價(jià)格。即：的影子價(jià)格。即： )2 , 1(*miybZii 2）影子價(jià)格是一種）影子價(jià)格是一種機(jī)會(huì)成本機(jī)會(huì)成本影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一個(gè)角度說(shuō)，它是一種機(jī)會(huì)成本。個(gè)角度說(shuō)，它是一種機(jī)會(huì)成本。37若第若第i 種資源的單位市場(chǎng)價(jià)格為種資源的單位市場(chǎng)價(jià)格為mi ，則有當(dāng)，則有當(dāng)yi* mi 時(shí)，企業(yè)愿意時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為購(gòu)進(jìn)這種資源，單位純利為 yi*mi ，則有利可圖；如果，則有利可圖；如果yi* mi ，則企業(yè)

25、有償轉(zhuǎn)讓這種資源，可獲單位純利則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利miyi * ，否則，企業(yè)無(wú)，否則，企業(yè)無(wú)利可圖，甚至虧損。利可圖，甚至虧損。3）影子價(jià)格在資源利用中的應(yīng)用）影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0 , YsX*=0.表明生產(chǎn)過(guò)程中表明生產(chǎn)過(guò)程中, 如果某種資源如果某種資源bi未得到充分利用時(shí)，該種資未得到充分利用時(shí)，該種資源的影子價(jià)格為源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。該種資源在生產(chǎn)中已耗費(fèi)完。11 0; 0, nnijjiiiijjij

26、ja xbyya xb也 即時(shí) ，而 當(dāng)有384）影子價(jià)格對(duì)單純形表計(jì)算的解釋）影子價(jià)格對(duì)單純形表計(jì)算的解釋單純形表中的檢驗(yàn)數(shù)單純形表中的檢驗(yàn)數(shù) miiijjjBjjyacPBCc11其中其中 cj 表示第表示第 j種產(chǎn)品的價(jià)格種產(chǎn)品的價(jià)格; 表示生產(chǎn)該種產(chǎn)品表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。即產(chǎn)品的隱含成本。 miiijya1當(dāng)產(chǎn)值大于隱含成本時(shí)，即當(dāng)產(chǎn)值大于隱含成本時(shí)，即 ，表明生產(chǎn)該項(xiàng)產(chǎn)品有，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則利，可在計(jì)劃中安排；否則 ，用這些資源生產(chǎn)別的，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安

27、排該產(chǎn)品。產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。0 j 0 j 產(chǎn)品產(chǎn)品資源資源 I II可用量可用量機(jī)械設(shè)備機(jī)械設(shè)備 1 28原材料原材料A 4 016原材料原材料B 0 412 X *=(4，2，0，0, 4)T， z* =14cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-2-3/2-1/81/801000-3/2-1/800,125.0,5.1*3*2*1yyy經(jīng)濟(jì)意義經(jīng)濟(jì)意義：在在其它條件不變其它條件不變的情況下，的情況下，單位資源變化單位資源變化所引起的目標(biāo)所引起的目標(biāo)函數(shù)的最優(yōu)值函數(shù)的最優(yōu)值的變化。的變化。影子價(jià)格 (P)的最終單純形表中松弛變量的

28、檢驗(yàn)的最終單純形表中松弛變量的檢驗(yàn)數(shù)對(duì)應(yīng)數(shù)對(duì)應(yīng)(D)的最優(yōu)解。的最優(yōu)解。40具體來(lái)說(shuō)：具體來(lái)說(shuō)：這說(shuō)明是其他條件不變的情況下，若設(shè)備增加一這說(shuō)明是其他條件不變的情況下，若設(shè)備增加一臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元；原材料元；原材料A增加增加1kg，可多獲利，可多獲利0.125元；原材料元；原材料B增加增加1kg，對(duì)獲利無(wú)，對(duì)獲利無(wú)影響。影響。 41從上圖可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線由移從上圖可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線由移至至，相應(yīng)的最優(yōu)解由，相應(yīng)的最優(yōu)解由(4，2)變?yōu)樽優(yōu)?4，2.5)，目標(biāo)函數(shù)，目標(biāo)函數(shù)z=2

29、4+32.5=15.5，即比原來(lái)的增大，即比原來(lái)的增大1.5。又若原材料。又若原材料A增加增加1kg時(shí)，代表該約束方程的直線由移至?xí)r，代表該約束方程的直線由移至，相應(yīng)的最優(yōu)解從，相應(yīng)的最優(yōu)解從(4，2)變?yōu)樽優(yōu)?4.25，1.875)，目標(biāo)函數(shù)，目標(biāo)函數(shù)z=4.25+31.875=14.125。比原。比原來(lái)的增加來(lái)的增加0.125。原材料。原材料B增加增加1kg時(shí)，該約束方程的直線由移時(shí)，該約束方程的直線由移至至，這時(shí)的最優(yōu)解不變。，這時(shí)的最優(yōu)解不變。42 這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為價(jià)格，稱它為“影子價(jià)格影子價(jià)格

30、”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.51.5元，元，1kg1kg原材料原材料A A的出的出讓費(fèi)為除成本外再附加讓費(fèi)為除成本外再附加0.1250.125元，元，1kg1kg原材料原材料B B可按原成本出可按原成本出讓，這時(shí)該廠的收入與自己組織生產(chǎn)時(shí)獲利相等。讓，這時(shí)該廠的收入與自己組織生產(chǎn)時(shí)獲利相等。 影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該資源用當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該資源用于擴(kuò)大生產(chǎn)；

31、而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣(mài)掉?？梢?jiàn)影子價(jià)格對(duì)市場(chǎng)有則企業(yè)的決策者應(yīng)把已有資源賣(mài)掉。可見(jiàn)影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。調(diào)節(jié)作用。 影子價(jià)格越影子價(jià)格越大大，說(shuō)明這種資源越是相對(duì)，說(shuō)明這種資源越是相對(duì) 緊缺緊缺。相反，。相反，影子價(jià)格越影子價(jià)格越小小，說(shuō)明這種資源相對(duì)，說(shuō)明這種資源相對(duì)寬松寬松。第三章 線性規(guī)劃的對(duì)偶理論 與靈敏度分析 n線性規(guī)劃的對(duì)偶問(wèn)題 n對(duì)偶問(wèn)題的基本性質(zhì)n影子價(jià)格n對(duì)偶單純形法n靈敏度分析n參數(shù)線性規(guī)劃第四節(jié) 對(duì)偶單純形法 對(duì)偶單純形法是求解線性規(guī)劃原問(wèn)題的另一個(gè)基本方法。它是根據(jù)對(duì)偶

32、原理和單純形法原理而設(shè)計(jì)出來(lái)的，因此稱為對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法。 原來(lái), 求解單純形法的基本思路是： 對(duì)原問(wèn)題的一個(gè)基可行解，判別是否所有檢驗(yàn)數(shù)cj-zj0(j=1,n)。若是，又基變量中無(wú)非零人工變量，即找到了問(wèn)題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。一、基本思路 原單純型迭代要求每步都是基可行解達(dá)到最優(yōu)解時(shí)，檢驗(yàn)數(shù) cjzj 0 (max) 或 cjzj 0 (min). 但對(duì)于(min, )型所加的剩余變量無(wú)法構(gòu)成初始基礎(chǔ)可行解，因此通過(guò)加人工變量來(lái)解決. 此時(shí), 使用的大M法和二階

33、段法較繁. 能否從剩余變量構(gòu)成的初始基非可行解出發(fā)迭代，但保證檢驗(yàn)數(shù)滿足最優(yōu)條件， cjzj 0 (max) 或 cjzj 0 (min) 每步迭代保持檢驗(yàn)數(shù)滿足最優(yōu)條件，但減少非可行度.46找出一個(gè)DP的可行基LP是否可行（XB 0）保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解最優(yōu)解是否循環(huán)結(jié)束找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶問(wèn)題為可行解的條件下，判斷找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶問(wèn)題為可行解的條件下，判斷XB是否可行（是否可行（XB為非負(fù)），若否，通過(guò)變換基解，直到找到原問(wèn)題基可行為非負(fù)），若否，通過(guò)變換基解，直到找到原問(wèn)題基可行解（即解（即XB為非負(fù)），這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)

34、到可行解，由對(duì)偶定為非負(fù)），這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解，由對(duì)偶定理可得最優(yōu)解。理可得最優(yōu)解。二、迭代步驟1.確定出變量 找非可行解中最小者，即 min bi | bi6 6 時(shí)有：時(shí)有： z z1010。 6當(dāng)當(dāng)-6-6時(shí)，基變量時(shí)，基變量x x3 3 將小于零，用對(duì)偶單純形法求解得：將小于零，用對(duì)偶單純形法求解得： 611613 得得: :cj21000CB基基bx1x2x3x4x5021x3x1x20100011005/41/41/415/21/23/2cjzj0001/41/24521541274123cj21000CB基基bx1x2x3x4x5021x5x1x2010001-2

35、/15-1/151/5-1/61/60100cjzj00-1/151/3061161300,0,0,0,618319 z 當(dāng)當(dāng)-18-18時(shí)，基變量時(shí)，基變量x x1 1 將小于零，用對(duì)偶單純形法求解得：將小于零，用對(duì)偶單純形法求解得： cj21000CB基基bx1x2x3x4x5021x5x1x2010001-2/15-1/151/5-1/61/60100cjzj00-1/151/306116130初等變換得初等變換得 ：cj21000CB基基bx1x2x3x4x5021x5x3x2-2-153001010-1/2-2/51/2100cjzj-1001/3021725452112得得:-24

36、:-24-18 -18 0,0,0,0,00217254521122112 zcj21000CB基基bx1x2x3x4x5021x5x3x2-2-153001010-1/2-2/51/2100cjzj-1001/3021725452112 當(dāng)當(dāng)-24-24時(shí)時(shí), , 將小于零，但將小于零，但 所在行元素均為正；故這時(shí)問(wèn)題無(wú)可所在行元素均為正；故這時(shí)問(wèn)題無(wú)可行解。行解。 2x2xZ()隨參數(shù)隨參數(shù)的變化見(jiàn)下頁(yè)圖所示。的變化見(jiàn)下頁(yè)圖所示。 目標(biāo)函數(shù)目標(biāo)函數(shù) 值隨值隨 值變化的情況如下圖所示：值變化的情況如下圖所示：)(zZ() 12 6 0 -6 -18 -24 3.0 7.0 10.0 圖 2

37、當(dāng)當(dāng) 時(shí)時(shí)Z=10 當(dāng)當(dāng) 時(shí)時(shí) 當(dāng)當(dāng)-24-24-18 -18 時(shí)時(shí)無(wú)可行解無(wú)可行解 當(dāng)當(dāng) 時(shí)時(shí)66641217z618319 z2112 z 當(dāng)當(dāng)-24-24時(shí)時(shí)某工廠計(jì)劃期內(nèi)要安排生產(chǎn)某工廠計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)和產(chǎn)品所需的設(shè)備臺(tái)時(shí)和A A、B B兩種原材料的消耗、以及可獲利潤(rùn)兩種原材料的消耗、以及可獲利潤(rùn)如表所示，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？如表所示，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？ 1.1.用單純形法求解，并指出對(duì)偶規(guī)劃的解；用單純形法求解，并指出對(duì)偶規(guī)劃的解；2.2.若若b b1 1和和b b3 3不變，則不變，則b

38、 b2 2在什么范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)基不變；在什么范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)基不變； 3. c2在什么范圍內(nèi)變化時(shí)最優(yōu)解不變；在什么范圍內(nèi)變化時(shí)最優(yōu)解不變；4.增加一種新產(chǎn)品增加一種新產(chǎn)品，它的技術(shù)系數(shù)是，它的技術(shù)系數(shù)是(2，6，3)T，利潤(rùn)系數(shù)是，利潤(rùn)系數(shù)是5， 問(wèn)該廠問(wèn)該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？5.若生產(chǎn)產(chǎn)品若生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)有改進(jìn)，其技術(shù)系數(shù)變?yōu)椋ǖ墓に嚱Y(jié)構(gòu)有改進(jìn)，其技術(shù)系數(shù)變?yōu)椋?， 5 ，2)T，利潤(rùn)系，利潤(rùn)系數(shù)為數(shù)為4，試分析對(duì)生產(chǎn)計(jì)劃有什么影響？，試分析對(duì)生產(chǎn)計(jì)劃有什么影響？課堂作業(yè)課堂作業(yè) 可可利利用用資資源源 設(shè)設(shè)備備 原原材材料料 A

39、A 原原材材料料 B B 1 1 4 4 0 0 2 2 0 0 4 4 8 8 臺(tái)臺(tái)時(shí)時(shí) 1 16 6k kg g 1 12 2k kg g 利利潤(rùn)潤(rùn) 2 2 3 3 ？元元 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 8 16 12 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 - -z 0 2 3 0 0 0 解（1） 初始表 X(3)=(4，2，0，0, 4)T， z3 =14cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-21/21/41/2-1/8010-1400-3/2-1/80最終表0,125. 0, 5 . 1*3*2*1yyy解：（2）所以，b2的變化范圍是-8，16；b2的變化范圍是8，32。 000125050 250 2440 0 2211b.bBbB 可得