教案對(duì)偶理論

設(shè)B為A中的一個(gè)m×m可行基，則可將A分為（B，N），同樣，將X分為（XB，XN）T，C亦分為（CB，CN），原模型maxz=CBXB+CNXN+0XS(2.1)BXB+NXN+IXS=b(2.2)XB，XN，XS≥0(2.3)XB=B-1b－B-1NXN－B-1XS

代入（2.1）式，有Z=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS

=CBB-1b+（CN－CBB-1N）XN－CBB-1XSZ=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS

=CBB-1b+（CN－CBB-1N）XN－CBB-1XS

-ZXBXNXS右端此方程組的系數(shù)增廣矩陣為：此方程組的系數(shù)增廣矩陣亦為：基變量非基變量XBXNXSI0B-1NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b單純形表的矩陣形式如例1的初始表和第三張表§2改進(jìn)單純形法單純形法中，除換入變量外，非基變量系數(shù)列的迭代運(yùn)算是多余的。為了減少計(jì)算量和存儲(chǔ)量，產(chǎn)生了改進(jìn)單純形法。當(dāng)m<<n時(shí)這種改進(jìn)的效果明顯。實(shí)際問(wèn)題：某養(yǎng)雞所用的混合飼料由A、B、C三種配料組成，下表給出了1單位各種配料所含的營(yíng)養(yǎng)成分、單位成本以及1份飼料必須含有的各種成份。問(wèn)如何配制混合飼料使成本最??？

營(yíng)養(yǎng)成分DEF單位成本ABC111???2116321份飼料應(yīng)含量20610設(shè):Xj=混合飼料中第j種配料的含量，j=A、B、CMinZ=6XA+3XB+2XCXA+XB+XC3201/2XA+1/2XB+1/4XC362XA+XB+XC310Xj30

有一個(gè)飼料廠，制造含有這3種營(yíng)養(yǎng)成份各1單位的營(yíng)養(yǎng)丸，知道養(yǎng)雞場(chǎng)對(duì)混合飼料的要求，因此，在制定營(yíng)養(yǎng)丸的價(jià)格時(shí)，使每丸D、E、F營(yíng)養(yǎng)丸的價(jià)格分別為q1、q2、q3。養(yǎng)雞場(chǎng)采購(gòu)1單位配料A,相當(dāng)于對(duì)3種營(yíng)養(yǎng)丸分別采購(gòu)1、1/2、2丸等，采購(gòu)1單位的B,相當(dāng)于對(duì)3種營(yíng)養(yǎng)丸分別采購(gòu)1、1/2、1丸等，采購(gòu)1單位的C,相當(dāng)于對(duì)3種營(yíng)養(yǎng)丸分別采購(gòu)1、1/4、1丸等，

因此飼料廠定營(yíng)養(yǎng)丸售價(jià)時(shí)，必須有：q1+1/2q2+2q3

￡6q1+1/2q2+q3

￡3q1+1/4q2+q3

￡2MaxZ=20q1+6q2+10q3設(shè)出租單位設(shè)備臺(tái)時(shí)的租金y1，轉(zhuǎn)讓原材料A、B的收費(fèi)為y2，y3。第一章例1生產(chǎn)組織問(wèn)題

MaxZ=2x1+3x2

x1+2x2≤84x1≤164x2≤12x1，x2≥0若工廠決策者準(zhǔn)備將所有資源出租或轉(zhuǎn)讓?zhuān)瑔?wèn)應(yīng)如何定價(jià)？設(shè)備原材Ay1y2原材By3

甲乙可用量機(jī)械設(shè)備128原材料A4016原材料B0412對(duì)偶問(wèn)題的定義標(biāo)準(zhǔn)型為：列向量行向量n個(gè)變量n個(gè)約束

證：AX=bAX≤bAX≥bAX≤b-AX≤-by′y〃解：設(shè)對(duì)偶變量為y1,y2,y3,對(duì)偶問(wèn)題模型為：Maxw=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3≥2≤3≤-5=1y1≥0,y2≤0,y3無(wú)約束4.2對(duì)偶問(wèn)題的基本性質(zhì)注意：(D)無(wú)可行解，(P)不一定為無(wú)界解。此性質(zhì)還說(shuō)明：(P)有可行解，(D)不一定有可行解。4、

可行解是最優(yōu)解時(shí)的性質(zhì)

設(shè)是(P)的可行解，是(D)的可行解，當(dāng)時(shí)，是最優(yōu)解。3、無(wú)界性

若（P）問(wèn)題可行，但目標(biāo)函數(shù)無(wú)界，則（D）問(wèn)題不可行。（D）不可行（P）無(wú)界（P）不可行利用弱對(duì)偶定理5、對(duì)偶定理若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。例1已知線性規(guī)劃問(wèn)題

