§2 对偶与灵敏度分析§2.1 LP 的对偶问题无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。

一、问题的提出例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表：1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件LP1：⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤++=0,16482122232211212121x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4yLP2：⎪⎩⎪⎨⎧=≥≥++≥+++++=4,3,2,1,0342224212168124213214321i y y y y y y y y y y y MinZ i二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题对称形式下原问题的一般式： 矩阵形式：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤++++++=n j x bx a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j mn mn m m n n n n nn .......21,0 (221)122222121112121112211⎩⎨⎧≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥+++≥+++≥++++++=m j y cy a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j nm mn n n m mn m m mm .......21,0 (221)122222112112211112211⎩⎨⎧≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题：方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。

例2.2写出下列LP 问题的对偶问题：⎪⎪⎩⎪⎪⎨⎧≤≥≤+--≥-++=--+-+++=无约束43214321432143214321,0,0,)3.........(..........2099912)2..(....................85376)1.....(....................53432x x x x x x x x x x x x x x x x x x x x MaxZ 为写出基对偶问题，先将其转化为对称形式，再进行变化：因目标函数为Max ，故约束条件全部转化为“0≤”，所有变量均应为“0≥”。

将（1）式变为：535343214321≤--+-≥--+-x x x x x x x x 和。

再将535343214321-≤-+-≥--+-x x x x x x x x 转化为将（2）式两端同乘以“-1”，并令：0,,;0,''4'4''4'44'33'3≥-=≥∴-=x x x x x x x x 其中得：855376''4'4'321-≤-++--x x x x x所以，例2.2可以变为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-++--≤-++---≤-+--≤+-++--+-+=0,,,,20999912855376533533)(432''4'4'321''4'4'321''4'4'321''4'4'321''4'4'321''4'4'321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x MaxZ 令对应上述四个约束条件的对偶变量为3'2''1'1,,,y y y y ，则其对偶问题为： ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥-≥---≥+++--≥++-≥---≥+-+-+--=0,,,4953349533393297112'6208553'2''1'13'2''1'13'2''1'13'2''1'13'2''1'132''1'13'2''1'1y y y y y y y y y y y y y y y y y y y y y y y y y y y y Min ω令'22''1'11,y y y y y -=-=，将第4与第5个不等式合并，将第三个不等式两端同乘以“-1”得：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤=+--≤-+-≥-+≥++-++=0,0,495339329711262085321321321321321321y y y y y y y y y y y y y y y y y y Min 无约束ω 由以上的推导可以发现有以下规律：方法二：根据原问题与对偶问题之间的关系，可将其归纳如下表：§2.2 对偶问题的基本性质一、单纯形法计算的矩阵描述设线性规划问题的矩阵表达式为：⎩⎨⎧≥≤=0X bAX CXMaxZ ，加上松弛变量s X 后为：⎩⎨⎧≥≥=++=0,00s s s X X b IX AX X CX MaxZ 式中：单位矩阵为m m I x x x X m n n n s ⨯=+++,),......,(21。

单纯形法计算时，总选取为初始基I ，对应基变量为s X 。

设迭代若干步后，基变量为B X ，B X 在初始单纯形表中的系数矩阵为B 。

将B 在初始单纯形表中单独列出，而A 中去掉B 的若干列后组成矩阵N ，同时将C 也分为两块),(N B C C ，B C 是目标函数中基变量B X 的系数行向量；N C 是目标函数中非基变量N X 的系数行向量。

这样LP 的初始单纯形表可列成如下形式：于是原LP 问题可以改写为：⎩⎨⎧≥=++++=0,,0s N B s N B sN N B B X X X bIX NX BX X X C X C MaxZ 将约束条件移项并左乘1-B 后得到B X 的表达式：s N B IX B NX B b B X 111-----=代入目标函数得：s B N B N B X B C X N B C C b B C Z 111)(-----+= 所以，经过迭代之后，得出新的单纯形表为：当为最优基时，在上述单纯形表中有：01≤--N B C C B N ，01≤--B C B 而B X 的检验数可以写为：0=-I C C B B 因此有：01≤--A B C C B ，01≤--B C B称1-B C B 为单纯形乘子，若令1-=B C Y B T则有：⎩⎨⎧≥≥0Y C Y A TT可以发现这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。

将这个解代入对偶问题的目标函数值，有：Z b B C b Y B T ===-1ω即：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。

（其实，这时对偶问题的解也为最优解。

）二、本节讨论先假定原问题和对偶问题为对称形式的LP ，即原问题为：⎩⎨⎧≥≤=0X b AX CX MaxZ 其对偶问题为：⎩⎨⎧≥≥=0Y C Y A YbMin T T ω然后说明对偶问题的基本性质在非对称形式也适用。

1.对称性：对偶问题的对偶是原问题。

证明：原问题与其对偶问题分别为：⎩⎨⎧≥≤=0X b AX CX Max 与⎩⎨⎧≥≥=0Y C Y A Yb Min T T ω2.弱对偶性：若X 是原问题可行解，Y 是对偶问题的可行解，则存在b Y X C ≤。

证明：设原问题为：0≥≤=X bAX CX Max原问题的对偶问题为：0≥≥=Y C Y A Yb Min TT ω3.无界性：若原问题为无界解，则其对偶问题为无可行解。

证明：由弱对偶性可得，本性质成立。

4.可行解是最优解时的性质：若X 是原问题可行解，Y 是对偶问题的可行解，当b Y X C =时，X 与Y 是原问题与对偶问题的最优解。

证明：5.对偶定理：若原问题有最优解，那么其对偶问题也有最优解，且目标函数值相等。

6.互补松弛性：若X 是原问题可行解，Y 是对偶问题的可行解，那么00==X Y X Y s s 和，当且仅当为X ，Y 最优解。

（在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量值一定为零。

）0,01==∑=si i nj j ij i x b x a y 则有　若 ；00,1=∑=i si i nj j ij y x b x a 则有　若 。

将互补松弛性质应用于其对偶问题时可以这样叙述：j mi i ij j c y a x =∑=1,0则有　若 ；0,1=∑=j j mi i ij x c y a 则有　若 。

由互补松弛定理可知：若原问题最优解中的第j个变量为正，则其对偶问题中与之对应的第j个约束条件在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶问题中第j个约束条件在最优情况下呈严格不等式，则原问题最优解中第j个变量必为0。

类似地，若对偶问题最优解中第i个对偶变量为正，则其原问题中与之对应的第i个约束条件在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i个约束条件在最优情况下呈严格不等式，则对偶问题最优解中第i个对偶变量必为0。

互补松弛定量阐明了原问题及其对偶问题最优解各分量之间的关系，当已知一对对偶问题之一的最优解时，可利用该定量求出另一个问题的最优解。

7.设原问题是：0,≥=+=s s X X bX AX CX Max对偶问题为：0,≥=-=s s Y Y CY YA YbMin ω则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下表所示：这里1S Y 是对应原问题中B X 基变量的剩余变量，2S Y 是对应原问题中非基变量N X 的剩余变量。