2.对偶问题与灵敏度分析

第二章线性规划的对偶理论及其应用对偶是一种普遍现象2.1线性规划的对偶理论2.1.1线性规划原问题与对偶问题的表达形式•任何线性规划问题都有其对偶问题•对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？0,,,B15232A25322..432)(max4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源例2.1.1–设A、B资源的出售价格分别为y1和y2–显然商人希望总的收购价越小越好–工厂希望出售资源后所得不应比生产产品所得少0,44233332222112..2121212121yyyyyyyyyyts的所得产品的所得产品的所得产品的所得产品目标函数ming(y)=25y1+15y20,,,B15232A25322..432)(max4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源2.1.1线性规划原问题与对偶问题的表达形式0XbAXtsCXxf..)(max:原问题0YCYAtsYbyg..)(min:对偶问题TmnmTnbbbbcccCyyyYxxxX),,,(),,,(),,,(),,,(21212121上两式中mnmmnnaaaaaaaaaA2122221112112.1.1线性规划原问题与对偶问题的表达形式0,,,..)(min21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybybyg把对偶问题展开0YCYAtsYbYgTTTTT..)(min:对偶问题习惯写为2.1.2标准(max,)型的对偶变换•目标函数由max型变为min型•对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m•对偶问题约束为型，有n行•原问题的价值系数C变换为对偶问题的右端项•原问题的右端项b变换为对偶问题的价值系数•原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵•原问题与对偶问题互为对偶–对偶问题可能比原问题容易求解–对偶问题还有很多理论和实际应用的意义2.1.3非标准型的对偶变换0,510342023..54)(max2.1.21221212121xxxxxxxxtsxxxf不限原线性规划问题例0,,551033420223..554)(max)(max,221221221221221221xxxxxxxxxxxxxxxtsxxxxf型标准问题化为0,,,532532443..551020)(min43214321432143214321则应用标准型对偶变换规不限经整理得令3213213213214332211,0,0532443..51020)(min:,,yyyyyyyyytsyyyygwwywywy表2.1.1对偶变换的规则•约束条件的类型与非负条件对偶•非标准的约束条件类型对应非正常的非负条件•对偶变换是一一对应的原问题(max)对偶问题(min)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为型对偶变量yi0第i行约束条件为型对偶变量yi0第i行约束条件为=型对偶变量yi不限决策变量xj0第j行约束条件为型决策变量xj0第j行约束条件为型决策变量xj不限第j行约束条件为=型2.2线性规划的对偶定理2.2.1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值•为了便于讨论，下面不妨总是假设0XbAXtsCXxf..)(max:原问题0YCYAtsYbyg..)(min:对偶问题#CXAXYbY0YCAY0XbAXYX.,,:0000000000容易看出有故有题的可行解分别为原问题和对偶问由于证弱对偶定理推论•max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限•如果原max(min)问题为无界解，则其对偶min(max)问题无可行解•如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解•注：有可能存在原问题和对偶问题同时无可行解的情况2.2.2最优解判别定理定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0bCX,Y0b=CX0Yb。证毕。2.2.3主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。主对偶定理的证明证：现证明定理的后一句话。设X0为原问题的最优解，它所对应的基矩阵是B，X0=B1b，则其检验数满足CCBB1A0令Y0=CBB1，则有Y0AC；而对原问题松弛变量的检验数有0CBB1I0，即Y00。显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b=CBB1b而原问题最优解的目标函数值为f(X0)=CX0=CBB1b故由最优解判别定理可知Y0为对偶问题的最优解。证毕。–该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本–即对偶变量的最优解是原问题资源的影子价格2.2.4互补松弛定理定理设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0+V0X0=0证：由定理所设，可知有AX0+U0=bX0,U00(1)Y0AV0=CY0,V00(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得Y0U0+V0X0=Y0bCX0若Y0U0+V0X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。miuynjxviijj,,2,10,,2,1000002.2.4互补松弛定理Y0U0+V0X0=0有什么应用•若(Y0)i0，则(U0)i=0，意味着原问题第i约束行必须为=约束；对(X0)i0亦如此•可用来简化问题的求解•线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解–原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优解miuynjxviijj,,2,10,,2,1000002.2.5原问题检验数与对偶问题的解•在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值•容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值•由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。•更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的机会成本对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。例2.2.3原问题检验数与对偶问题的解Cj536-600MCBXBbx1x2x'3x3x4x5x60x41812111000x51621(3)3010Mx6101111001OBJ=10MMMMM00Mcj-zj5+M3+M6+M-6-M0000x438/31/35/30011/306x'316/32/31/31101/30Mx614/31/3(2/3)0001/31OBJ=32-14M/34-M/32-2M/36602+M/3Mcj-zj1+M/31+2M/3000-2-M/300x411/200011/25/26x'33(1/2)01101/23/23x271/210001/23/2OBJ=399/236603/23/2cj-zj1/200003/2-M-3/20x4400111135x1610220113x24011(1)012OBJ=425377021cj-zj001102-M+10x4801001015x11412000136x340111012OBJ=465466013cj-zj010001-M3对偶问题最优解：y4=0y5=1y6=0y1=0y2=1y3=3原问题最优解：x1=14,x2=0,x3=-4,x4=8,x5=0,x6=0,OBJ=46Cj18161000MCBYBby1y2y3y4y5y60y4-5-1-2-11000y5-3-2-1-1010My6613(1)001OBJ=6MM3MM00Mcj-zj18-M16-3M10-M0000y410(1)01010y53-12001110y36131001OBJ=601030100010cj-zj8-14000M-1016y210101010y51-300-21-110y33101-30-2OBJ=46101610-140-4cj-zj800140M4原问题最优解：x4=8x5=0x6=0x1=14x2=0x3=4对偶问题最优解：y1=0,y2=1,y3=3,y4=0,y5=1,y6=0,OBJ=46线性规划原问题与对偶问题的表达形式0XbAXtsCXxf..)(max:原问题0YCYAtsYbyg..)(min:对偶问题TmnmTnbbbbcccCyyyYxxxX),,,(),,,(),,,(),,,(21212121上两式中mnmmnnaaaaaaaaaA212222111211对偶单纯形算法•基本思想•算法过程•算例♂返回对偶单纯型算法基本思路：•原单纯型迭代要求每步都是基础可行解•达到最优解时，检验数cj–zj0(max)或cj–zj0(min)•但对于(min,)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决•大M法和二阶段法较繁•能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cj–zj0(max)或cj–zj0(min)–每步迭代保持检验数满足最优条件，但减少非可行度–如何判断达到最优解–如何保证初始基础解满足最优条件–为什么叫对偶单纯型法b=B1b0基本思想♂返回NB1I0N0BBxNxbBcB101bB从满足01bB的基解入手，在保持01bB的条件下寻找满足01ABccB的基解。NB1IN0BbBcB101bBBxNx同样可以从满足01ABccB的基解出发，在保持01ABccB的条件下寻找满足01bB的基解。我们称满足01ABccB的基解为正则解。对偶单纯形算法就是从正则解出发，从一个正则解调整到另一个正则解，直至找到可行的正则解。NB1I0N0BbBcB1bB1BxNx01ABccB0YAc1BcYB正则解对偶可