試用對(duì)偶理論證明上述問(wèn)題無(wú)最優(yōu)解。無(wú)界性定理。（P）可行，但無(wú)界則（D）不可行。（D）不可行（P）無(wú)界（P）不可行對(duì)偶問(wèn)題X（0）=（0，0，0）T是原問(wèn)題的一個(gè)可行解對(duì)偶問(wèn)題不可行6、互補(bǔ)松弛定理

設(shè)X*和Y*分別(P）問(wèn)題(D）問(wèn)題的可行解，則它們分別是最優(yōu)解的充要條件是Y*（b-AX*)=0(Y*A-C)X*=0如何應(yīng)用該定理？AX*≤bAX*+XS*=bb-AX*=XS*Y*（b-AX*)=0Y*XS*=0對(duì)偶變量不為0，原問(wèn)題相應(yīng)約束式是等式原問(wèn)題約束為不等式，相應(yīng)對(duì)偶變量為0最優(yōu)解點(diǎn)檢驗(yàn)數(shù)行cj

CBXBbx1x2x3x4x5

-z

23000

4

1

00

1/40

4

0

0-2

1/21

2

0

11/2

-1/8

0-1400-1.5-1/8

0x1x5x2203§5對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋—

影子價(jià)格

(P)的最終單純形表中松弛變量的檢驗(yàn)數(shù)對(duì)應(yīng)(D)的最優(yōu)解。

當(dāng)某約束條件的右端常數(shù)增加一個(gè)單位時(shí)（假設(shè)原問(wèn)題的最優(yōu)基不變），原問(wèn)題的目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。Z*=CX*=Y*b=(y1*,y2*,…,ym*)b1b2﹕﹒bm=y1*b1+y2*b2+…+ym*bm當(dāng)某個(gè)右端常數(shù)bibi+1時(shí)bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I種資源的影子價(jià)格是第i個(gè)約束條件的右端常數(shù)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)增加的數(shù)量

甲乙可用量機(jī)械設(shè)備128原材料A4016原材料B0412

X(3)=(4，2，0，0,4)T，z3=14cj23000CBXBbx1x2x3x4x5203x1x5x2442100001-2?-3/2?-1/81/8010-1400-3/2-1/80經(jīng)濟(jì)意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。影子價(jià)格

產(chǎn)品資源ⅠⅡ現(xiàn)有資源數(shù)鋼材12100（噸）煤22180（噸）機(jī)時(shí)16240（小時(shí)）利潤(rùn)（萬(wàn)元）13x1x2x3x4x5-zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T,Z*=135y1*=1/4y2*=0,y3*=1/4影子價(jià)格經(jīng)濟(jì)意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。影子價(jià)格的意義(1)影子價(jià)格客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。如果某一資源在系統(tǒng)內(nèi)供大于求（即有剩余），其影子價(jià)格就為零。如果某一資源是稀缺的（即相應(yīng)約束條件的剩余變量為零）,則其影子價(jià)格必然大零。影子價(jià)格越高，資源在系統(tǒng)中越稀缺。(2)影子價(jià)格是對(duì)系統(tǒng)資源的一種優(yōu)化估價(jià)，只有當(dāng)系統(tǒng)達(dá)到最優(yōu)時(shí)才能賦予該資源這種價(jià)值，因此也稱(chēng)最優(yōu)價(jià)格。(3)影子價(jià)格的取值與系統(tǒng)狀態(tài)有關(guān)。系統(tǒng)內(nèi)部資源數(shù)量、技術(shù)系數(shù)和價(jià)格的任何變化，都會(huì)引起影子價(jià)格的變化，它是一種動(dòng)態(tài)價(jià)格。(4)如果考慮擴(kuò)大生產(chǎn)能力，應(yīng)該從影子價(jià)格高的設(shè)備入手。§6對(duì)偶單純形法保持對(duì)偶可行性，逐步改進(jìn)主可行性，求解主問(wèn)題。

當(dāng)b有負(fù)分量，A中有一明顯初始對(duì)偶可行基(檢驗(yàn)數(shù)均非正)，因而易得一初始解時(shí)，可用對(duì)偶單純形法求解。

設(shè)B為一個(gè)基基本解X（0）為基本可行解的條件？B-1b≥0X（0）為最優(yōu)解的條件？原原始可行性條件原始最優(yōu)性條件令Y=CBB-1，代入原始最優(yōu)性條件，→YA≥C對(duì)偶可行性條件例用對(duì)偶單純形法求解單純形法大M法剩余變量、人工變量

用（-1）乘不等式兩邊，再引入松弛變量。cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300先選出基變量后選進(jìn)基變量原問(wèn)題，符合原始最優(yōu)性條件，但不可行cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2