3.9線性規(guī)劃的對偶問題,第三章線性規(guī)劃,1對偶問題的提出,4對偶單純形法,2對偶規(guī)劃的形式,3.8修正單純形法,3對偶定理,MaxZ=CXs.t.AX=bX0,j=CBTB-1pj-cj,3.8修正單純形法,（1）檢驗(yàn)數(shù)：（2）基變量值：（3）主列元素：,定理3.8.1設(shè)在單純形法某次迭代中的可行基為B，作了r,s旋轉(zhuǎn)基變換后，則下一個新基的逆為,其中,改進(jìn)單純形法的計(jì)算步驟,（1）求單純形乘子：,（2）計(jì)算：若則停，得最優(yōu)解否則轉(zhuǎn)（3）,j=CBTB-1pj-cj,（3）計(jì)算向量：若所有，則停，無最優(yōu)解；否則轉(zhuǎn)（4）,（4）計(jì)算：,（5）形成變換矩陣：,Ers,（6）計(jì)算：以代，以代，轉(zhuǎn)（1）,例MaxZ=x12x2-x3S.t.x1x2+x34-x1+2x2-2x362x1+x25x1,x2,x30,解MaxZ=x12x2-x3S.t.x1x2+x3+x44-x1+2x2-2x3+x562x1+x2+x65x1,x2,x3x4,x5,x60,111100-12-2010210001,（1）,（2）,S=2,（3）,第一次迭代,（4）,（5）,（6）,令,轉(zhuǎn)(1),第二次迭代,（1）,（2）,S=1,轉(zhuǎn)(3),（3）計(jì)算,（4）,（5）,（6）,令,轉(zhuǎn)(1),第三次迭代,（1）,（2）,例:某工廠要安排生產(chǎn)甲、乙兩種產(chǎn)品.生產(chǎn)單位產(chǎn)品所需設(shè)備臺時(shí)及A,B兩種原材料的消耗量，每件產(chǎn)品可以獲得的利潤以及設(shè)備可利用的時(shí)數(shù),可用的原材料如下表所示：,1、對偶問題的提出：,3.9線性規(guī)劃的對偶問題,若有一公司有一訂單要生產(chǎn)甲、乙兩種產(chǎn)品,需要向工廠租用設(shè)備.公司決策者就要考慮給每種設(shè)備如何定價(jià),才最有競爭力？,Maxz=2x1+3x2s.t.x1+2x284x1164x212x1,x20,A(4,2),Minf=8y1+16y2+12y3,設(shè)y1，y2，y3分別為出租單位設(shè)備臺時(shí)和出讓原材料A、B的費(fèi)用。,Maxz=2x1+3x2s.t.x1+2x284x1164x212原問題x1,x20,s.t.y1+4y22（不少于甲產(chǎn)品的利潤）,2y1+4y33（不少于乙產(chǎn)品的利潤）,y1,y2,y30對偶問題,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,2、對偶規(guī)劃的形式(1)對稱形式的對偶關(guān)系(規(guī)范型的線性規(guī)劃),Minf=b1y1+b2y2+bnyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcny1，y2，ym0,一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系。原問題記為LP,對偶問題記為DP,LP問題為目標(biāo)最大化，DP問題為最小化;,LP問題的約束為“”,DP問題的約束為“”;,LP的價(jià)值系數(shù)ci,在DP問題中恰好為約束右端項(xiàng);,LP的約束右端項(xiàng)bi,在DP問題中恰好為價(jià)值系數(shù);,LP中的每個約束條件對應(yīng)著DP問題中的一個變量,而LP中的每個決策變量對應(yīng)著DP問題中的一個約束;,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,Minf=b1y1+b2y2+bnyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcny1，y2，ym0,1)2)3)4)5),(LP)Maxz=CTXs.t.AXbX0,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,Maxf=b1y1+b2y2+bmyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcmy1，y2，ym0,LP與DP的矩陣的形式,(DP)Minf=bTys.t.ATyCy0,(2)非對稱形式的對偶關(guān)系,Maxz=2x1+4x2s.t.x1+x2=1-3x1+2x23x1,x20,Maxz=2x1+4x2s.t.x1+x21-x1-x21-3x1+2x23,Miny1-y2+3y3s.t.y1-y2-3y32y1-y2+2y34y1,y2,y3,0,令y1-y2=y4,Miny4+3y3s.t.y4-3y32y4+2y34y30,若LP問題的某個約束條件為等式約束，則在對偶DP問題中與此約束對應(yīng)著一個變量且那個變量取值無非負(fù)限制；,Miny1+3y2s.t.y1-3y22y1+2y24y20,Maxz=2x1+4x2s.t.x1+x2=1-3x1+2x23x1,x20,Maxz=2x1+3x2s.t.x1+x21-3x1+2x23x10,令x/2x/2=x2,Maxz=2x1+3x/23x/2s.t.x1+x/2x/21-3x1+2x/22x/23x1,x/2,x/20,Miny1+3y2s.t.y1-3y22y1+2y23-y1-2y2-3y1y20,Miny1+3y2s.t.y1-3y22y1+2y2=3y1y20,若LP問題的某個變量的值沒有非負(fù)限制，則在對偶DP問題中與此變量對應(yīng)的那個約束為等式。,（1）將模型統(tǒng)一為“max，”或“min，”的形式對于其中的等式約束按下面(2)、(3)中的方法處理；,對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系直接給出其對偶規(guī)劃:,（2）若LP問題的某個約束條件為等式約束，則在對偶DP問題中與此約束對應(yīng)著一個變量且那個變量取值無非負(fù)限制；（3）若LP問題的某個變量的值沒有非負(fù)限制，則在對偶DP問題中與此變量對應(yīng)的那個約束為等式。,例寫出下面線性規(guī)劃的對偶規(guī)劃模型,解先將約束條件變形為“”形式，再根據(jù)非對稱形式的對應(yīng)關(guān)系，寫出對偶規(guī)劃,1.對稱性2.弱對偶性3.最優(yōu)性準(zhǔn)則定理,定理3.對偶問題的對偶是原問題.,定理3.9.1若X,Y分別為（LP)和（DP）的任意可行解，那么CTXbTY.,3對偶定理,證:AXb,XTATYbTY;ATYC,XTATYXTC,那么CTXbTY.,推論3.9.2若(LP)和(DP)同時(shí)有可行解那么(LP)和(DP)均有最優(yōu)解.,4.最優(yōu)解存在的一個充分條件5.無界性,推論3.9.1若X(0),Y(0)分別為（LP)和(DP)的可行解，且CTX(0)=bTY(0).那么X(0),Y(0)分別為(LP)和(DP)的最優(yōu)解.,證:CTXbTY(0)=CTX(0);bTY(0)=CTX(0)bTY.,定理3.若原問題的目標(biāo)無界,則其對偶問題必?zé)o可行解.,證:若對偶問題有可行解Y(0),則CTXbTY(0)與原問題的目標(biāo)無界矛盾.,6.強(qiáng)對偶性7.原問題與對偶問題的解之間只有以下三種可能的關(guān)系,定理3.9.2若(LP)和(DP)中有一個有最優(yōu)解,則另一個問題也必存在最優(yōu)解,且兩個問題的最優(yōu)解的目標(biāo)函數(shù)值必相等.,(1)兩個問題都有可行解,從而都有最優(yōu)解;(2)一個問題有可行解而目標(biāo)為無界,另一個問題必?zé)o可行解;(3)兩個問題都無可行解.,Maxz=CTXs.t.AXbX0,證,Maxz=CTX+CTXs.t.AX+IX=bX0,X0,最優(yōu)解X*=X*0,X*T,X*B=B-1b.X*0為原問題變量,j0,即j=CBTB-1Pj-cj0.j=1,2,n+1,n+m,CBTB-1(p1,p2,pnpn+1,pn+m)-(c1,c2,cncn+1,cn+m)0,原問題變量檢驗(yàn)數(shù)CBTB-1(p1,p2,pn)-(c1,c2,cn)0(1),松弛變量的檢驗(yàn)數(shù)CBTB-1(pn+1,pn+m)-(cn+1,cn+m)0(2),由(1)CBTB-1A-CT0,得CBTB-1ACT,記Y*=(CBTB-1)T,則ATY*C即Y*滿足對偶問題的約束,又由(2)知CBTB-1I-(0,0,0)0(3)得CBTB-10,即Y*0,Y*滿足對偶問題的非負(fù)條件.,Minf=bTYs.t.ATYCY0,故Y*=(CBTB-1)T為對偶問題的可行解.且有,bTY*=(Y*Tb)T=(CBTB-1b)T=X*BTCB=CBTXB*(4)下證兩個問題的目標(biāo)最優(yōu)值相等,從而Y*為最優(yōu)解:,將原問題最優(yōu)值Z*按基變量X*B與非基變量X*N表示:將原問題最優(yōu)值Z*按最優(yōu)解X*=X0*,X*T表示:,對偶問題目標(biāo)函數(shù)在可行解Y*=(CBB-1)T的目標(biāo)值為f*=bTY*,再由(4)(5)有:,Z*=CX*0=Y*b=f*,X*0,Y*分別為原問題與對偶問題的可行解且目標(biāo)值相等,由推論3.9.2,X*0,Y*必為各自問題的最優(yōu)解.,Z*=CBTX*B+CNTX*N=CBTX*B,Z*=CTX*0+CTX*=CTX*0,故CBTX*B=CTX*0(5),由上述證明過程可以得出:,推論1若線性規(guī)劃原問題有最優(yōu)解,最優(yōu)基為B,則Y*=(CBTB-1)T就是其對偶問題的一個最優(yōu)解.,推論2對于對稱形式的線性規(guī)劃原問題,若有最優(yōu)解,則在其最優(yōu)單純形表中,松弛變量的檢驗(yàn)數(shù)就是對偶問題的一個最優(yōu)解.,若X*,W*分別為（LP）和（DP）的最優(yōu)解，那么，CX*=W*b。根據(jù)f=W*b=b1w1*+b2w2*+bmwm*可知f/bi=wi*wi*表示bi變化1個單位對目標(biāo)f產(chǎn)生的影響（在不改變原最優(yōu)基情況下），即若原問題的某個約束的右端項(xiàng)bi每增加一個單位而引起的最優(yōu)目標(biāo)函數(shù)值的增加量就等于該約束條件相對應(yīng)的對偶變量的最優(yōu)解。稱wi*為bi的影子價(jià)格。注意：B是最優(yōu)基，影子價(jià)格它表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。,對偶解的經(jīng)濟(jì)解釋,Maxz=2x1+3x2s.t.x1+2x284x1164x212x1,x20 x1*=4,x2*=2z*=14,Minf=8w1+16w2+12w3s.t.w1+4w222w1+4w33w1,w2,w30,由互補(bǔ)定理,將x1*,x2*代入第三個約束，為嚴(yán)格不等號，故w*3=0；又x1*,x2*嚴(yán)格大于零故對應(yīng)的對偶約束為等號w*1+4w*2=2,2w*1+4w*3=3解得w*1=1.5,w*2=0.125,w*3=0,B(4,2.5),z=15.5,比原目標(biāo)增1.5,C(4.25,2.875),z=14.125,比原目標(biāo)增0.125,一、對偶單純形法的基本思想(1)基本思想,4.對偶單純形法,從原問題的一個基本解(不一定是可行解)出發(fā),它對應(yīng)著一個對偶可行解（檢驗(yàn)數(shù)非負(fù)），也可以說是從一個對偶可行解出發(fā)；然后檢驗(yàn)原問題的基本解是否可行，即是否有負(fù)的分量，如果有負(fù)的分量，則求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗(yàn)數(shù)非負(fù)）。如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性，使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。,(2)離基變量與進(jìn)基變量的選擇,選取負(fù)值的基變量出基:br=minbi0,xr為出基變量,1)若第r行所有元素arj0則原問題無可行解.xr=br(ar1x1+arjxj+),jJN,2)若第r行有ark0,有利于向可行解轉(zhuǎn)化,但還需考慮保證對偶解的可行性,即新檢驗(yàn)數(shù)j/0,于是取k/ark=maxj/arj|arj0,jJN則j/=j(arj/ark)k=j(k/ark)arjj(j/arj)arj=0此時(shí)xr為出基變量.,1)建立初始對偶單純形表,對應(yīng)一個基本解,所有檢驗(yàn)數(shù)均非負(fù),轉(zhuǎn)2；,二、對偶單純形法求解線性規(guī)劃問題步驟,2)若b0,則得到最優(yōu)解,停止;否則,若有bk0,由br=minbk0,基變量xr為出基變量,Ar為主行.轉(zhuǎn)3,3)若所有arj0(j=1,2,n)，則原問題無可行解,停止;否則,若有arj0，則選=maxj/arjarj0=k/ark那么xk為進(jìn)基變量,Pk為主列,轉(zhuǎn)4；,4)以ark為主元,作矩陣行變換使其變?yōu)?,該列其它元變?yōu)?,轉(zhuǎn)2.,對偶單純形法優(yōu)缺點(diǎn)：,優(yōu)點(diǎn):1)原問題的初始解可以是非可行解.當(dāng)檢驗(yàn)數(shù)都是非負(fù)時(shí),就可以進(jìn)行基變換,不需要加入