运筹学课件 第2章：线性规划的对偶理论

第二章线性规划的对偶理论(DualityTheory)线性规划的对偶问题对偶问题的基本性质对偶问题的经济解释----影子价格对偶单纯形法灵敏度分析WinQSB软件应用第一节线性规划的对偶问题一、问题的提出【例2-1】第一章例1-1中讨论了某企业利用三种资源生产甲乙两种产品的生产计划问题，得到其线性规划问题为：0,6553623167090max)1(212212121xxxxxxxxxzLP下面从另一个角度来讨论这个问题：假定该企业决定自己不生产产品，而将现有的资源转让或出租给其他企业，那么该如何确定资源的转让价格？分析问题：1、定价不能太高，否则买方无法接受，并且对买方来说，其目的是越低越好；2、定价不能太低，否则企业不愿意放弃生产、出让资源合理的价格应是对方用最少的资金购买该企业的全部资源，而该企业所获得的利润又不低于自己组织生产时所获得的利润。设分别用y1、y2和y3代表单位时间(h)设备、每公斤材料A、材料B的出让代价，则有：（LP2）321653616minyyyw0,,705290332132121yyyyyyyy对偶问题从以下方面比较(LP1)与(LP2)：系数矩阵目标函数价格系数向量约束条件右端项目标函数约束条件决策变量原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数Maxz=CXMinw=Y’b约束条件AX≤bA’Y≥C’决策变量X≥0Y≥00,6553623167090max)1(212212121xxxxxxxxxzLP（LP2）321653616minyyyw0,,705290332132121yyyyyyyy二、对称形式下对偶问题的一般形式满足下列条件的线性规划问题称为具有对称形式:(1)变量均满足非负约束；(2)约束条件当目标函数求极大时取“≤”号，目标函数求极小时取“≥”号注：对称形式与线性规划标准型是两种不同的形式，对称形式中约束条件的符号由目标函数决定nnxcxcxcz1100max),,2,1(022112222212111212111njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnnmmybybybw2211min),,2,1(022112222211211221111miycyayayacyayayacyayayainmmnnnmmmm原问题CXzmax0XbAXbYwmin0YCYA对偶问题若原问题为求极小形式的对称形式线性规划问题，对偶问题应该具有什么形式？0'YCYAbYwMin'0XbAXCXzMaxbYw'max0'YCYACXzmin0XbAX★若一个线性规划问题是另一个线性规划问题的对偶问题，则它们互为对偶问题★对偶问题的对偶问题是原问题【例2-2】写出下述线性规划问题的对偶问题32134maxxxxZ例中目标函数为max，若为对称形式，则约束条件应为“≤”号，所有变量均应≥0。——非对称形式三、非对称形式的原——对偶问题关系)(,0,0)(4)(163)(2532321321321321dxxxcxxxbxxxaxxx无约束2．变量均有非负约束令则1．目标函数为求极大，故约束条件应均为“≤”号约束b两边乘-1：163321xxx444321321321xxxxxxxxx0,222xxx0,,33333xxxxx约束c写成两个不等式约束：3321334maxxxxxz0,,,4416632553233213'3'213'3'213'3'213'3'21xxxxxxxxxxxxxxxxxxxx3321442minyyyy0,,,3653654313233213321332133213321yyyyyyyyyyyyyyyyyyyy令，则33322,yyyyy32142minyyy无约束321321321321,0,036543132yyyyyyyyyyyy32134maxxxxZ无约束321321321321,0,041632532xxxxxxxxxxxx原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数Maxz=CX目标函数Minw=Y’b约束条件m个≤≥=m个≥0≤0无约束变量变量n个≥0≤0无约束n个≥≤=约束条件【例2-3】写出下列线性规划问题的对偶问题4321532minxxxx无约束43214324314321,0,,0642253xxxxxxxxxxxxxx无约束3213213213121321,0,01523322645maxyyyyyyyyyyyyyyyyz4321532maxxxxxz无约束432143214214321,0,,0643247235234xxxxxxxxxxxxxxx【练习】写出下列线性规划问题的对偶问题无约束32132131321321321,0,01725433322234645minyyyyyyyyyyyyyyyyyw第二节对偶问题的基本性质一、单纯形法计算的矩阵描述CXzmax0XbAX(LP)(LD)bYwmin0YCYA对称形式线性规划问题的矩阵表达式加上松弛变量后为：0,00maxsssXXbIXAXXCXz其中，Xs=(xn+1,xn+2,…，xn+m)为松弛变量，I为m×m单位矩阵。设B是一个可行基，也称基矩阵。若将系数矩阵A分为(B,N)两块(这里N是非基变量的系数矩阵),对应于基B的变量为XB，其它非基变量用XN表示。则:NBXXX同时也将C分为两块(CB,CN)，CB是目标函数中基变量XB的系数行向量，CN是目标函数中非基变量XN的系数行向量。于是0CNCBCj-zjINBbXs0XsXNXB基变量非基变量初始单纯形表-CBB-1CN-CBB-1N0Cj-zjB-1B-1NIB-1bXBCBXsXNXB非基变量基变量最终单纯形表000)(111BCNBCCBBCCBBNBB0)()(1NBBCCCBNB0011BCABCCBB0YCYA即1BCYB此时，zbBCbYB1'若B-1b为最优解，则1.初始表中单位阵在迭代后单纯形表中对应的位置就是B-12.对于原问题的最优解，各松弛变量检验数的相反数恰好是其对偶问题的一个可行解，且两者具有相同的目标函数值。根据下面介绍的对偶问题的基本性质还将看到，若原问题取得最优解，则对偶问题的解也为最优解。0YCAY二、对偶问题的基本性质1、对称性：对偶问题的对偶问题是原问题2、弱对偶性：设和分别是问题（LP）和（LD）的可行解，则恒有:__X__Y____bYXC证明：bYXAYbXAXCXAYCAYCYA注：LP求极大，LD求极小推论1：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。试估计它们目标函数的界，并验证弱对偶性原理。例102023220322432max41432143214321xxxxxxxxxxxxxZLP：0,042333222122020min212121212121yyyyyyyyyyyyWLD：解：由观察可知：=（1,1,1,1），=（1,1），分别是（LP）和（LD）的可行解。Z=10，W=40，故有弱对偶定理成立。由推论⑴可知，W的最小值不能小于10，Z的最大值不能超过40。__X__YbYXC__推论2：如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解注：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然推论3：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界例3已知试用对偶理论证明原问题无界。21max:xxzP0,,122321321321xxxxxxxxx212minyyw0,0011221212121yyyyyyyy0,0242max21212121xxxxxxxxZ无界解如：LP0,01224min21212121yyyyyyyyW无可行解LD又如0,11max:21212121xxxxxxxxZLP0,11min:21212121yyyyyyyyWLD两个问题都无可行解3、最优性若和分别是LP和LD的可行解，则当时，和分别是问题LP和LD的最优解。bYXCˆˆXˆYˆXˆYˆ证：设和分别是原问题和对偶问题的任一可行解由弱对偶性故XYbYXCˆbYXCˆbYXCbYXCˆˆ4、强对偶性若原问题有最优解，则对偶问题也有最优解（反之亦然），且目标函数的最优值必相等。证：设是原问题的最优解，由单纯形法的矩阵表示，故是对偶问题的可行解代入目标函数有由最优性是对偶问题的最优解。XˆCABCB11ˆBCYBXCbBCbYBˆˆ1Yˆ5、互补松弛性若，分别是LP和LD的可行解，和是它们可行解的松弛变量，那么，为最优解当且仅当，。XˆYˆsXsYXˆYˆ0ˆsXY0ˆXYs证：设由弱对偶性0,0maxszXXbIXAX0XCXss0,0minsssYYCIYYA0YbYwbYXAYXCˆˆˆˆ0ˆˆˆ0ˆˆˆXAYbYXAYXC0)ˆ(ˆ0ˆ)ˆ(XAbYXAYC0ˆ0ˆssXYXYbYXAYXCˆˆˆˆ在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即若，则有，即0ˆiynjijijbxa1ˆ0ˆsix若，即，则有njijijbxa1ˆ0ˆsix0ˆiy若，则有0ˆjxmijiijcya1ˆ若，则mijiijcya1ˆ0ˆjx推论0ˆ,0;0,0ˆ0ˆYXXYXYsss则则0ˆ,0;0,0ˆ0ˆXYYXXYsss则则证明：【例2-4】已知原问题的最优解为X*=（0,0,4），Z=12试求对偶问题的最优解。