教案對偶理論

設(shè)B為A中的一個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改進單純形法單純形法中，除換入變量外，非基變量系數(shù)列的迭代運算是多余的。為了減少計算量和存儲量，產(chǎn)生了改進單純形法。當(dāng)m<<n時這種改進的效果明顯。實際問題：某養(yǎng)雞所用的混合飼料由A、B、C三種配料組成，下表給出了1單位各種配料所含的營養(yǎng)成分、單位成本以及1份飼料必須含有的各種成份。問如何配制混合飼料使成本最小？

營養(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

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

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

￡6q1+1/2q2+q3

￡3q1+1/4q2+q3

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

MaxZ=2x1+3x2

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

甲乙可用量機械設(shè)備128原材料A4016原材料B0412對偶問題的定義標準型為：列向量行向量n個變量n個約束

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

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

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

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

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

設(shè)X*和Y*分別(P）問題(D）問題的可行解，則它們分別是最優(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對偶變量不為0，原問題相應(yīng)約束式是等式原問題約束為不等式，相應(yīng)對偶變量為0最優(yōu)解點檢驗數(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對偶問題的經(jīng)濟解釋—

影子價格

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

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

甲乙可用量機械設(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)濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。影子價格

產(chǎn)品資源ⅠⅡ現(xiàn)有資源數(shù)鋼材12100（噸）煤22180（噸）機時16240（小時）利潤（萬元）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影子價格經(jīng)濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。影子價格的意義(1)影子價格客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。如果某一資源在系統(tǒng)內(nèi)供大于求（即有剩余），其影子價格就為零。如果某一資源是稀缺的（即相應(yīng)約束條件的剩余變量為零）,則其影子價格必然大零。影子價格越高，資源在系統(tǒng)中越稀缺。(2)影子價格是對系統(tǒng)資源的一種優(yōu)化估價，只有當(dāng)系統(tǒng)達到最優(yōu)時才能賦予該資源這種價值，因此也稱最優(yōu)價格。(3)影子價格的取值與系統(tǒng)狀態(tài)有關(guān)。系統(tǒng)內(nèi)部資源數(shù)量、技術(shù)系數(shù)和價格的任何變化，都會引起影子價格的變化，它是一種動態(tài)價格。(4)如果考慮擴大生產(chǎn)能力，應(yīng)該從影子價格高的設(shè)備入手?！?對偶單純形法保持對偶可行性，逐步改進主可行性，求解主問題。

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

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

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

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300先選出基變量后選進基變量原問題，符合原始最優(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