運(yùn)籌學(xué)對(duì)偶問(wèn)題

運(yùn)籌學(xué)對(duì)偶問(wèn)題第1頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月4.1對(duì)偶問(wèn)題(1)對(duì)偶問(wèn)題的提出例1、生產(chǎn)組織與計(jì)劃問(wèn)題A,B各生產(chǎn)多少,可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉(cāng)庫(kù)AB123202單位利潤(rùn)4050306024第2頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件如果因?yàn)槟撤N原因，不愿意自己生產(chǎn)，而希望通過(guò)將現(xiàn)有資源承接對(duì)外加工來(lái)獲得收益，那么應(yīng)如何確定各資源的使用價(jià)格？第3頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件兩個(gè)原則所得不得低于生產(chǎn)的獲利要使對(duì)方能夠接受設(shè)三種資源的使用單價(jià)分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350第4頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月通過(guò)使用所有資源對(duì)外加工所獲得的收益W=30y1+60y2+24y3根據(jù)原則2，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問(wèn)題可歸結(jié)為以下數(shù)學(xué)模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問(wèn)題稱為原問(wèn)題，此問(wèn)題為對(duì)偶問(wèn)題，y1,y2,y3稱為影子價(jià)格第5頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(2)對(duì)偶問(wèn)題的形式定義設(shè)原線性規(guī)劃問(wèn)題為則稱下列線性規(guī)劃問(wèn)題為其對(duì)偶問(wèn)題，其中yi(i=1,2,…,m)稱為對(duì)偶變量。上述對(duì)偶問(wèn)題稱為對(duì)稱型對(duì)偶問(wèn)題。原問(wèn)題簡(jiǎn)記為(P)，對(duì)偶問(wèn)題簡(jiǎn)記為(D)第6頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月原始問(wèn)題MaxZ=CXs.t.AX≤b X≥0bAC≤Maxnm對(duì)偶問(wèn)題MinW=Ybs.t. YAT≥C Y≥0≥MinCTATbTnm第7頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月例2：求線性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知為對(duì)稱型對(duì)偶問(wèn)題第8頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月例3：求線性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問(wèn)題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。第9頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月例4：求線性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問(wèn)題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。第10頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月上式已為對(duì)稱型對(duì)偶問(wèn)題，故可寫(xiě)出它的對(duì)偶規(guī)劃令則上式化為第11頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月對(duì)偶關(guān)系對(duì)應(yīng)表原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)類(lèi)型MaxMin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系右邊項(xiàng)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對(duì)應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問(wèn)題變量類(lèi)型與

0

對(duì)偶問(wèn)題約束類(lèi)型變量

0約束

的對(duì)應(yīng)關(guān)系無(wú)限制＝原問(wèn)題約束類(lèi)型與

0對(duì)偶問(wèn)題變量類(lèi)型約束

變量

0的對(duì)應(yīng)關(guān)系＝無(wú)限制第12頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月4.2對(duì)偶問(wèn)題的基本性質(zhì)定理1對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0對(duì)偶的定義對(duì)偶的定義第13頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月定理2(弱對(duì)偶定理)分別為(P),(D)的可行解，則有CbX，yXy證明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb第14頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月推論2、(P)有可行解,但無(wú)有限最優(yōu)解，則(D)無(wú)可行解。定理3、yX,分別為(P),(D)的可行解，且XyC=b,則它們是(P),(D)的最優(yōu)解。證明：對(duì)任X，有CXby=CXX最優(yōu)推論1、(P),(D)都有可行解，則必都有最優(yōu)解。第15頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月定理4(主對(duì)偶定理)若一對(duì)對(duì)偶問(wèn)題(P)和(D)都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：(1)當(dāng)X*和Y*為原問(wèn)題和對(duì)偶問(wèn)題的一個(gè)可行解有原問(wèn)題目標(biāo)函數(shù)值對(duì)偶問(wèn)題目標(biāo)函數(shù)值所以原問(wèn)題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問(wèn)題有下界，也存在有限最優(yōu)解。第16頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(2)當(dāng)X*為原問(wèn)題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過(guò)引入松弛變量Xs,將問(wèn)題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令令所以Y*是對(duì)偶問(wèn)題的可行解，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為X*是原問(wèn)題的最優(yōu)解，原問(wèn)題的目標(biāo)函數(shù)值為第17頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月推論：若一對(duì)對(duì)偶問(wèn)題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對(duì)對(duì)偶問(wèn)題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個(gè)都無(wú)可行解；一個(gè)問(wèn)題無(wú)界，則另一問(wèn)題無(wú)可行解。第18頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月定理5若X,Y分別為(P),(D)的可行解，則X,Y為最優(yōu)解的充要條件是同時(shí)成立證:(必要性）原問(wèn)題對(duì)偶問(wèn)題第19頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.ATY-YS=C W,WS

≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù)第20頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的松弛變量原始問(wèn)題的變量原始問(wèn)題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0第21頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月4.3對(duì)偶問(wèn)題的解令設(shè)原問(wèn)題為為原問(wèn)題的一最優(yōu)解則為對(duì)偶問(wèn)題的一最優(yōu)解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1第22頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月例1MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW’=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t第23頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月MaxW’=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tC-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-My640130-101040/3-My7502220-10125Z-90M-30+3M-60+5M-24+2MMM00

