對偶理論吉清凱第1頁，課件共23頁，創(chuàng)作于2023年2月這里的對偶是指同一事物從不同角度觀察，有兩種對立的表述。如“平面中矩形的面積與周長的關(guān)系”有兩種表述：周長一定，面積最大（MAX）的矩形是正方形；面積一定，周長最短（MIX）的矩形是正方形。例一、資源的合理利用問題已知資料如表所示，問應(yīng)如何安排生產(chǎn)計劃使得既能充分利用現(xiàn)有資源有使總利潤最大？1810單件利潤150（設(shè)備）51C100（煤炭）32B170（鋼材）25A資源限制乙甲單件產(chǎn)消耗品資源一、對偶問題的提出第2頁，課件共23頁，創(chuàng)作于2023年2月下面從另一個角度來討論這個問題：假定：該廠的決策者不是考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工任務(wù)，只收取加工費。試問該決策者應(yīng)制定怎樣的收費標(biāo)準(zhǔn)（合理的）？第3頁，課件共23頁，創(chuàng)作于2023年2月分析：

1、每種資源收回的費用不能低于自己生產(chǎn)時的可獲利潤；

2、定價又不能太高，要使對方能夠接受。第4頁，課件共23頁，創(chuàng)作于2023年2月

工廠方希望W越大越好，接受方希望越小越好，故為最好。該問題的數(shù)學(xué)模型為：第5頁，課件共23頁，創(chuàng)作于2023年2月模型對比：尋找資源的最優(yōu)售價，以便了解若放棄生產(chǎn)、出售資源至少能獲得的收入尋找一套最優(yōu)生產(chǎn)方案，以謀求一個最大利潤；第6頁，課件共23頁，創(chuàng)作于2023年2月1、對稱型對偶問題max

z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤

b2(3)

……am1x1+am2x2+…+amnxn≤

bmxj

≥0（j=1,2,…,n）min

w=b1y1+b2y2+…+bmym

s.t.a11y1+

a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2(4)

……a1ny1+a2ny2+…+amnym≥

cnyi≥0（i=1,2,…,m）定義1設(shè)原

LP

問題為則稱下列LP

問題為其對偶問題，其中yi≥0（i=1,2,…,m）稱為對偶變量，并稱（3）、（4）為一對對稱型對偶問題二、線性規(guī)劃的對偶理論

（一）、對偶問題的形式

maxz=cx(P)s.t.Ax≤bx≥0

minw=yb(D)s.t.yA≥

cy≥0第7頁，課件共23頁，創(chuàng)作于2023年2月2、非對稱型對偶問題

maxz=cx(P)s.t.Ax=bx≥0引入對偶變量（u,v），其中

u=(u1,u2,…,um)為對應(yīng)于第一組不等式約束

Ax≤b的對偶變量，v=(v1,v2,…,vm)為對應(yīng)于第二組不等式約束

-Ax≤-b的對偶變量，按對稱型的結(jié)論：令

y=u-v

minw=yb(D)s.t.yA≥cy無符號限制

maxz=cxs.t.Ax≤b-Ax≤

-bx≥0

minw=(u-v)bs.t.(u-v)A≥

cu,v≥0第8頁，課件共23頁，創(chuàng)作于2023年2月第二章線性規(guī)劃的對偶理論3、混合型對偶問題

maxz=c1x1+c2x2s.t.A11x1+A12x2

≤

b1A21x1+A22x2=b2A31x1+A32x2

≥b3x1

≥0,x2無符號限制其中

Aij

為mi×nj

矩陣；bi為mi維列向量；cj為nj維行向量；xj為nj維列向量，i=1,2,3；j=1,2,且m1+m2+m3=m,n1+n2=n令

x2=x21-x22,x21,x22

≥0.化原問題為標(biāo)準(zhǔn)型：按非對稱型maxz=c1x1+c2(x21-x22)s.t.A11x1+A12(x21-x22)+Isxs=

b1A21x1+A22(x21-x22)

=b2A31x1+A32(x21-x22)-Itxt=b3x1,x21,x22,xs,xt≥0minw=b1y1+b2y2+b3y3s.t.y1A11+y2A21+y3A31

≥c1y1A12+y2A22+y3A32

≥c2-y1A12-y2A22-y3A32

≥-c2

y1Is

≥0-y3It

≥0

