運(yùn)籌學(xué)基礎(chǔ)課件 1

1、主講教師：,聯(lián)系電話： 短 號(hào)：,E-mail:,清華大學(xué)出版社,運(yùn)籌學(xué)教程（第三版）,運(yùn)籌學(xué)基礎(chǔ),胡運(yùn)權(quán) 主編,教材,運(yùn) 籌 學(xué) 課 件 第二章,Linear progranming,對(duì)偶理論 與 靈敏度分析,例一,美佳公司計(jì)劃制造、兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況如下表所示。問該公司應(yīng)制造、兩種家電備多少件,使獲取的利潤(rùn)為最大。,第一節(jié) 線性規(guī)劃的對(duì)偶問題,一、對(duì)偶問題的提出,1）標(biāo)準(zhǔn)化,）寫出初始單純形表（假設(shè)存在有單位矩陣）,2 1 0 0 0,）最優(yōu)解檢驗(yàn)（唯一解、無(wú)限多解、無(wú)界

2、解和無(wú)解）,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,一個(gè)問題？,市場(chǎng)上設(shè)備A、設(shè)備B和調(diào)試工序每小時(shí)值多少錢？在什么價(jià)位時(shí)，可以出租或去租借適當(dāng)數(shù)量的資源來擴(kuò)大生產(chǎn)規(guī)模？,6y2 + y3,分 析,設(shè)： y1 設(shè)備A值的價(jià)值 y2 設(shè)備B值的價(jià)值 y3 調(diào)試工序值的價(jià)值,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,總價(jià)值,min,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2

3、y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,問題求解,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,Y=(0, , , 0, 0),z=-17/2,z = 17/2,問題求解,Y*=(0, , , 0, 0 ),問題分析,問題 的解,問題：,？,原問題：,問題 的解,X*=(7/2,3/2,15/2,0,0),Z*= 17/2,

4、Z*= 17/2,5*3/2 = 15/2,15,結(jié) 論,兩個(gè)問題的最優(yōu)解的值一致 最大值問題的最優(yōu)解是最小值問題的可行解 一個(gè)問題的剩余變量（松弛變量） 不為0（即有資源剩余），則對(duì)應(yīng)問題的解為0 一個(gè)決策變量不為0，則對(duì)應(yīng)的問題的約束條件的剩余變量(松弛變量) 為0(即無(wú)資源剩余),估價(jià)影子價(jià)格 （即增加單位資源所得到的貢獻(xiàn)）,Z= =CX=Yb Z/ b=(Yb) =Y,二、對(duì)稱形式下對(duì)偶問題的一般形式,對(duì)稱形式的定義,對(duì)稱形式,X 0,st.,AX b,max z =,CX,其中： C=（c1，c2, ,cn) b=（b1，b2, ,bm)T X=（x1，x2, ,xn)T Y=（y1

5、，y2, ,ym)T,A=,a11 a12 a1n a21 a22 a2n am1 am2 anm,Y 0,st.,ATY CT,min w =,YTb,三、非對(duì)稱形式的原對(duì)偶問題關(guān)系,非對(duì)稱形式？,x1 0, x2 0, x3無(wú)約束,st.,a11x1+a12x2+a13x3 b1 a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 b3,max z = c1x1 + c2x2 +c3x3,x1 , x2, x3，x3 0,st.,a11x1 - a12x2 + a13x3- a13x3 b1 a21x1 - a22x2 + a23x3- a23x3 b2 -a

6、21x1 + a22x2 _ a23x3+ a23x3 -b2 -a31x1 + a32x2 - a33x3+ a33x3 -b3,max z = c1x1 - c2x2 + c3x3 - c3x3,y1 , y2, y2 ，y30,st.,a11y1 + a21y2 a21y2 - a31y3 c1 -a12y1 - a22y2+ a22y2 - a32y3-c2 a13y1 + a23y2 a23y2- a33y3 c3 -a13y1 - a23y2+ a23y2+ a33y3-c3,min w = b1y1 + b2y2- b2y2 - b3y3,min w = b1y1 + b2y2

7、+ b3y3,a11y1 + a21y2 + a31y3 c1 a12y1 + a22y2 + a32y3 c2 a13y1 + a23y2 + a33y3 = c3,st.,y10, y2無(wú)約束，y3 0,對(duì)偶規(guī)則 變量、約束與系數(shù),原問題有m個(gè)約束條件，對(duì)偶問題有m個(gè)變量 原問題有n個(gè)變量，對(duì)偶問題有n個(gè)約束條件 原問題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問題的右端項(xiàng) 原問題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問題的價(jià)值系數(shù) 原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問題系數(shù)矩陣 原問題的約束條件與對(duì)偶問題方向相反 原問題與對(duì)偶問題優(yōu)化方向相反,對(duì)偶規(guī)則 變量與約束對(duì)應(yīng)關(guān)系,第二節(jié) 對(duì)偶問題的基本性質(zhì),X 0,st.,AX b,max

