线性规划的对偶理论运筹学学习教案

《线性规划的对偶理论运筹学学习教案》由会员分享，可在线阅读，更多相关《线性规划的对偶理论运筹学学习教案（35页珍藏版）》请在装配图网上搜索。

1、线性规划的对偶线性规划的对偶(du u)理论运筹学理论运筹学第一页，共35页。第1页/共35页第二页，共35页。1、对称(duchn)型对偶问题：nnxcxcxczP2211max: )(mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxxmmybybybSD2211min)(nmmnnnmmmmcyayayacyayayacyayayat s22112222211211221111.0,21myyyCXz max0,.XbAXts，nxxxX21ncccC21,212222111211mnmmnnaaaaaaaaaA若

2、取mbbbb21myyyY21YbS min0,.YCYAts第2页/共35页第三页，共35页。nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx2、标准型的对偶(du u)问题：mmybybybS2211minnmmnnnmmmmcyayayacyayayacyayayats22112222211211221111.无符号限制myyy,21CXz max0,.XbAXtsYbS min无符号限制YCYAts,.则对偶(du u)问题（D）为：第3页/共35页第四页，共35页。 原问题

3、对偶问题目标(mbio)函数max目标(mbio)函数min目标函数(hnsh)系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵AA系数矩阵3、混合型对偶问题第4页/共35页第五页，共35页。第5页/共35页第六页，共35页。最优单纯形表：对偶问题剩余变量 对偶问题 的变量最优单纯形表：原问题的松弛变量原问题的变量0, 5 2426 155 2max212121221xxxxxxxs.t.xxz原问题：0, 5 2426 155 2max543543,212121221xxxxxxxx

4、xxxxxs.t.xxz标准型：常数(chngsh)项213xxx0 1 0 -1/4 3/2 3/21 0 0 1/4 -1/2 7/2 0 0 1 5/4 -15/2 15/20 0 0 -1/4 -1/2 Z-17/20,y 125 26.32132132yyyyyyyts32152415minyyyw对偶问题：32152415maxyyyw标准型：0,y 125 26.543215321432yyyyyyyyyyyt s217wy1y2y3y4y5常数项-15/200-7/2-3/2y2-5/4 10-1/41/41/4y315/2011/2-3/21/2最优值Z*=17/2最优值W*

5、=17/2最优解（7/2，3/2）最优解（0，1/4，1/2）第6页/共35页第七页，共35页。定理2.1 对偶(du u)问题的对偶(du u)就是原问题。（即互为对偶(du u)规划）一、对称一、对称(duchn)(duchn)定理：定理： 设原问题（设原问题（P P） 对偶问题（对偶问题（D D）0. .maxXbAXtsCXz0. .minYCYAtsYbw第7页/共35页第八页，共35页。bYCXDYPX00002 . 2）的一个可行解，则有对偶问题（是其）的一个可行解，是原问题（若定理为对称型证明：设原问题)(P0,.XbAXtsYbSDmin）为则其对偶问题（0,.YCYAtsC

6、Xz max0,00XbAX有000XCAY，由,000bYAXY000CXAXY,0000bYAXYCXbYCX00即）的一个可行解，是（PX0）的一个可行解，是（DY00,00YCAY，有0,00YbAX由二、弱对偶性定理二、弱对偶性定理(dngl)：第8页/共35页第九页，共35页。bYCXDYPX00002 . 2）的一个可行解，则有对偶问题（是其）的一个可行解，是原问题（若定理推论(tuln)2、若原问题（P）和其对偶问题 （D）都存在可 行解，则（P） 和（D）都存在最优解推论1： 若（P）有可行(kxng)解，但无上界，则（D）无 可行(kxng)解。若（D）有可行(kxng)解

7、，但无下界，则 （P）无可行(kxng)解0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题第9页/共35页第十页，共35页。三、对偶性定理三、对偶性定理(dngl)：第10页/共35页第十一页，共35页。证明：，）有最优解必要性：若（0XPABCCB1,1CABCB即10BCYB取,0CAY则有）的一个可行解是（即DBCYB10由定理(dngl)2.2的推论2知：（D）有最优解充分性：由定理2.1知，（P）与（D）互为对偶(du u)， 充分性同理证明, 01NBCCBN有),(),(1NBBCCCBNB),(),(1NBCCCCBBNB), 0(1

8、NBCCBN, 0（1）（P）有最优解的充要条件是（D）有最优解B为最优基0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(第11页/共35页第十二页，共35页。（2）若X*和Y*分别(fnbi)是（P）和（D）的可行解，则X*和 Y*分别(fnbi)是（P）和（D）的最优解的充要条件是 CX*=Y*b证明(zhngmng)：必要性，设X*和Y*分别(fnbi)是（P）和（D）的最优解，由定理2.2,必有CX*Y*b设（P）的最优解X* 对应的最优基为B10BCYB取）的一个可行解是（则DY0,bYbY*0于是有0,1*bBCCCXNB且

9、bBCB1bY0bY*所以 CX*=Y*b0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(第12页/共35页第十三页，共35页。充分性，设X*和Y*分别(fnbi)是（P）和（D）的可行解， 且CX*=Y*b证：设X是（P）的任一可行(kxng)解，由定理2.2，必有CX Y*b=CX*所以(suy)X* 是（P）的最优解同理可证Y*（D）的最优解0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(要证X*和Y*分别是（P）和（D）的最优解第13页/共35页第十四页，共35页。定理2

10、.3 原问题(wnt)（P）与其对偶问题(wnt) （D）存在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b推论推论(tuln)(tuln)：1 1、若（、若（P P）有可行解而）有可行解而(D)(D)无可行解，则无可行解，则(P)(P)无界。无界。 若（若（D D）有可行解而）有可行解而(P)(P)无可行解，则无可行解，则(D)(D)无界。无界。3：若（P）存在(cnzi)最优解X*，则（D）一定存在(cnzi) 最优解Y*，且1*BCYB2、原问题（P）与其对偶

11、问题（D）最优值相同只需求出（P）或(D)中一个的最优解和最优值，即可得另一个的最优解和最优值0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(第14页/共35页第十五页，共35页。0,1226.215max543215321432131xxxxxxxxxxxxxt sxxz已知线性规划问题例0 1/2 1 1/4 1/4 1/4 1 2 0 1/2 -3/2 1/213xx0 1/2 0 -11/4 9/4 Z+31/4X1X2X3X4X5常数项的最优单纯形表为：求其对偶(du u)问题的最优解和最优值解：对偶(du u)问题的最优值W

12、*=-31/4最优解31PPB 21611*BCYB*11BBB116221541解所以，对偶问题的最优1*BCYB9114149411116241第15页/共35页第十六页，共35页。推论3*：若（P） （D）为对称型对偶问题，且（P） 存在最优解X*，则（D）一定存在最优解Y*， 且（-1）Y*是（P）的标准型的最优单纯形表 检验行中松弛(sn ch)变量的系数)(P证明：对原问题0,.XbAXtsCXz max:)()(,PPXS化为标准型把引进松弛变量0,.SSXXbXAXtsSXCXz0maxSXXX取OCC, EAA, 0,.XbXAtsXCz max:)(P标准型第16页/共35

13、页第十七页，共35页。SXXX其中OCC,ENB,，0,.XbXAtsXCz max:)(P对标准型设最优基为B,OCCCNB，,SNBXXXX，XCz OCCNB，,XA由SNBXXXSNBXNXBXbENBA,，则 SNBXNXbBXSNBXBNXBbBX111SNBXXXNNBBXCXCNNSNBXCXBNXBbBC111SBNBNBXBCXNBCCbBC111)(EAA, ) 1)()( （数纯形表中松弛变量的系的最优单的对偶问题的最优解为结论：PPbBCZXBCXNBCCXBSBNBNB111)(0第17页/共35页第十八页，共35页。0,8234.52max:21212121xxx

14、xxxtsxxZP）为设（例问题的最优解和最优值利用对偶定理求其对偶0,8234.52max,5421521423121543xxxxxxxxxxxtsxxZPxxx，）化为标准型把（，引进松弛变量X1 X2 X3 X4 X5 Z 2 5 0 0 0 Z-0 X4 1 0 1 0 0 4X5 0 1 0 1 0 3 X6 1 2 0 0 1 8X1 X2 X3 X4 X5 Z 2 0 0 -5 0 Z-15 X4 1 0 1 0 0 4X2 0 1 0 1 0 3 X6 1 0 0 -2 1 2X1 X2 X3 X4 X5 Z 0 0 0 -1 -2 Z-19 X4 0 0 1 2 0 2X2

15、 0 1 0 1 0 3 X1 1 0 0 -2 1 20 , 2 , 0 , 3 , 2)(XP 的最优解最优值Z=19松弛(sn ch)变量X3 X4 X5 的检验数为0，-1，-2（D）的最优解Y0 =（0，1，2） 最优值S0 =19 第18页/共35页第十九页，共35页。bYCXDYPX00002 . 2）的一个可行解，则有对偶问题（是其）的一个可行解，是原问题（若定理推论2、若原问题(wnt)（P）和其对偶问题(wnt) （D）都存在可 行解，则（P） 和（D）都存在最优解推论(tuln)1： 若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无

16、可行解第19页/共35页第二十页，共35页。定理2.3 原问题（P）与其对偶问题（D）存在以 下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别(fnbi)是（P）和（D）的可行解，则X*和Y*分别(fnbi)是（P）和（D）的最优解的充要条件是 CX*=Y*b推论推论(tuln)(tuln)：1 1、若（、若（P P）有可行解而）有可行解而(D)(D)无可行解，则无可行解，则(P)(P)无界。无界。 若（若（D D）有可行解而）有可行解而(P)(P)无可行解，则无可行解，则(D)(D)无界。无界。3：若（P）存在(cnzi)最优解X*，则（D）一定存在(cnzi

17、) 最优解Y*，且1*BCYB2、原问题（P）与其对偶问题（D）最优值相同第20页/共35页第二十一页，共35页。 对偶问题原问题有最优解 无界无可行解有最优解无界无可行解一定(ydng)不可能(knng)不可能不可能不可能可能不可能可能可能1minxZP）为设（无符号限制212121,11.xxxxxxts21maxyySD）为（1.21yyt s021 yy0, 021yy（P）无可行解（D）无可行解0,21xx无界（P）无可行解（D）有可行解第21页/共35页第二十二页，共35页。四、互补四、互补(h b)松弛定理：松弛定理：定理(dngl)2.4 设X*和Y*分别是（P）和（D）的可行

18、解， 则X*和Y*分别是（P）和（D）的最优解的 充要条件是方程组 成立0*)*(0*)(*XCAYAXbY证明(zhngmng):充分性0*)*(0*)(*XCAYAXbY已知X*和Y*分别是（P）和（D）的可行解，且0*)(*AXbY由0*AXYbYbYAXY*0*)*(XCAY由0*CXAXY*CXAXY*CXbY即所以X*和Y*分别是（P）和（D）的最优解第22页/共35页第二十三页，共35页。必要性：已知X*和Y*分别(fnbi)是（P）和（D）的最优解0*)*(0*)(*XCAYAXbY要证：, 0,21mnnnSxxxXP）中引进松弛变量在（, 0,21nmmmSyyyYD）中引

19、进剩余变量在（0.max)(SSXXbXAXtsCXzPP，为）的标准型（0*SSYYCYAY，所以0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题）的最优解为（），（）的最优解，知是（由PXXPXS*）的最优解）为（，（）的最优解，知是（由DYYDYS*0*SSXXbXAX，所以*)*(SXAXb*SXYAXY*YY*)*(SYAYC0.min)(SSYYCYYAtsYbSDD，）为的标准型（*XYAXYS*XX第23页/共35页第二十四页，共35页。因为(yn wi)X*和Y*分别是（P）和（D）的最优解*CXbY有*SXYAXY*XYAXYS*

20、SXY0*XYS）的最优解为（），因为（PXXS*）的最优解）为（，因为（DYYS*0*SXY0*,XYS0*SSYYCYAY，有0*,*SSXXbXAX，有*SYCAY*SXAXb0*)*(XCAY*)*(*SXAXY*SXYAXYbY *于是*)*(*XYAXYXYAYCXSS0.max)(SSXXbXAXtsCXzPP，为）的标准型（0.min)(SSYYCYYAtsYbSDD，）为的标准型（0) *(*AXbY第24页/共35页第二十五页，共35页。定理2.4 设X*和Y*分别(fnbi)是（P）和（D）的可行解，则X*和Y*分别(fnbi)是（P）和（D）的最优解的充要条件是方程组

21、成立 0*)*(0*)(*XCAYAXbY互补松弛互补松弛(sn ch)定理定理:第25页/共35页第二十六页，共35页。的含义：0*)*(0*)(*XCAYAXbY，*21nxxxXncccC21mnmmnnaaaaaaaaaA212222111211mbbbb21*21myyyYm21*)(*AXbY*21myyymbbb21m21*X*21myyymbbb21*21XXXm*21myyy*12211XbmXbXbm*)( *222111XbyXbyXbymmm0第26页/共35页第二十七页，共35页。的含义：0*)*(0*)(*XCAYAXbY*)(*222111XbyXbyXbymmm

22、0*)(*AXbY0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题bAX*由0*, AXb即0*12211XbmXbXbm即0*Xbii0*,iy又miXbyiii, 2 , 1, 0*0*)*(XCAY同理：由njxcPYjjj, 2 , 1, 0*miXbyiii, 2 , 1, 0*njxcPYjjj, 2 , 1, 0*0*)*(0*)(*XCAYAXbY即：mnmmnnaaaaaaaaaA212222111211nPPP21第27页/共35页第二十八页，共35页。互补松弛(sn ch)定理： 设X*和Y*分别是（P）和（D）的可行解，则X*

23、和Y*分别是（P）和（D）的最优解的充要条件是方程组 成立 miXbyiii, 2 , 1, 0*njxcPYjjj, 2 , 1, 0*)*(处）的最优解及（处）的最优解即在（*,*,*,*,*,*,*2121mnyyyYDxxxXP jjjcPYx*, 0*3必有则若有某个 0*,*4jjjxcPY则必有若有某个 iiibXy*, 0*1则必有若有某个 0*,*2iiiybX则必有若有某个把X*代入（P）的第i个方程(fngchng)时为等式松约束(yush)紧约束mnmmnnaaaaaaaaaA212222111211nPPP21m21第28页/共35页第二十九页，共35页。定理2.4

24、设X*和Y*分别(fnbi)是（P）和（D）的可行解，则X*和Y*分别(fnbi)是（P）和（D）的最优解的充要条件是方程组 成立 对任一种形式的对偶问题(wnt)成立互补松弛互补松弛(sn ch)定理定理:miXbyiii, 2 , 1, 0*njxcPYjjj, 2 , 1, 0*)*(第29页/共35页第三十页，共35页。优解和最优值偶理论求对偶问题的最，试用对最优值，的最优解12*400*ZX无符号限制321321321321, 0, 041632532.xxxxxxxxxxxxts32134maxxxxZ例：已知原问题32142minyyyW解：对偶问题为无符号限制321321321

25、321, 0, 036543132.yyyyyyyyyyyyts约束方程，得：）的代入（，将PX400*441242200*0*21yy得由, 04*3x3*6*5321yyy3*3 y12*300*WY最优值），（最优解所以：对偶问题的第30页/共35页第三十一页，共35页。0,32235.54321543215432xxxxxxxxxxxxxxts5432195243minxxxxxZ例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最2132maxyyW解：对偶问题为0,92355243.21212121212yyyyyyyyyyyts01y2y.92321yy32y221 y

26、y5521yy421 yy63221 yy10*31*WY最优值），（最优解第31页/共35页第三十二页，共35页。0,32235.54321543215432xxxxxxxxxxxxxxts5432195243minxxxxxZ例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最 约束方程，得：）的代入（将DY3 , 1*99522244330*0*43xx3*2*2*3*5*543215432xxxxxxxxx2132maxyyW解：对偶问题为0,92355243.21212121212yyyyyyyyyyyts10*31*WY最优值），（最优解得由, 03*, 01*21yy3

27、*2*2*3*52152xxxxx即2*1*0*215xxx，得令），（得最优解00021*1X0*35*32*215xxx，得令），（得最优解3200035*2X10*10*1*21ZXXX最优值，）（原问题的最优解第32页/共35页第三十三页，共35页。课堂练习：问题的最优解和最优值试用对偶理论求对偶，的最优解0,2, 1 , 1*X)4 , 3 , 2 , 1(0226332.31434321421ixxxxxxxxxxxxtsi43216368minxxxxZ已知原问题43212263maxyyyyW解：对偶问题为0,636283.432132143221421yyyyyyyyyyyy

28、yyyts23226633由0*4 y得由, 02*, 01*, 01*321xxx3*6*28*3*43221421yyyyyyyy20*0, 1 ,2,2*WY最优值），（最优解对偶问题的第33页/共35页第三十四页，共35页。0.maxXbAXtsCXz对问题mPPPB21取可行基NBNBXNBCCbBCZ)(max11NBNXBbBX110, 0NBXX0NX令bBXB1得011bBX得基本可行解011NBCN、若所有的检验数为最优解则1,X单纯形法：解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数, 0, 021NBCCBN域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数, 0, 031NBCCBN第34页/共35页第三十五页，共35页。