运筹学线性规划对偶问题

1、第三章 线性规划的对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,第二节 对偶问题的基本性质,为了便于讨论，下面不妨总是假设,原线性规划问题的矩阵表达式加上松弛变量后为,一、单纯形法的矩阵描述,上式中Xs为松弛变量， ，I为mm单位矩阵,单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下形式,当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对

2、约束增广矩阵进行的行的初等变换，对应XS的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有如下形式,当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有： （1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 （2）初始单纯形表中基变量Xs=b，迭代后的表中 XB= B-1 b （3）初始单纯形表中约束系数矩阵为 ，迭代后的表中约束系数矩阵为(B-1 左乘),4）若初始矩阵中变量Xj的系数向量为Pj ，迭代后为 ，则有,5）当B为最优基时，应有,这时从检验数行看出，若取其相反数恰好是其对偶问题的一个可行解。 将这个解代入对偶问题的目标函数值，有,因XB的检

3、验数可写为,XN的检验数,XS的检验数,XB的检验数,例1 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为,二、原规划与对偶规划问题的变量及解之间的对应关系,两个问题的最终单纯形表见下页,二、原规划与对偶规划问题的变量及解之间的对应关系,对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值 对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。 更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，

4、原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了,三、线性规划的对偶定理,弱对偶性（弱对偶定理,证明,弱对偶定理推论,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限。 如果原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 如果原问题（对偶问题）有可行解，其对偶问题（原问题）无可行解，则原问题（对偶问题）为无界解。 注意：如果原问题（对偶问题）无可行解，对偶问题（原问题）具有无界解或无可行解,2. 最优性（最优解判别定理,证明：设xj*是原问题的最优解， yi*是对偶问题的最优解,3.强对偶性（对偶定理,定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。 证：第一步，证明都有最优解。原问题和对偶问题都有可行解，由弱对偶定理推论1可知，原问题目标函数有上界，对偶问题的目标函数有下界，故一定存在最优解。 第二步，证明最优解的目标函数值相等。根据单纯形法的矩阵描述，原问题有最优解，对偶问题为可行解，且二者的目标函数值相等，根据最优性定理，二者的解均为最优解,4. 互补松弛性（互补松弛定理,在