8、z = CX,X, Xs 0,st.,AX + IXs = b,max z = CX + 0Xs,一、單純形法計(jì)算的矩陣描述,B與B-1,Y=(0, , , 0, 0 ),X*=(7/2,3/2, 15/2,0,0),二、原問題和對(duì)偶問題解的關(guān)系,第二節(jié) 對(duì)偶問題的基本性質(zhì),對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題 弱對(duì)偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問題任意可行解的目標(biāo)函數(shù)值。P56推論 無(wú)界性：原問題有可行解且z無(wú)界，對(duì)偶問題無(wú)可行解。 對(duì)偶定理：若原問題與其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解且最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值相等。若原問題最優(yōu)基為B，則其對(duì)偶問題最優(yōu)解Y*=

9、CBB-1 互補(bǔ)松弛性：,需要說明的是：這些性質(zhì)同樣適用于非對(duì)稱形問題,T,T,對(duì)偶定理的證明,X 0,st.,AX b,max z = CX,對(duì)稱形式,Y 0,st.,ATY CT,min w = YTb,原問題為優(yōu)解0，即：,CB-CBB-1B 0 CN-CBB-1N 0 -CBB-1 0,C - CBB-1A0,令YT= CBB-1,則有：,CBB-1 0,ATY CT Y 0,w = YTb = CBB-1b = z 即此時(shí)原問題與對(duì)偶問題的解的值是相等的。,則可以得到：,Y*=(0, , , 0, 0 ),互補(bǔ)松弛性：,問題 的解,對(duì)偶問題：,？,原問題：,問題 的解,X*=(7/2

10、,3/2,15/2,0,0),Z*= 17/2,Z*= 17/2,5*3/2 = 15/2,15,互補(bǔ)松弛性,當(dāng)原問題約束0,則yi=0 未充分利用。 yi0,原問題約束為等式。資源得到充分利用，即xsi=0。,第三節(jié) 影子價(jià)格,一、原問題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問題,單位產(chǎn)品的利潤(rùn)（元/件）,產(chǎn)品產(chǎn)量（件）,總利潤(rùn)（元）,資源限量（噸）,單位產(chǎn)品消耗的資源（噸/件）,剩余的資源（噸）,消耗的資源（噸）,二、對(duì)偶問題是資源定價(jià)問題,資源限量（噸）,資源價(jià)格（元/噸）,總利潤(rùn)（元）,對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、.、ym稱為m種資源的影子價(jià)格（Shadow Price）,原始

11、和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤(rùn) max z=min y,三、資源影子價(jià)格的性質(zhì),影子價(jià)格代表在資源最優(yōu)利用條件下對(duì)單位第i種資源的估價(jià)。,市場(chǎng)價(jià)格是已知數(shù)，相對(duì)穩(wěn)定。影子價(jià)格依賴于資源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等的變化而變化。,資源影子價(jià)格是一種邊際價(jià)格,影子價(jià)格越大，說明增加這種資源越帶來的z增加越多， 該資源是相對(duì)緊缺的。 影子價(jià)格越小，說明增加這種資源越帶來的z增加越少， 該資源是相對(duì)不緊缺的。 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,w1 w2 wm,影子價(jià)格是一種機(jī)會(huì)成本,增加單位資源可以增加的利潤(rùn),減少一件產(chǎn)品可以節(jié)省的資源,機(jī)會(huì)成本

12、 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn),在純市場(chǎng)經(jīng)濟(jì)下，當(dāng)市場(chǎng)價(jià)格y*時(shí)，賣出該資源，否則當(dāng)市場(chǎng)價(jià)格y*時(shí)，買進(jìn)該資源。,隱含成本,利潤(rùn),差額成本,產(chǎn)品的差額成本（Reduced Cost）,差額成本=機(jī)會(huì)成本 - 利潤(rùn),第四節(jié) 對(duì)偶單純形法,對(duì)于單純形法疊代過程本質(zhì)：1）確保z變大； 2）B-1b 0,由對(duì)偶理論知道，當(dāng)原問題為最優(yōu)解時(shí)，-0且為對(duì)偶問題的最優(yōu)解，因此人們提出對(duì) 偶單純形法。疊代過程本質(zhì)：1） 0； 2）逐步使B-1b 0,與,設(shè)原問題為 max z=CX AX=b X0 又設(shè)B是一個(gè)基。不失一般性，令B=（P1,P2,Pm）,它對(duì)應(yīng)的變量為XB=(x1,x2,xm)

