运筹学线性规划对偶问题课件.ppt

1、第三章第三章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析 n线性规划的对偶问题线性规划的对偶问题 n对偶问题的基本性质对偶问题的基本性质n影子价格影子价格n对偶单纯形法对偶单纯形法n灵敏度分析灵敏度分析第1页，共18页。第二节第二节 对偶问题的基本性质对偶问题的基本性质为了便于讨论，下面不妨总是假设：为了便于讨论，下面不妨总是假设：0XbAXCX.max :tsZ原问题0YCYAbY.min :tsW对偶问题第2页，共18页。原线性规划问题的矩阵表达式加上松弛变量后为：原线性规划问题的矩阵表达式加上松弛变量后为：一、一、单纯形法的矩阵描述单纯形法的矩阵描述上式中上式中XsXs

2、为松弛变量，为松弛变量，I为为m mm m单位矩阵。单位矩阵。0,00maxsssXXbIXAXXCXz),(21mnnnsxxxX0,0,.000 21212211222222121111212111212211mnnnnmmnnmnmmnnnnnnmnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxatsxxxxcxcxczMax第3页，共18页。Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0 xn+1b1a11a12a1n1000 xn+2b2a21a22a2n0100 xn+mbmam1am2amn001cj-zjc1c2cn000非基变量非基

3、变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0 单纯形法计算时，总选取单纯形法计算时，总选取I I为为初始基初始基，对应基变量为对应基变量为XsXs。设迭代若干步后，基变量为设迭代若干步后，基变量为X XB B，在初始单纯形表中的在初始单纯形表中的系数矩阵为系数矩阵为B B。B B将在初始单纯形表中单独列出，而将在初始单纯形表中单独列出，而A A中去掉若干列中去掉若干列后剩下的列组成矩阵后剩下的列组成矩阵N N，这样初始单纯形表可列成如下形式。这样初始单纯形表可列成如下形式。第4页，共18页。非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB

4、 CN0 当迭代若干步后，基变量为当迭代若干步后，基变量为X XB B时时，则该步的单纯形表中由则该步的单纯形表中由X XB B系数组成的矩阵为系数组成的矩阵为I I。又因单纯形法的迭代是对约束增广矩阵进行的行的又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换初等变换，对应对应X XS的系数矩阵在新表中的系数矩阵在新表中应为应为B B-1-1。故当基变量为故当基变量为X XB B时，新的单纯形表具有如下形式。时，新的单纯形表具有如下形式。基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N

5、-CB B B-1-1 第5页，共18页。当迭代后基变量为当迭代后基变量为XB时时，其在初始单纯形表中的系数矩阵为其在初始单纯形表中的系数矩阵为B B，则有：则有：（1 1）对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I I，迭代后的单纯形表中为迭代后的单纯形表中为B B-1-1（2）初始单纯形表中基变量初始单纯形表中基变量Xs=bXs=b，迭代后的表中迭代后的表中 XB=B B-1-1 b（3）初始单纯形表中约束系数矩阵为初始单纯形表中约束系数矩阵为 ，迭代后的表中约迭代后的表中约束系数矩阵为束系数矩阵为(B B-1-1 左乘左乘):INBIA,1111111,BNBIIBNBB

6、BIBAB非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N -CB B B-1-1（4）若初始矩阵中变量若初始矩阵中变量Xj的系数向量为的系数向量为Pj，迭代后为，迭代后为 ，则有，则有:jPjjPBP1第6页，共18页。（5）当当B B为最优基时为最优基时，应有，应有:01NBCCBN01BCB这时从检验数行看出，若取其相反数恰好是其对偶问题的一个可行解。这时从检验数行看出，若取其相反数恰好是其对偶问题的一

7、个可行解。将这个解代入对偶问题的目标函数值，有将这个解代入对偶问题的目标函数值，有：因因XB的检验数可写为的检验数可写为:zbBCbYwB11BCYB0YCYA则有则有称为称为单纯形乘子单纯形乘子，若令若令1BCB基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N -CB B B-1-1 XN的检验数的检验数 XS的检验数的检验数 0ICCBBXB的检验数的检验数 01ABCCB所以所以XA的检验数的检验数 第7页，共18页。例例1 1 两个互为对偶的线性规划问题，两者分别加上两个互为对偶的线

8、性规划问题，两者分别加上松弛和剩余变量后为：松弛和剩余变量后为：543210002maxxxxxxz)5,.1(05242615552142132jxxxxxxxxxj543210052415minyyyyyw)5,1(0125265321432iyyyyyyyyi二、原规划与对偶规划问题的变量及解之间的对应关系二、原规划与对偶规划问题的变量及解之间的对应关系第8页，共18页。两个问题的最终单纯形表见下页：两个问题的最终单纯形表见下页：jjzc 原问题变量原问题变量松弛变量松弛变量x1x2x3x4x5x315/20015/415/2x17/21001/41/2x23/20101/43/2000

9、-1/4-1/2对偶问题的剩余变量对偶问题的剩余变量对偶问题变量对偶问题变量y4y5y1y2y3jjzc对偶问题变量对偶问题变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4 5/410 1/41/4y31/215/2011/23/215/2007/23/2原问题松弛变量原问题松弛变量x3x4x5原问题变量原问题变量x1x2第9页，共18页。二、原规划与对偶规划问题的变量及解之间的对应关系二、原规划与对偶规划问题的变量及解之间的对应关系对偶对偶(minmin型型)变量的最优解等于原问题变量的最优解等于原问题松弛变量松弛变量检验数的检验数的绝对值绝对值对偶问题最优解的剩余变量

10、解值等于原问题对偶问题最优解的剩余变量解值等于原问题对应变量对应变量的检的检验数的绝对值验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在更一般地讲，不管原问题是否标准，在最优解的单纯型表最优解的单纯型表中，都有原问题中，都有原问题虚变量虚变量(松弛或剩余松弛或剩余)的检验数对应其对的检验数对应其对偶问题偶问题实变量实变量 (对偶变量对偶变量)的最优解，原问题的最优解，原问题实变量实变量(决策决策变量变量)的检验数对应其对偶问题的检验

11、数对应其对偶问题虚变量虚变量 (松弛或剩余变量松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。可以了。第10页，共18页。三、线性规划的对偶定理三、线性规划的对偶定理弱对偶性（弱对偶性（弱弱对偶定理对偶定理）证明：证明：miiinjjjminjijijmiinjjijmiiiminjijijnjjmiiijnjjjybxcyxayxaybyxaxyaxc111111111111)()(第11页，共18页。弱弱对偶定理推论对偶定理推论:max问题问题的任何可行解目标函数值是其的任何可行解目标函数值是其对偶对偶min问题问

12、题目标目标函数值的下限；函数值的下限；min问题的任何可行解目标函数值是其对问题的任何可行解目标函数值是其对偶偶max问题目标函数值的上限。问题目标函数值的上限。如果原问题（对偶问题）为无界解，则其对偶问题（原问如果原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。题）无可行解。如果原问题（对偶问题）有可行解，其对偶问题（原问题）如果原问题（对偶问题）有可行解，其对偶问题（原问题）无可行解，则原问题（对偶问题）为无界解。无可行解，则原问题（对偶问题）为无界解。u注意：注意：如果原问题（对偶问题）无可行解，对偶问题（原如果原问题（对偶问题）无可行解，对偶问题（原问题）具有无界解或无可行

13、解。问题）具有无界解或无可行解。第12页，共18页。2.2.最优性（最优解判别最优性（最优解判别定理）定理）证明：设xj*是原问题的最优解，yi*是对偶问题的最优解miiimiiinjjjnjjjmiiinjjjmiiinjjjmiiimiiinjjjnjjjybybxcxcybxcybxcybybxcxc11*1*11*1*1111*1*1,第13页，共18页。3.强对偶性（对偶强对偶性（对偶定理）定理）定理定理 如果原问题和对偶问题都有可行解，则它们都有最优如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。解，且它们的最优解的目标函数值相等。证：第一步，证明

14、都有最优解。证：第一步，证明都有最优解。原问题和对偶问题都有可原问题和对偶问题都有可行解，由弱对偶定理推论行解，由弱对偶定理推论1可知，原问题目标函数有上界，可知，原问题目标函数有上界，对偶问题的目标函数有下界，故一定存在最优解。对偶问题的目标函数有下界，故一定存在最优解。第二步，证明最优解的目标函数值相等。第二步，证明最优解的目标函数值相等。根据单纯形根据单纯形法的矩阵描述，原问题有最优解，对偶问题为可行解，且法的矩阵描述，原问题有最优解，对偶问题为可行解，且二者的目标函数值相等，根据最优性定理，二者的解均为二者的目标函数值相等，根据最优性定理，二者的解均为最优解。最优解。第14页，共18页。4.互补松弛性（互补松弛互补松弛性（互补松弛定理）定理）在线性规划问题的最优解中，如果对应某一约束条件的对在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为偶变量值为非零非零的，则该约束条件取的，则该约束条件取严格等式严格等式；反之如果约束；反之如果约束条件取条件取严格不等式严格不等式，则其对应的对偶变量一定为，则其对应的对偶变量一定为0。也即。也即第15页，共18页。第16页，共18页。第17页，共18页。第18页，共18页。