《运筹学》胡运权 第4版 第二章 线性规划的对偶理论及灵敏度分析

第二章线性规划的对偶理论及灵敏度分析OperationalResearch(OR)线性规划的对偶问题与灵敏度分析线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划对偶原理对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。问题的导出项目ⅠⅡ每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21例2-1我们引用第一章中美佳公司的例子，如表1其线性规划问题为：122121212max25156224..5,0zxxxxxstxxxx假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？（LP1）问题的导出2312362521yyyyy例2-1条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工序的出让代价。y1,y2,y3的取值应满足：美佳公司用6h设备B和1h调试可生产一件家电I,赢利2元用5h设备A,2h设备B及1h调试可生产一件家电Ⅱ，赢利1元该公司希望用最小代价把美佳公司的全部资源收买过来，即：123min1524zyyy问题的导出123minw1524yyy例2-1综上所述，2312312362..521,,0yystyyyyyy（LP2）LP1和LP2两个线性规划问题，通常称LP1为原问题，LP2为前者的对偶问题。对偶问题的定义nnxcxcxcZ2211max0,,,..212121212222111211nmnmnmmnnxxxbbbxxxaaaaaaaaatsmmybybybW2211min0,,,..212121212221212111mnmmnnnmmyyycccyyyaaaaaaaaats对称形式的对偶问题对偶问题的定义对称形式的对偶问题CXZmaxTTYbWmin0..TTTTYCYAts0..XbAXts对偶问题的定义对偶问题的特点•若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然•原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵•极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。对偶问题的定义一般线性规划问题的对偶问题nnxcxcxcZ2211maxmmybybybW2211minnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa~1),0(0),(),(),(22112222212111212111或符号不限mijnmmnnnmmmmycyayayacyayayacyayaya~1),0(0),(),(),(22112222211211221111或符号不限对偶问题的定义对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数maxZ目标函数minZ约束条件：m个第i个约束类型为“≤”第i个约束类型为“≥”第i个约束类型为“＝”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”对称形式下的对偶问题例2－2标准型对偶问题nnxcxcxcZ2211max0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats符号不限mnmmnnnmmmmyyycyayayacyayayacyayaya,,,2122112222211211221111mmybybybW2211min对称形式下的对偶问题例2－3321324minxxxZ0,32121321321,01413121110987654xxxxxxxxxxx符号不限32114117maxyyyW0y0,y,3212132132131062139541284符号不限yyyyyyyyy非对偶形式的原-对偶问题例2-4写出下列问题的对偶问题1122331111213322112222333113223333123max..00zcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx，，无约束（2.4a）（2.4b）（2.4c）（2.4d）11223333maxzcxcxcxcx11112213313321122223323321122223323331132233333312331223..0000axaxaxaxbaxaxaxaxbstaxaxaxaxbaxaxaxaxbxxxx，，，对偶变量y1y2′y2″y3′先转换成对称形式，如下：非对偶形式的原-对偶问题例2-4令各约束对应的对偶变量分别为y1、y2′、y2″、-y3′11222233minwbybybyby11121221231312122222232313123223233313123223233312331223..0000ayayayaycayayayaycstayayayaycayayayaycyyyy，，，令y2=y2′-y2″，y3=-y3′，原问题的对偶问题为112233minwbybyby112131122232132333123112321233123..0y0ayayaycayayaycstayayaycyy，无约束，对应关系总结项目原问题（对偶问题）对偶问题（原问题）A约束系数矩阵其约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数maxz=∑CjXjminw=∑biyi(1,...,)00jjjjxjnxxx变量无约束ijijijijijijnjaycaycaycmi=1mi=1mi=1有个（=1，...,n）约束条件nijijnijijnijijmjmaxbaxbaxbi=1i=1i=1有个（=1，...,）约束条件y(1,...,)00jjjjjmyyy变量无约束线性规划的对偶问题与灵敏度分析线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划对偶问题的基本性质单纯形法计算的矩阵描述对称形式线性规划矩阵表达式加上松弛变量Xs后为：max0..0,0zCXXsAXIXsbstXXs其中松弛变量Xs=（xn+1,xn+2,...,xn+m）,I为m×m单位矩阵项目基变量基变量XBXNXs0XsbBNIcj-zjCBCN0选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。A中去掉B的若干列后剩下的列组成矩阵N。进一步迭代,新的单纯形表如下：对偶问题的基本性质项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N–CBB-1•对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1•初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b•初始单纯形表中约束系数矩阵为[A,I]=[B,N,I]，迭代后的表中约束系数矩阵为[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]•若初始矩阵中变量xj的系数向量为Pj，迭代后为Pj′，则有Pj′=B-1Pj•当B为最优基时，表中应有CN-CBB-1N≤0,-CBB-1≤0对偶问题的基本性质例2-5参看例2-1中的原问题和对偶问题，并分别加上松弛变量和剩余变量，如下：12345max2000zxxxxx231241255156224..50(1,...,5)jxxxxxstxxxxj12345min1524500wyyyyy234123562..5210(1,...,5)iyyystyyyyyi对偶变量y1y2y3对偶变量x1x2对偶问题的基本性质两个问题的最终单纯形表如下：项目原问题变量原问题松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2变量对偶问题的剩余变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2变量原问题松弛变量原问题变量x3x4x5x1x2对偶问题的基本性质1.弱对偶性如果xj（j=1，...，n）是原问题的可行解，yi（i=1，...，m）是其对偶问题的可行解，则恒有11jjnmiijicxby对偶问题的基本性质弱对偶性的推论：(1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。(2)如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。对偶问题的基本性质(3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。对偶问题的基本性质对偶问题的基本性质最优性如果(j=1,...,n)是原问题的可行解，(i=1,...,m)是其对偶问题的可行解，且有jˆxiˆyˆˆnmjjiij=1i=1cx=by则(j=1,...,n)是原问题的最优解，(i=1,...,m)是其对偶问题的最优解。jˆxiˆy对偶问题的基本性质强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。对偶问题的基本性质互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即iˆy若0，则有，即1ˆnijjijaxbˆ0six若，即，则有1ˆnijjijaxbˆ0sixˆ0iy因此一定有，ˆsixˆ0iy线性规划的对偶问题与灵敏度分析线性规划的对