运筹学线性规划对偶问题

第三章线性规划的对偶理论与灵敏度分析

线性规划的对偶问题

对偶问题的基本性质影子价格对偶单纯形法灵敏度分析运筹学线性规划对偶问题共18页，您现在浏览的是第1页!第二节对偶问题的基本性质为了便于讨论，下面不妨总是假设：运筹学线性规划对偶问题共18页，您现在浏览的是第2页!原线性规划问题的矩阵表达式加上松弛变量后为：

一、单纯形法的矩阵描述上式中Xs为松弛变量，，I为m×m单位矩阵。

运筹学线性规划对偶问题共18页，您现在浏览的是第3页!非基变量基变量XBXNXS0XSbBNICj-zjCBCN0

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

Cj-zj0CN-CBB-1N-CBB-1

运筹学线性规划对偶问题共18页，您现在浏览的是第4页!（5）当B为最优基时，应有:

这时从检验数行看出，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有：

因XB的检验数可写为:

则有称为单纯形乘子，若令基变量非基变量XBXNXSCBXBB-1bIB-1NB-1

Cj-zj0CN-CBB-1N-CBB-1

XN的检验数

XS的检验数

XB的检验数

所以XA的检验数

运筹学线性规划对偶问题共18页，您现在浏览的是第5页!两个问题的最终单纯形表见下页：

原问题变量松弛变量

x1x2x3x4x5x315/20015/4－15/2x17/21001/4－1/2x23/2010－1/43/2000-1/4-1/2

对偶问题的剩余变量对偶问题变量y4y5y1y2y3

对偶问题变量对偶问题的剩余变量

y1y2y3y4y5y21/4－5/410－1/41/4y31/215/2011/2－3/215/2007/23/2

原问题松弛变量x3x4x5原问题变量x1x2运筹学线性规划对偶问题共18页，您现在浏览的是第6页!三、线性规划的对偶定理弱对偶性（弱对偶定理）证明：运筹学线性规划对偶问题共18页，您现在浏览的是第7页!2.最优性（最优解判别定理）证明：设xj*是原问题的最优解，yi*是对偶问题的最优解运筹学线性规划对偶问题共18页，您现在浏览的是第8页!4.互补松弛性（互补松弛定理）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零的，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0。也即运筹学线性规划对偶问题共18页，您现在浏览的是第9页!运筹学线性规划对偶问题共18页，您现在浏览的是第10页!Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0xn+1b1a11a12a1n1000xn+2b2a21a22a2n0100xn+mbmam1am2amn001cj-zjc1c2cn000非基变量基变量XBXNXS0XSbBNICj-zjCBCN0

单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下形式。运筹学线性规划对偶问题共18页，您现在浏览的是第11页!

当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：（1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1

（2）初始单纯形表中基变量Xs=b，迭代后的表中

XB=B-1

b（3）初始单纯形表中约束系数矩阵为

，迭代后的表中约束系数矩阵为(B-1左乘):非基变量基变量XBXNXS0XSbBNICj-zjCBCN0基变量非基变量XBXNXSCBXBB-1bIB-1NB-1

Cj-zj0CN-CBB-1N-CBB-1

（4）若初始矩阵中变量Xj的系数向量为Pj，迭代后为，则有:运筹学线性规划对偶问题共18页，您现在浏览的是第12页!

例1

两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：二、原规划与对偶规划问题的变量及解之间的对应关系运筹学线性规划对偶问题共18页，您现在浏览的是第13页!二、原规划与对偶规划问题的变量及解之间的对应关系●对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值●对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值●由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。●更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量

(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量

(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。运筹学线性规划对偶问题共18页，您现在浏览的是第14页!弱对偶定理推论:●max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限。●如果原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。●如果原问题（对偶问题）有可行解，其对偶问题（原问题）无可行解，则原问题（对偶问题）为无界解。注意：如果原问题（对偶问题）无可行解，对偶问题（原问题）具有无界解或无可行解。运筹学线性规划对偶问题共18页，您现在浏览的是第15页!3.强对偶性（对偶定理）定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：步，证明都有最优解。原问题和对偶问题都有可行解，由弱对偶定理推论1可知，原问题目标函