运筹学-线性规划的对偶理论.ppt

1、第2章 线性规划的 对偶理论及其应用 线性规划最重要的理论之一 进行经济分析的重要工具上堂课的主要内容：1、对称型对偶问题：nnxcxcxczP2211max:)(mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxxmmybybybSD2211min)(nmmnnnmmmmcyayayacyayayacyayayat s22112222211211221111.0,21myyyCXz max0,.XbAXts，nxxxX21ncccC21,212222111211mnmmnnaaaaaaaaaA若取mbbbb21myyy

2、Y21YbS min0,.YCYAtsnnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx2、标准型的对偶问题：mmybybybS2211minnmmnnnmmmmcyayayacyayayacyayayats22112222211211221111.无符号限制myyy,21CXz max0,.XbAXtsYbS min无符号限制YCYAts,.则对偶问题（D）为：原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束

3、方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵AA系数矩阵3、混合型对偶问题最优单纯形表：对偶问题剩余变量 对偶问题 的变量最优单纯形表：原问题的松弛变量原问题的变量0,5 2426 155 2max212121221xxxxxxxs.t.xxz原问题：0,5 2426 155 2max543543,212121221xxxxxxxxxxxxxs.t.xxz标准型：常数项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.3

4、2132132yyyyyyyts32152415minyyyw对偶问题：32152415maxyyyw标准型：0,y 125 26.543215321432yyyyyyyyyyyts217wy1y2y3y4y5常数项-15/200-7/2-3/2y2-5/4 10-1/41/41/4y315/2011/2-3/21/2最优值Z*=17/2最优值W*=17/2最优解（7/2，3/2）最优解（0，1/4，1/2）定理2.1 对偶问题的对偶就是原问题。（即互为对偶规划）一、对称定理：一、对称定理：设原问题（设原问题（P P）对偶问题（对偶问题（D D）0.maxXbAXtsCXz0.minYCYAt

5、sYbwbYCXDYPX00002.2）的一个可行解，则有对偶问题（是其）的一个可行解，是原问题（若定理为对称型证明：设原问题)(P0,.XbAXtsYbSDmin）为则其对偶问题（0,.YCYAtsCXz max0,00XbAX有000XCAY，由,000bYAXY000CXAXY,0000bYAXYCXbYCX00即）的一个可行解，是（PX0）的一个可行解，是（DY00,00YCAY，有0,00YbAX由二、弱对偶性定理：二、弱对偶性定理：bYCXDYPX00002.2）的一个可行解，则有对偶问题（是其）的一个可行解，是原问题（若定理推论2、若原问题（P）和其对偶问题（D）都存在可 行解，

6、则（P）和（D）都存在最优解推论1：若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无可行解0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题定理2.3 原线性规划（P）与其对偶规划（D）存 在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解 （2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充 要条件是：CX*=Y*b 三、对偶性定理：三、对偶性定理：证明：，）有最优解必要性：若（0XPABCCB1,1CABCB即10BCYB取,0CAY则有）的一个可行解是（即

7、DBCYB10由定理2.2的推论2知：（D）有最优解充分性：由定理2.1知，（P）与（D）互为对偶，充分性同理证明,01NBCCBN有),(),(1NBBCCCBNB),(),(1NBCCCCBBNB),0(1NBCCBN,0（1）（P）有最优解的充要条件是（D）有最优解B为最优基0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(（2）若X*和Y*分别是（P）和（D）的可行解，则X*和 Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b证明：必要性，设X*和Y*分别是（P）和（D）的最优解，由定理2.2,必有CX*Y*b设（P）

8、的最优解X*对应的最优基为B10BCYB取）的一个可行解是（则DY0,bYbY*0于是有0,1*bBCCCXNB且bBCB1bY0bY*所以 CX*=Y*b0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(充分性，设X*和Y*分别是（P）和（D）的可行解，且CX*=Y*b证：设X是（P）的任一可行解，由定理2.2，必有CX Y*b=CX*所以X*是（P）的最优解同理可证Y*（D）的最优解0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(要证X*和Y*分别是（P）和（D）的最优解定理2

9、.3 原问题（P）与其对偶问题 （D）存在以下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b推论推论：1 1、若（、若（P P）有可行解而）有可行解而(D)(D)无可行解，则无可行解，则(P)(P)无界。无界。若（若（D D）有可行解而）有可行解而(P)(P)无可行解，则无可行解，则(D)(D)无界。无界。3：若（P）存在最优解X*，则（D）一定存在 最优解Y*，且1*BCYB2、原问题（P）与其对偶问题（D）最优值相同只需求出（P）或(D)中一个的最优解和最优值，即可

10、得另一个的最优解和最优值0.maxXbAXtsCXzP）为标准型设原问题（无符号限制为则其对偶问题YCYAtsYbSD.min)(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常数项的最优单纯形表为：求其对偶问题的最优解和最优值解：对偶问题的最优值 W*=-31/4最优解31PPB 21611*BCYB*11BBB116221541解所以，对偶问题的最优1*BCYB9114149

11、411116241推论3*：若（P）（D）为对称型对偶问题，且（P）存在最优解X*，则（D）一定存在最优解Y*，且（-1）Y*是（P）的标准型的最优单纯形表 检验行中松弛变量的系数)(P证明：对原问题0,.XbAXtsCXz max:)()(,PPXS化为标准型把引进松弛变量0,.SSXXbXAXtsSXCXz0maxSXXX取OCC,EAA,0,.XbXAtsXCz max:)(P标准型SXXX其中OCC,ENB,，0,.XbXAtsXCz max:)(P对标准型设最优基为B,OCCCNB，,SNBXXXX，XCz OCCNB，,XA由SNBXXXSNBXNXBXbENBA,，则 SNBXN

12、XbBXSNBXBNXBbBX111SNBXXXNNBBXCXCNNSNBXCXBNXBbBC111SBNBNBXBCXNBCCbBC111)(EAA,)1)()(（数纯形表中松弛变量的系的最优单的对偶问题的最优解为结论：PPbBCZXBCXNBCCXBSBNBNB111)(00,8234.52max:21212121xxxxxxtsxxZP）为设（例问题的最优解和最优值利用对偶定理求其对偶0,8234.52max,5421521423121543xxxxxxxxxxxtsxxZPxxx，）化为标准型把（，引进松弛变量X1 X2 X3 X4 X5 Z 2 5 0 0 0 Z-0 X4 1 0

13、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 0 1 0 1 0 3 X1 1 0 0 -2 1 20,2,0,3,2)(XP 的最优解最优值Z=19松弛变量X3 X4 X5 的检验数为0，-1，-2（D）的最优解Y0 =（0，1，2）最优值S0 =19 bYCXDYPX00002.2）的一个可行解，则有对偶问题（是

14、其）的一个可行解，是原问题（若定理推论2、若原问题（P）和其对偶问题（D）都存在可 行解，则（P）和（D）都存在最优解推论1：若（P）有可行解，但无上界，则（D）无 可行解。若（D）有可行解，但无下界，则 （P）无可行解定理2.3 原问题（P）与其对偶问题（D）存在以 下对应关系：（1）（P）有最优解的充要条件是（D）有最优解（2）若X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是 CX*=Y*b推论：推论：1 1、若（、若（P P）有可行解而）有可行解而(D)(D)无可行解，则无可行解，则(P)(P)无界。无界。若（若（D D）有可行解而）有可行解

15、而(P)(P)无可行解，则无可行解，则(D)(D)无界。无界。3：若（P）存在最优解X*，则（D）一定存在 最优解Y*，且1*BCYB2、原问题（P）与其对偶问题（D）最优值相同原问题与对偶问题解的关系：对偶问题原问题有最优解 无界无可行解有最优解无界无可行解一定不可能不可能不可能不可能可能不可能可能可能1minxZP）为设（无符号限制212121,11.xxxxxxts21maxyySD）为（1.21yyt s021 yy0,021yy（P）无可行解（D）无可行解0,21xx无界（P）无可行解（D）有可行解四、互补松弛定理：四、互补松弛定理：定理2.4 设X*和Y*分别是（P）和（D）的可行

16、解，则X*和Y*分别是（P）和（D）的最优解的 充要条件是方程组 成立0*)*(0*)(*XCAYAXbY证明:充分性0*)*(0*)(*XCAYAXbY已知X*和Y*分别是（P）和（D）的可行解，且0*)(*AXbY由0*AXYbYbYAXY*0*)*(XCAY由0*CXAXY*CXAXY*CXbY即所以X*和Y*分别是（P）和（D）的最优解必要性：已知X*和Y*分别是（P）和（D）的最优解0*)*(0*)(*XCAYAXbY要证：,0,21mnnnSxxxXP）中引进松弛变量在（,0,21nmmmSyyyYD）中引进剩余变量在（0.max)(SSXXbXAXtsCXzPP，为）的标准型（0

17、*SSYYCYAY，所以0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题）的最优解为（），（）的最优解，知是（由PXXPXS*）的最优解）为（，（）的最优解，知是（由DYYDYS*0*SSXXbXAX，所以*)*(SXAXb*SXYAXY*YY*)*(SYAYC0.min)(SSYYCYYAtsYbSDD，）为的标准型（*XYAXYS*XX因为X*和Y*分别是（P）和（D）的最优解*CXbY有*SXYAXY*XYAXYS*SXY0*XYS）的最优解为（），因为（PXXS*）的最优解）为（，因为（DYYS*0*SXY0*,XYS0*SSYYCYAY，有

18、0*,*SSXXbXAX，有*SYCAY*SXAXb0*)*(XCAY*)*(*SXAXY*SXYAXYbY*于是*)*(*XYAXYXYAYCXSS0.max)(SSXXbXAXtsCXzPP，为）的标准型（0.min)(SSYYCYYAtsYbSDD，）为的标准型（0)*(*AXbY定理2.4 设X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是方程组 成立 0*)*(0*)(*XCAYAXbY互补松弛定理互补松弛定理:的含义：0*)*(0*)(*XCAYAXbY，*21nxxxXncccC21mnmmnnaaaaaaaaaA21222211121

19、1mbbbb21*21myyyYm21*)(*AXbY*21myyymbbb21m21*X*21myyymbbb21*21XXXm*21myyy*12211XbmXbXbm*)(*222111XbyXbyXbymmm0的含义：0*)*(0*)(*XCAYAXbY*)(*222111XbyXbyXbymmm0*)(*AXbY0.maxXbAXtsCXzP）为设原问题（0.min)(YCYAtsYbSD 为其对偶问题bAX*由0*,AXb即0*12211XbmXbXbm即0*Xbii0*,iy又miXbyiii,2,1,0*0*)*(XCAY同理：由njxcPYjjj,2,1,0*miXbyiii

20、,2,1,0*njxcPYjjj,2,1,0*0*)*(0*)(*XCAYAXbY即：mnmmnnaaaaaaaaaA212222111211nPPP21互补松弛定理：设X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是方程组 成立 miXbyiii,2,1,0*njxcPYjjj,2,1,0*)*(处）的最优解及（处）的最优解即在（*,*,*,*,*,*,*2121mnyyyYDxxxXP jjjcPYx*,0*3必有则若有某个 0*,*4jjjxcPY则必有若有某个 iiibXy*,0*1则必有若有某个 0*,*2iiiybX则必有若有某个把X*代

21、入（P）的第i个方程时为等式松约束紧约束mnmmnnaaaaaaaaaA212222111211nPPP21m21定理2.4 设X*和Y*分别是（P）和（D）的可行解，则X*和Y*分别是（P）和（D）的最优解的充要条件是方程组 成立 对任一种形式的对偶问题成立互补松弛定理互补松弛定理:miXbyiii,2,1,0*njxcPYjjj,2,1,0*)*(优解和最优值偶理论求对偶问题的最，试用对最优值，的最优解12*400*ZX无符号限制321321321321,0,041632532.xxxxxxxxxxxxts32134maxxxxZ例：已知原问题32142minyyyW解：对偶问题为无符号限

22、制321321321321,0,036543132.yyyyyyyyyyyyts约束方程，得：）的代入（，将PX400*441242200*0*21yy得由,04*3x3*6*5321yyy3*3 y12*300*WY最优值），（最优解所以：对偶问题的0,32235.54321543215432xxxxxxxxxxxxxxts5432195243minxxxxxZ例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最2132maxyyW解：对偶问题为0,92355243.21212121212yyyyyyyyyyyts01y2y.92321yy32y221 yy5521yy421 yy

23、63221 yy10*31*WY最优值），（最优解0,32235.54321543215432xxxxxxxxxxxxxxts5432195243minxxxxxZ例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最 约束方程，得：）的代入（将DY3,1*99522244330*0*43xx3*2*2*3*5*543215432xxxxxxxxx2132maxyyW解：对偶问题为0,92355243.21212121212yyyyyyyyyyyts10*31*WY最优值），（最优解得由,03*,01*21yy3*2*2*3*52152xxxxx即2*1*0*215xxx，得令），（得

24、最优解00021*1X0*35*32*215xxx，得令），（得最优解3200035*2X10*10*1*21ZXXX最优值，）（原问题的最优解课堂练习：问题的最优解和最优值试用对偶理论求对偶，的最优解0,2,1,1*X)4,3,2,1(0226332.31434321421ixxxxxxxxxxxxtsi43216368minxxxxZ已知原问题43212263maxyyyyW解：对偶问题为0,636283.432132143221421yyyyyyyyyyyyyyyts23226633由0*4 y得由,02*,01*,01*321xxx3*6*28*3*43221421yyyyyyyy20*0,1,2,2*WY最优值），（最优解对偶问题的0.maxXbAXtsCXz对问题mPPPB21取可行基NBNBXNBCCbBCZ)(max11NBNXBbBX110,0NBXX0NX令bBXB1得011bBX得基本可行解011NBCN、若所有的检验数为最优解则1,X单纯形法：解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数,0,021NBCCBN域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数,0,031NBCCBN