資源描述：
《對(duì)偶問(wèn)題.ppt.convertor》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第2章線性規(guī)劃的對(duì)偶理論Duality對(duì)偶DualProblem對(duì)偶問(wèn)題DualLinearProgramming對(duì)偶線性規(guī)劃DualTheory對(duì)偶理論2.1問(wèn)題的提出例：某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，該兩種產(chǎn)品均需要A、B、C、D四種不同的材料，按工藝資料規(guī)定，生產(chǎn)一單位甲乙產(chǎn)品需要各種材料數(shù)量及單位產(chǎn)品利潤(rùn)如表中所示。問(wèn):如何安排產(chǎn)品的生產(chǎn)計(jì)劃,才能使企業(yè)獲利最大?1.最大生產(chǎn)利潤(rùn)模型設(shè)企業(yè)生產(chǎn)甲產(chǎn)品為X1件，乙產(chǎn)品為X2件，則maxz=2X1+3X2s.t2X1+2X2￡12X1+2X2￡84X1￡164X2￡12X
2、130,X2302.資源最低售價(jià)模型(原問(wèn)題)<========>(對(duì)偶問(wèn)題)設(shè)第i種資源價(jià)格為yi,（i=1,2,3,4,）則有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y4322y1+2y2+0y3+4y433yi30,(i=1,2,3,4)y1y2y3y42.2原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系一般表示式：原問(wèn)題：maxz=c1X1+c2X2+┈+cnXns.t a11X1+a12X2+┈+a1nXn￡b1a21X1+a22X2+┈+a2nXn￡b2 ····················
3、···am1X1+am2X2+┈+amnXn￡bmxj30，j=1,2,┈,n對(duì)偶問(wèn)題：minw=b1y1+b2y2+┈+bmym s.t a11y1+a21y2+┈+am1ym3c1a12y1+a22y2+┈+am2ym3c2 ·························a1ny1+a2ny2+┈+amnym3cnyi30，(i=1,2,···,m)典式模型對(duì)應(yīng)對(duì)偶結(jié)構(gòu)矩陣表示（1）maxz=CXs.tAX￡bX30minw=Ybs.tYA3CY30對(duì)偶問(wèn)題原問(wèn)題對(duì)偶模型其他結(jié)構(gòu)關(guān)系（2）若模型為maxz=CX
4、s.tAX3bX30maxz=CXs.t-AX￡-bX30變形minw=Ybs.tYA3CY￡0Minw=Y′(-b)st.Y′(-A)3CY′30令Y=-Y′對(duì)偶問(wèn)題對(duì)偶變量Y￠（3）maxz=CXs.tAX￡bX￡0變形設(shè)X=-X′max=-CX′st.-AX′￡bX′30minw=Ybs.tYA￡CY30則有minw=Ybs.t-YA3-CY30對(duì)偶問(wèn)題典式：用矩陣形式表示：（1）maxz=CXminw=Ybs.tAX￡b<========>s.tYA3CX30Y30（2）maxz=CXminw=Ybs.tAX3b<=
5、=======>s.tYA3CX30Y￡0（3）maxz=CXminw=Ybs.tAX￡b<========>s.tYA￡CX￡0Y30原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”個(gè)變量是自由變量決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量約束條件數(shù)：n第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“=”例2-3
6、寫(xiě)出下面線性規(guī)劃的對(duì)偶問(wèn)題：課堂練習(xí)：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃：下面的答案哪一個(gè)是正確的？為什麼？（原問(wèn)題是極小化問(wèn)題，因此應(yīng)從原始對(duì)偶表的右邊往左邊查！）例題2minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5≥7x1+2x3-x4≤4-x1+3x2-x4+x5=-2x1，x2，x3≥0;x4≤0;x5無(wú)限制maxω=7y1+4y2-2y32y1+y2-y3≤3y1+3y3≤2-4y1+2y2≤-6y1-y2-y3≥03y1+y3=1y1≥0y2≤0y3無(wú)約束2.3對(duì)偶問(wèn)題的基本性質(zhì)Maxz=CXM
7、inw=Ybst.AX￡bst.YA3CX30Y30(1)弱對(duì)偶性：若X0——原問(wèn)題可行解，Y0——對(duì)偶問(wèn)題可行解則CX0￡Y0b證明：∵Y030，AX0￡b，∴Y0AX0￡Y0b，而Y0A3C，∴CX0￡Y0AX0，∴CX0￡Y0AX0￡Y0b（2）最優(yōu)性：若X0——原問(wèn)題可行解，Y0——對(duì)偶問(wèn)題可行解，且CX0=Y0b則X0——原問(wèn)題最優(yōu)解，Y0——對(duì)偶問(wèn)題最優(yōu)解證明：設(shè)X*——原問(wèn)題最優(yōu)解，Y*——對(duì)偶問(wèn)題最優(yōu)解則CX0￡CX*￡Y*b￡Y0b但CX0=Y0b，∴CX0=CX*=Y*b=Y0b∴X0=X*，Y0=Y*即
8、X0——原問(wèn)題最優(yōu)解，Y0——對(duì)偶問(wèn)題最優(yōu)解證畢。（3）無(wú)界性若原問(wèn)題最優(yōu)解無(wú)界，則對(duì)偶問(wèn)題無(wú)可行解證：有性質(zhì)1，CX0￡Y0b，當(dāng)CX0?∞時(shí)，則不可能存在Y0，使得CX0￡Y0b。注：逆定理不成立，即如果原問(wèn)題（對(duì)偶問(wèn)題）無(wú)可行解，那么對(duì)偶問(wèn)題（或原問(wèn)題）“解無(wú)界”不成立。（4）強(qiáng)對(duì)偶
