




已閱讀5頁,還剩61頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
第二章 線性規(guī)劃對(duì)偶理論,第一節(jié) 線性規(guī)劃對(duì)偶理論 第二節(jié) 對(duì)偶問題基本性質(zhì) 第三節(jié) 影子價(jià)格 第四節(jié) 對(duì)偶單純形法 第五節(jié) 靈敏度分析,1/66,第一節(jié) 線性規(guī)劃對(duì)偶理論,一、對(duì)偶問題的提出 例,2/66,3/66,生產(chǎn)是為贏利(取得收入)。還有別的辦法贏利(取得收入) 。例如,賣出或出租設(shè)備。 問,三種設(shè)備賣價(jià)或租價(jià)各應(yīng)是多少,進(jìn)項(xiàng)才不低于自己生產(chǎn)時(shí)的銷售收入?,原來的問題:兩種產(chǎn)品各生產(chǎn)多少,利潤總額最大?,4/66,用y1、y2和y3分別表示A、 B和 C三種設(shè)備單位臺(tái)時(shí)賣價(jià)或租價(jià),則,總進(jìn)項(xiàng)w可表示成 w=4y1 +12y2+18y3 生產(chǎn)兩種產(chǎn)品消耗的設(shè)備臺(tái)時(shí)的價(jià)值(或稱出售或出租兩種產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng))分別是 1y1 +0y2+3y3 和 0y1 +2y2+2y3 兩種產(chǎn)品售價(jià)分別是3和5。出售或出租產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)不能低于售價(jià)。所以,應(yīng)有 1y1 +0y2+3y3 3 和 0y1 +2y2+2y3 5 從另一個(gè)角度看,w=4y1 +12y2+18y3是總消耗。,5/66,回答y1、y2和y3各是多少的問題,可表示如下: Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 2y2 +2y3 5 y1, y2, y30 該問題叫做原問題(P)的對(duì)偶問題(D)??煽闯?, Max z=CX Min w=bTY (P) s.t. AXb (D) s.t. ATYCT X0 Y0,6/66,若要問對(duì)偶問題的解是什么,可以看解(P)時(shí)得到的最終單純形表。 最終單純形表,7/66,從該表松弛變量的檢驗(yàn)數(shù)行得到: 3 =0, 4 = -3/2,5 = -1, y1 =0,y2 = 3/2,y3 = 1,將其代入(D): w=40 +123/2+181=36 (1) 0 +31 =3 (2) 23/2+21 =5 (3) y1, y2, y30 (4) 這是對(duì)偶問題有趣的一個(gè)方面。,8/66,二、對(duì)稱的對(duì)偶問題一般形式 上面的例子叫做對(duì)稱的對(duì)偶問題。 三、非對(duì)稱的對(duì)偶問題 請(qǐng)見教科書第三版第52頁或第四版第53頁的表。,9/66,第二節(jié) 對(duì)偶理論基本性質(zhì),一、對(duì)稱形式單純形法矩陣表達(dá) Max z=CX s.t. AXb X0 化成標(biāo)準(zhǔn)形式 Max z=CX+0Xs s.t. AX+IXs=b X,Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛變量,10/66,令 X = XB ,(C, 0)=(CB, CN) Xs XN (A, I)=(B, N) z=CBB-1b+(CN-CBB-1N)XN (1) CN-CBB-1N是非基變量xm+1, xm+2, ,xn的檢驗(yàn)數(shù),令j =cj -CBB-1Pj,若所有的j 0,即 CN-CBB-1N0 (2) 則表示目前的基可行解最優(yōu)。另外,基變量XB 的檢驗(yàn)數(shù)是 CB-CBB-1B=0 (3),11/66,松弛變量Xs =(xs1, xs2, ,xsm)T的檢驗(yàn)數(shù)是 0-CBB-1I 0,即 -CBB-10 (4) 將(2)和(3)寫在一起: (CB,CN) - (CBB-1B,CBB-1N)0或 (CB,CN) - CBB-1(B,N)0 ,即 C- CBB-1A0 (5),12/66,再將(1) z=CBB-1b 、(5)和(4)寫在一起: z=CBB-1b (1) C- CBB-1A0 (5) -CBB-10 (4) 令YT=CBB-1,w=YTb (1) C- YTA0 (5) -YT0 (4) 或 w=YTb ATYCT Y0,13/66,Min w=YTb (D) s.t. ATYCT Y0 添加剩余變量后,變成 Min w=YTb+0Ys (D) s.t. ATY-IYs=CT Y, Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余變量,14/66,15/66,例 Max z=3x1+5x2 s.t. x1 4 y1 (P) 2x2 12 y2 3x1+2x2 18 y3 x1,x2 0 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 x1 (D) 2y2 +2y3 5 x2 y1, y2, y30,Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1,x2 ,x3 ,x4 ,x5 0 Min w=4y1 +12y2+18y3 +0y4+0y5+My6+My7 s.t. y1 +3y3 -y4 +y6 = 3 (D) 2y2 + 2y3 -y5 +y7 =5 y1, y2, y3, y4, y5, y6, y7 0,16/107,17/66,對(duì)偶問題初始單純形表,3應(yīng)當(dāng)是18-5M,但錯(cuò)算為18-2M,所以誤選y2為換入變量。以下將錯(cuò)就錯(cuò)算下去。,18/66,對(duì)偶問題最終單純形表,19/66,重新算一遍, 對(duì)偶問題初始單純形表,20/66,對(duì)偶問題最終單純形表,計(jì)算結(jié)果同上。,21/66,(P)最終單純形表,22/66,(D)對(duì)偶問題最終單純形表,二、對(duì)偶問題基本性質(zhì) 1. 弱對(duì)偶性。若 (1jn)和 (1im)分別是(P)和(D)的可行解,則恒有 C bT 證: C = = ,回想ATYCT ,即 cj PjTY= = ,所以,有 C = = = ( = ) ,另一方面,bT = = ,回想AXb ,即 bi = ,所以,有 bT = = = ( = ) ,證畢。,23/107,推論1 (P)任一可行解目標(biāo)函數(shù)值是(D)目標(biāo)函數(shù)值下界。反之, (D)任一可行解目標(biāo)函數(shù)值是(P)目標(biāo)函數(shù)值上界。 推論2 若(P)有可行解且目標(biāo)函數(shù)值無界,則(D)無可行解;反之, (D)有可行解且目標(biāo)函數(shù)無界,則(P)無可行解。當(dāng) (D)無可行解時(shí), (P)無可行解或目標(biāo)函數(shù)值無界。 推論3 若(P)有可行解,而(D)無可行解,則(P)目標(biāo)函數(shù)值無界;反之, (D)有可行解,而(P)無可行解,則(D)目標(biāo)函數(shù)值無界。,24/66,2. 最優(yōu)性。若 (j=1, 2, , n)和 (i=1, 2, , m)分別是(P)和(D)的可行解,且有 C =bT 則 和 分別是(P)和(D)的最優(yōu)解。 證明:設(shè)X*和Y *分別是(P)和(D)的最優(yōu)解。則有C CX * ,bTY * bT ,即bTYbT =C CX * 另一方面,根據(jù)性質(zhì)1,CX * bTY * ,這就是說CX * =bTY * ,證畢。,25/107,3. 對(duì)偶定理。若(P)和(D)均有可行解,則均有最優(yōu)解,且兩者的目標(biāo)函數(shù)值相等。 證明:由于(P)和(D)均有可行解,根據(jù)弱對(duì)偶性推論1,(P)目標(biāo)函數(shù)值有上界, (D)目標(biāo)函數(shù)值有下界,因此,(P)和(D)都有最優(yōu)解。另外,根據(jù) ATYCT,Y0,w=YTb=CBB-1b=z知道,當(dāng)(P)取得最優(yōu)解時(shí),(D)有可行解,且有w=z,根據(jù)性質(zhì)2(最優(yōu)性), (D)的可行解也是最優(yōu)解,證畢。,26/107,4. 互補(bǔ)松弛性。若 和 分別是(P)和 (D)的可行解,那么, TXs=0和 TYs=0的充分必要條件是 和 分別是(P)和 (D)的最優(yōu)解。 證明: Max z=CX+0Xs (P) s.t. AX+IXs=b X,Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛變量 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y,Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余變量,27/107,z=CX+0Xs=(YTA-IYsT)X+0Xs=YTAX-IYsTX w=bTY-0Ys=(AX+IXs)TY-0Ys=XTATY+IXsTY 若 TXs=0和 TYs=0 ,有z=w,根據(jù)性質(zhì)2,知 和 是最優(yōu)解。若 和 是最優(yōu)解,則有z=w,即 CX=YTAX-IYsTX=bTY=XTATY+IXsTY 或 YTAX-IYsTX=XTATY+IXsTY 或 -YsTX=XsTY 即 YsTX=XsTY=0 證畢。,28/107,第三節(jié) 影子價(jià)格,一、影子價(jià)格 在例子 Max z=3x1+5x2 s.t. x1 4 (P) 2x2 12 3x1+2x2 18 x1,x2 0 bT=(4, 12, 18)是資源,即可利用的設(shè)備臺(tái)班量。在討論如何才能贏利最多時(shí),沒有考慮三種設(shè)備單位臺(tái)班的價(jià)格。它們的價(jià)格藏在深處。,29/66,30/66,有些經(jīng)濟(jì)學(xué)家認(rèn)為,自由的市場(chǎng)交易,商品成交價(jià)格能夠反映其真正價(jià)值。但是,資源的現(xiàn)實(shí)市場(chǎng)價(jià)格并不反映其“真正”價(jià)值。還有些經(jīng)濟(jì)學(xué)家認(rèn)為,影子價(jià)格是原本無交易的資源,在轉(zhuǎn)為其他用途時(shí)的價(jià)格,或者說,另外再增加一個(gè)單位此種資源需要付出的價(jià)格。這個(gè)問題可以利用對(duì)偶問題的解給予某種解釋。 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 (D) 2y2 +2y3 5 y1, y2, y30 其解是(Y, Ys)T=(y1, y2, y3, y4, y5) =(0, 3/2, 1, 0, 0),31/66,這就是說,三種設(shè)備每臺(tái)時(shí)的價(jià)格分別是0, 3/2和1。第一種設(shè)備每臺(tái)時(shí)的價(jià)格為0,這是什么意思? 請(qǐng)看原問題 Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1,x2 ,x3 ,x4 ,x5 0 其解是(X, Xs)T=(x1, x2, x3, x4, x5) =(2, 6, 2, 0, 0),32/66,x3=2,也就說,第一種設(shè)備臺(tái)時(shí)有余裕,再增加其臺(tái)時(shí),無助于增加利潤,因此,“另外再增加一個(gè)單位此種資源需要付出的價(jià)格”為0。 第i種資源“再增加一個(gè)單位需要付出的價(jià)格”=limit w/ b=w/b=bTY/b=Y,這就是說,Y設(shè)備臺(tái)時(shí)的影子價(jià)格。 w/b1 y1 w= w/b= w/b2 = y2 =Y . . . . . . w/bm ym,33/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,34/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,x1=5,z=36-36=0,35/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(5/3, 6.5),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,2x2=13,z=3x1+5x2=37.5,z=37.5-36=1.5,36/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,z=3x1+5x2=37,3x1+2x2=19,z=37-36=1,第四節(jié) 對(duì)偶單純形法,一、對(duì)偶單純形法思路 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y,Ys0,37/66,二、對(duì)偶單純形法計(jì)算步驟,Step1:找出初始可行基、初始單純形表和初始基解。 Step2:若B-1b0,初始基解是最優(yōu)解,停。否則,下一步。 Step3:取(B-1b)l=min(B-1b)i|(B-1b)i0,第l行基變量換出。若所有的alj0,無可行解,停。 Step4:計(jì)算k/alk=minj/alj|alj0,第k列非基變量換入。 Step5:求基的逆矩陣、新基解和z。回Step2。,38/107,39/66,例1 Min w=4x1+12x2 +18x3 s.t. x1 + 3x3 3 2x2 + 2x3 5 x1,x2 ,x3 0 將其改寫如下: Max -w= -4x1-12x2 -18x3+0x4+0x5 s.t. -x1 - 3x3 +x4 = - 3 -2x2 -2x3 +x5 = -5 x1,x2 ,x3 ,x4 ,x5 0,40/66,初始單純形表,先確定換出變量,再換入變量,41/66,求B-1,再確定換出變量和換入變量,,42/66,求B-1,判斷是否最優(yōu),第五節(jié) 靈敏度分析,問題的由來,先看一個(gè)方程 x1+ x2=10 1.01x1+ x2=11, x1=100, x2= -90 如果1.01增加到1.011,該方程解會(huì)如何變化? x1+ x2=10 1.011x1+ x2=11, x1=1/0.011=90.91, x2= -80.91 a21/a21 =0.001/1.01=0.1%, x1/x1 =(90.91-100)/100=-9%,43/66,再看另外一個(gè)方程 x1+ x2=10 2.02x1+ x2=11, x1=0.980, x2= 9.020 如果2.02增加到2.022,該方程解會(huì)如何變化? x1+ x2=10 2.022x1+ x2=11, x1=0.978, x2= 9.022 a21/a21 =0.002/2.02=0.1%, x1/x1 =(0.978-0.980)/0.980=0.2%, 這時(shí)候,可以說,第一個(gè)方程組的解對(duì)于a21敏感,而第一個(gè)方程組則否。,44/66,實(shí)際問題的數(shù)學(xué)模型,應(yīng)當(dāng)避免第一種情況,因?yàn)閷?shí)際中很難避免將1.011算成1.01。 LP問題也會(huì)遇到類似情況。其中A、b和C都是從實(shí)際中收集、歸納和整理的數(shù)字,很難保證與實(shí)際情況絲毫不差。 如果LP問題的解因?yàn)檫@些數(shù)字與實(shí)際稍有偏差就會(huì)相差很大,那就說明利用A、b、C構(gòu)造的LP問題模型不能用做實(shí)際問題的模型。 合理的 LP問題模型不應(yīng)敏感于A、b或C的些小變化。本節(jié)課學(xué)習(xí),當(dāng) A、b或C發(fā)生小變動(dòng)時(shí),最優(yōu)解將如何變化,看一看對(duì)這些變化的敏感性。,45/66,靈敏度分析的步驟: 1. 先用最終單純形表中B-1變換A、b和C的增量 b =B-1b, Pj =B-1Pj , 2. 檢查(P)是否仍為可行解。 3. 檢查(D)是否仍為可行解。 4. 根據(jù)下表中各種情況決定下一步行動(dòng)。,46/66,一、分析C的變化 問題1 若兩種產(chǎn)品單價(jià)分別變成5元/件和3.25元/件,兩種產(chǎn)品最優(yōu)產(chǎn)量是否變化? 問題2 使最優(yōu)產(chǎn)量不變的第二種單價(jià)變化范圍多大?,47/66,48/66,為了回答問題1,將兩種產(chǎn)品改變后的單價(jià)填入最終單純形表,并重新計(jì)算檢驗(yàn)數(shù),得到:,為了回答問題2,用5+c2表示第二種產(chǎn)品改變后的單價(jià),并填入最終單純形表,并重新計(jì)算檢驗(yàn)數(shù),得到: c4=-3/2-c2/2,若使最優(yōu)解不變,則須有c40 -3/2-c2/20,c2-3,49/66,若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價(jià)變化范圍,則用3+c1表示第一種產(chǎn)品改變后的單價(jià),并填入最終單純形表,并重新計(jì)算檢驗(yàn)數(shù): c4=-3/2+c1/3, c5=-1-c1/3,若使最優(yōu)解不變,則須有c40,c50,-3/2+c1/30, -1-c1/30, -3c19/2,50/66,二、分析b的變化 若b=(0, b2, 0)T,問最優(yōu)解是否改變,為此,先計(jì)算 b2/3 b =B-1b = = b2/2 -b2/3 將其添入最終單純形表中,得到:,51/66,52/66,為使第二種設(shè)備可用臺(tái)時(shí)改變后的解仍然可行,須有:2+b2/30, 6+b2/20, 2-b2/30, max-6, -12b2min6, -6b26, 對(duì)于b1和b3,同樣處理。,三、分析增添新變量xj的情況 如果增加新產(chǎn)品x6 ,單價(jià)為4元,問如何生產(chǎn),總收入最多。設(shè)其所需三種設(shè)備臺(tái)時(shí)為 2 5/3 P6= 0 ,變換,得P6 = = 0 1 1/3 將P6 填入最終單純形表,并重新計(jì)算檢驗(yàn)數(shù):,53/66,54/66,四、分析技術(shù)系數(shù)aij變化時(shí)的情況 如果aij對(duì)應(yīng)的xj是非基變量,處理辦法同“三”。如果xj是基變量,先變換Pj, Pj =B-1Pj 例1第二種產(chǎn)品用設(shè)備臺(tái)時(shí)由 0 改為 0 2 P2 = 2 2 3/2 單價(jià)由5元增加為5.5元/件,用x*2表示這種“新”產(chǎn)品產(chǎn)量,先變換P2如下,然后添入最終單純形表,并重新計(jì)算檢驗(yàn)數(shù):,55/66,1/6 P
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 全球環(huán)保產(chǎn)業(yè)技術(shù)創(chuàng)新與市場(chǎng)前景分析報(bào)告2025
- BLX-3887-生命科學(xué)試劑-MCE
- 寧夏葡萄酒與防沙治沙職業(yè)技術(shù)學(xué)院《中國文學(xué)導(dǎo)讀》2023-2024學(xué)年第一學(xué)期期末試卷
- 滄州師范學(xué)院《綜藝節(jié)目編導(dǎo)》2023-2024學(xué)年第一學(xué)期期末試卷
- 內(nèi)蒙古師范大第二附中2024年化學(xué)九年級(jí)第一學(xué)期期末達(dá)標(biāo)測(cè)試試題含解析
- 武昌首義學(xué)院《中外經(jīng)典戲劇作品選講》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024年河北省石家莊市橋西區(qū)九年級(jí)化學(xué)第一學(xué)期期末質(zhì)量檢測(cè)模擬試題含解析
- 共享出行信用保險(xiǎn)與信用體系構(gòu)建研究報(bào)告
- 2025全球勞動(dòng)力趨勢(shì)報(bào)告第1期
- 2024年山東省青島市廣雅中學(xué)七年級(jí)數(shù)學(xué)第一學(xué)期期末達(dá)標(biāo)檢測(cè)模擬試題含解析
- 陜西省金太陽2024-2025學(xué)年高二期末教學(xué)質(zhì)量檢測(cè)英語(含答案)
- 2025至2030中國中小型風(fēng)電行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025-2030中國油田化學(xué)品行業(yè)市場(chǎng)深度調(diào)研及行情監(jiān)測(cè)與投資前景研究報(bào)告
- 2025年烏魯木齊危險(xiǎn)品駕駛員模擬試題
- 2025至2030中國質(zhì)子束治療系統(tǒng)行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 自主招生面試題及答案
- 深基坑監(jiān)測(cè)管理制度
- 2025年甘肅省民航機(jī)場(chǎng)集團(tuán)校園招聘45人筆試參考題庫帶答案詳解
- 2025年高考真題-英語(全國一卷) 含答案
- 2025-2030年中國線纜設(shè)備行業(yè)市場(chǎng)現(xiàn)狀供需分析及投資評(píng)估規(guī)劃分析研究報(bào)告
- 兒童情商課件
評(píng)論
0/150
提交評(píng)論