第24頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月C-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-60y240/31/310-1/301/30

-My770/34/3022/3-1-2/31

Z-800-70M/3-10+4M/30-24+2M2M/3-M

0

-60y240/31/310-1/301/3040-24y335/32/3011/3-1/2-1/31/235/2Z-1080600-12-12

-60y215/201-1/2-1/21/41/6-1/4

-30y135/2103/21/2-3/4-1/23/4

Z-97500-9-15-15/2

第25頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月例1、MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.tX1+2X2+X3=303X1+2X2+X4=602X2+X5=24

X1–X50s.tCBXBBX1X2X3X4X5θ40X115101/2-1/20

0X59003/2-1/21

50X215/297501-3/41/40

Z

0

0

-35/2-15/2

0

第26頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月第27頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的松弛變量原始問(wèn)題的變量原始問(wèn)題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0第28頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月第29頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月C23-5-M0-MθCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0

-MX4207/21/211/2-1/24/72X151-5/21/20-1/21/2

Z2M-1003M/2+8M/2-60M/2+1-3M/2-1

3X24/7011/72/71/7-1/7

2X145/7106/75/7-1/71/7

Z102/700-50/7-M-16/7-1/7-M+1/7

第30頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(P)第31頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月第32頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月4.4影子價(jià)格(1)原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題單位產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）第33頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(2)對(duì)偶問(wèn)題資源限量（噸）資源價(jià)格（元/噸）總利潤(rùn)（元）對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（ShadowPrice）原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn)MaxZ=MinW第34頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(3)資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0第35頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月y1y2ym(4)產(chǎn)品的機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源第36頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月機(jī)會(huì)成本利潤(rùn)差額成本(5)產(chǎn)品的差額成本（ReducedCost）差額成本=機(jī)會(huì)成本-利潤(rùn)第37頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(6)互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋在利潤(rùn)最大化的生產(chǎn)計(jì)劃中（1）邊際利潤(rùn)大于0的資源沒(méi)有剩余（2）有剩余的資源邊際利潤(rùn)等于0（3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)（4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)第38頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月4.5對(duì)偶單純形法定義：設(shè)A=(BN)，其中B是一個(gè)非奇異的m×m階方陣，對(duì)應(yīng)地C=(CBCN)，則YB=CB的解Y*=CBB-1稱為對(duì)偶問(wèn)題(D)的一個(gè)基本解；若Y*還滿足Y*N≧CN，則稱Y*為(D)的一個(gè)基可行解；若有Y*N>CN，則稱Y*為非退化的基可行解，否則稱為退化的基可行解。(1)對(duì)偶單純形法的基本原理定義：如果原問(wèn)題(P)的一個(gè)基本解X與對(duì)偶問(wèn)題(D)的基可行解Y對(duì)應(yīng)的檢驗(yàn)數(shù)向量滿足條件則稱X為原問(wèn)題(P)的一個(gè)正則解。原問(wèn)題(P)的正則解X與對(duì)偶問(wèn)題(D)的基可行解Y一一對(duì)應(yīng)第39頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行(正則解)，但它對(duì)應(yīng)著一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶基可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的正則解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)正則解，此正則解對(duì)應(yīng)著另一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正）。如果得到的正則解的分量皆非負(fù)則該正則解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的正則解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。第40頁(yè)，課件共47頁(yè)，創(chuàng)作于2023年2月(2)對(duì)偶單純形法的迭代步驟建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；若b’≥0,則得到最優(yōu)解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉(zhuǎn)3若所有akj’≥0(j=1,2,…,n)，則原問(wèn)題無(wú)可行解,停止;否則,若有akj’<0則選=min{j’/akj’┃akj’<0}=r’/akr’那么x