13、當(dāng)非基變量都為0時(shí)，可以得到XB=B-1b.若B-1b中至少有一個(gè)負(fù)分量，設(shè)（B-1b）I0,并且在單純形表的檢驗(yàn)數(shù)行中得檢驗(yàn)數(shù)都為非正，即對(duì)偶問題保持可行解。 每次迭代是將基變量中的負(fù)分量xl取出，取替換非基變量中的xk,經(jīng)基變換，所有檢驗(yàn)數(shù)仍保持非正，從原問題來看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近，當(dāng)原問題得到可行解時(shí)，便得到了最優(yōu)解。,對(duì)偶單純形法的計(jì)算步驟：,（1）根據(jù)線性規(guī)劃問題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則得到了最優(yōu)解。停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行下一步計(jì)算。 （2） 確定換出變量按 對(duì)應(yīng)的

14、基變量xl為換出變量。,（3） 確定換出變量 在單純形表中檢查xl所在行的各系數(shù)alj0,則無(wú)可行解。停止計(jì)算。 若存在alj0(j=1,2,n),計(jì)算 按規(guī)則所對(duì)應(yīng)的列的非基變量xk為換入變量，這樣才能保持得到的對(duì)偶問題解仍然為可行解。,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,例一,6y2 + y3,2,5y1 + 2y2 + y3,1,z= 15 y

15、1 + 24y2 + 5y3,min,z= -15 y1 - 24y2 - 5y3,max,6y2 + y3 y4,=,2,5y1 + 2y2 + y3 y5,1,=,y1, y2, y3, y4, y5,=,0,-15 0 -1 -4 0,y2 y5,-24 0,-24 -5,y2 y3,-15 0 0 -7/2 3/2,對(duì)偶單純形法優(yōu)點(diǎn),初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。 當(dāng)變量個(gè)數(shù)多于約束條件個(gè)數(shù)，對(duì)這樣的線性規(guī)劃問題，用對(duì)偶單純形法可以減少計(jì)算的工作量。因此對(duì)變量較少而約束條件很多的線性規(guī)劃問題，可以先將它變?yōu)閷?duì)偶問

16、題，然后用對(duì)偶單純形法求解。 在靈敏度分析中,有時(shí)需要用對(duì)偶單純形法，可使問題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是對(duì)大多數(shù)線性規(guī)劃問題，很難找到一個(gè)初始可行基，因而這方法很少單獨(dú)使用。,第五節(jié) 靈敏度分析,靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。,當(dāng)線性規(guī)劃問題的系數(shù)發(fā)生變化時(shí)，最優(yōu)解一般要發(fā)生變化，主要有以下幾種情況：,當(dāng)線性規(guī)劃問題的系數(shù)發(fā)生變化時(shí)，最優(yōu)解一般要發(fā)生變化，主要有以下幾種情況：,第五節(jié) 靈敏度分析,靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。,一、目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析,可以分別就cj時(shí)對(duì)應(yīng)的非基變量和基變量?jī)煞N情況

17、來討論。,（1） 若cj是非基變量xj的系數(shù)，這時(shí)他在計(jì)算表中所對(duì)應(yīng)的檢驗(yàn)數(shù)是 當(dāng)cj變化cj時(shí)，要保證最終表中這個(gè)檢驗(yàn)數(shù)仍然小于或等于零，即 j=cj+cj- CBB-1Pj0 那么cj+cjYPj,即cj的值必需小于或等于YPj-cj,才可以滿足原最優(yōu)解條件，這可以確定cj的變化范圍了。,下面就各種情況分別進(jìn)行討論。,(2)若cr是基變量xr的系數(shù)。因crCB,當(dāng)cr變化cr時(shí)，就引起CB的變化，這時(shí) (CB+CB)B-1A=CB B-1A+(0, cr,0) B-1A = CB B-1A+cr(ar1,ar2,arn) 可見當(dāng)cr變化cr時(shí)，最終表中的檢驗(yàn)數(shù)是 j=cj - CBB-1A-cjarj,j=1,2,n,若要求原最優(yōu)解不變，即必需滿足j0。于是得到 當(dāng)arj0，crj/a rj j=1,2,n cr可變化的范圍是 例題見書P64,二、資源數(shù)量bj變化的分析,資源數(shù)量變化是