y1,y2,y3無符號限制第9頁，課件共23頁，創(chuàng)作于2023年2月例原問題

minw=b1y1+b2y2+b3y3（D）s.t.y1A11+y2A21+y3A31

≥c1y1A12+y2A22+y3A32

=c2y1≥0,y2

無符號限制,y3

≤0

第10頁，課件共23頁，創(chuàng)作于2023年2月對偶問題

注意：以后不強調(diào)等式右段項b≥0，原因在對偶單純型表中只保證而不保證，故b可以是負(fù)數(shù)。第11頁，課件共23頁，創(chuàng)作于2023年2月綜上所述，其變換形式歸納如下：原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項第12頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)討論對稱形式：（P）問題maxz=cxs.t.Ax≤bx≥0（D）問題minw=ybs.t.yA≥cy≥0一、對偶規(guī)劃的若干定理Theorem1

(對稱性定理)對偶問題的對偶是原問題.proofTheorem2

(弱對偶定理)設(shè)x0

和y0

分別是（P）問題和（D）問題的可行解，則必有cx0

≤y0b.Corollary1(解的最優(yōu)性)如果x*

和y*分別是（P）問題和（D）問題的可行解，且cx*

=y*b，則x*

和y*分別是（P）問題和（D）問題的最優(yōu)解。（貌似）亦稱松緊定理proof向前第13頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)Theorem1

(對稱性定理)proof

:先將(D)問題化成原問題形式（D）問題minw=ybs.t.yA≥cy≥0設(shè)

xT為它的對偶變量,寫出它的對偶問題即這就是(P)問題.證畢第14頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)Theorem2

(弱對偶定理)proof:因為x0是(P)問題的可行解,故必有Ax0

≤b,

x0≥0(1)又y0是問題(D)的可行解,于是有y0A≥c,y0

≥0

(2)

用y0左乘不等式

(1)兩邊,得y0Ax0

≤y0b

用x0左乘不等式

(2)兩邊,得y0Ax0

≥

cx0

從而有cx0

≤y0b

證畢cx0≤y0b第15頁，課件共23頁，創(chuàng)作于2023年2月

Corollary2.

若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解；反之不成立。這也是對偶問題的無界性。關(guān)于無界性有如下結(jié)論：問題無界無可行解無可行解問題無界對偶問題原問題無界如：（原）無可行解（對）第16頁，課件共23頁，創(chuàng)作于2023年2月第二章線性規(guī)劃的對偶理論Corollary3如果一對對偶問題都有可行解，則它們都有最優(yōu)解。Theorem3

(對偶定理)如果（P）問題（（D）問題）有最優(yōu)解，那么（D）問題（（P）問題）也有最優(yōu)解，且目標(biāo)函數(shù)值相等。proofCorollary4(單純形乘子定理)如果（P）問題有最優(yōu)解，最優(yōu)基為B，則y*=cBB-1就是（D）問題的一個最優(yōu)解。向前第17頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)Theorem3

(對偶定理)proof:設(shè)x*是（P）問題的最優(yōu)解，它對應(yīng)的基矩陣為B，引入松弛變量xs=(xn+1，xn+2，…,xn+m)T將（P）問題化為標(biāo)準(zhǔn)形式.顯然，該問題也有最優(yōu)解由最優(yōu)性判別定理知令則有第18頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)即這表明是（D）問題的可行解對應(yīng)的目標(biāo)函數(shù)值為：又因為

x*是（P）問題的最優(yōu)解，其目標(biāo)函數(shù)值為：所以有則由

Corollary1知（D）問題有最優(yōu)解，且兩者的目標(biāo)函數(shù)的最優(yōu)值相等。同理可證，當(dāng)（D）問題有最優(yōu)解時，（P）問題也有最優(yōu)解，且目標(biāo)函數(shù)相等。證畢第19頁，課件共23頁，創(chuàng)作于2023年2月§2對偶問題的基本性質(zhì)Corollary5對于對稱形式（P）問題，如果有最優(yōu)解，則在其最優(yōu)單純形表中，松弛變量xn+1,xn+2,…,xn+m的檢驗數(shù)（）的負(fù)值即為（D）問題的一個最優(yōu)解。cBsxBsc0xs檢驗數(shù)cBcN0xBxNxsBNIcBcN0bb0cBcBxBxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB