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

第三章 线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质； 2、对偶单纯形法；3、灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。

要 求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§1 对偶问题的对称形式一、对偶问题引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A 、B 两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？解：设1x 、2x 分别为甲、乙两种产品的产量则目标函数2132m ax x x z +=约束条件 ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,12416482212121x x x x x x(1)假设该工厂决定不再生产甲、乙产品，而将其出租或出售。

这时要考虑每种资源的定价问题，设321,,y y y 分别为出租单位设备台时的租金和出让单位原材料A 、B 的附加额。

作一比较：若用一个单位台时和4个单位原材料A 生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。

即：2421≥+y y同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。

即：34231≥+y y将工厂所有设备台时和资源都出租和出让，其收入为32112168y y y ++=ω对工厂来说，ω越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足≥所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。

为此，得到如下模型：32112168m in y y y ++=ω⎪⎩⎪⎨⎧=≥≥+≥+3,2,1,0342243121j y y y y y j(2)我们就称(2)为模型(1)的对偶问题。

一般地，设原问题为n n x c x c x c z +++= 2211m ax⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤+++nj x bx a x a x a b x a x a x a b x a x a x a j mn mn m m n n n n ,,2,1,022112222212111212111则其对偶问题为：n n y b y b y b +++= 2211m in ω⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥+++≥+++≥+++mi y cy a y a y a c y a y a y a c y a y a y a i nm mn n n m m m m ,,2,1,022112222211211221111 矩阵形式：原问题 对偶问题cX z =max Yb =ωmin⎩⎨⎧≥≤0XAX ⎩⎨⎧≥≥≥0)(y C y A C YA T T T 实际为例1 求下列问题的对偶问题4321532m in x x x x z +-+=⎪⎪⎩⎪⎪⎨⎧≥≤=++≤-+≥+-+无约束43214324314321,0,,0642253x x x x x x x x x x x x x x解：321645m ax y y y ++=ω⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≥=+--≤++-≤+≥+无约束3213213213121,0,01523322y y y y y y y y y y y y y§2 对偶问题的基本性质一、对称性：对偶问题的对偶是原问题。

证：设原问题为cX z =max⎩⎨⎧≥≤0X b AX 则其对偶问题为：Yb =ωmin⎩⎨⎧≥≥0y C YA对上式两边取负号，得Yb-=-ωmin⎩⎨⎧≥-≤-0y C YA Ybw-=-∴=--)max (min )max (ωω ⎩⎨⎧≥-≤-0Y CYA上式的对偶问题为CXv -=-)min(⎩⎨⎧≥-≥-0X bAX （两边同取负号）z CX v vv max max max )min(==∴=--⎩⎨⎧≥≤0X b AX 二、弱对偶性：若)0(X 是原问题的可行解，)0(Y 是对偶问题的可行解，则存在b Y cX)0()0(≤。

证：)0(X 是原问题的可行解∴有b AX≤)0(已知)0(Y 是对偶问题的可行解，用)0(Y左乘上式得b Y AX Y )0()0()0(≤ 同理c A Y≥)0(，用)0(X 右乘之得)0()0()0(CX AX Y ≥∴b Y AXYCX)0()0()0()0(≤≤,故b Y CX)0()0(≤三、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。

注意：此性质不可逆。

四、可行解是最优解时的性质最优性：设)0(X 是原问题的可行解，)0(Y 是对偶问题的可行解，当b YCX)0()0(=时，)0(X、)0(Y是最优解。

五、对偶定理（强对偶性）：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。

反之，若其一无最优解，则另一也无最优解。

六、互补松弛性：若)0(X、)0(Y分别是原问题和对偶问题的可行解，那么0)0(=s X Y 和0)0(=X Y S ，当且仅当)0(X 、)0(Y 为最优解。

证：设原问题和对偶问题的标准型是CX z =maxYb =ωmin⎩⎨⎧≥=+0,s s X X bX AX⎩⎨⎧≥=-0,ss Y Y CY YA 将s s X AX b Y YA C +=-=,分别代入原问题和对偶问题目标函数得s Y YAX z -=，s YX YAX +=ω若0,0)0()0(==s s X YXY ；则)0()0()0()0(CX AX Y b Y ==由性质4知，)0(X、)0(Y为最优解。

又如果)0(X 、)0(Y 为原问题和对偶问题的最优解，由性质4有b Y AX Y CX )0()0()0()0(==即s sX Y AX Y AX Y X Y AX Y )0()0()0()0()0()0()0()0(+==- ∴必有0,0)0()0(==s s X YXY例2 已知线性规划问题21m ax x x z +=⎪⎩⎪⎨⎧≥≤-+-≤++-0,,122321321321x x x x x x x x x试用对偶理论证明上述线性规划问题无最优解。

证：原问题存在可行解，如TX )0,0,0(=上述问题的对偶问题为212m in y y +=ω⎪⎪⎩⎪⎪⎨⎧≥≥-≥+≥--0,011221212121y y y y y y y y 由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。

七、对偶问题的经济解释----影子价格由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有m m b y b y b y b Y cX z )0(2)0(21)0(1)0()0(+++===求z 对b 的偏导数得：)0(2)0(21)0(1mm b z y b z y b z y∂∂=∂∂=∂∂=，，，即i i b z y ∂∂=**其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。

iy 的值代表对第i 种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。

影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。

可见，影子价格对市场有调节作用。

§3 对偶单纯形法一、基本思路对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。

首先讨论这样一个问题：设原问题：0,;max ≥≤=X b AX cX z则其对偶问题：0;;min ≥≥=Y c YA Ybω 化为标准型：0,;;m ax ≥=+=s s X X b X AX cX z0,;;m in ≥=-=s s Y Y c Y YA Yb ω设B 是原问题的一个可行基，于是A=(B|N)，原问题可改写为：N N B B X C X C z +=max⎩⎨⎧≥=++0,,S N B S N B X X X bX NX BX 相应地对偶问题可以表示为minYb=ωmin⎪⎩⎪⎨⎧≥=-=-0,,)2()1(2121S S N S N B S B Y Y Y C Y Y C Y Y这里),(21S S S Y Y Y =1S Y ----对应原问题中基变量BX的剩余变量2S Y ----对应原问题中非变量NX的剩余变量当求得原问题的一个基解bB X B 1-=，其相应的检验数为N BC C BN 1--与1--BC B 。

现分析这些检验数与对偶问题的解之间的关系：令1-=BC Y B 代入(1)、(2)得⎪⎩⎪⎨⎧-=-=-N B C C Y Y B N S S 1210由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：说明：在单纯形表中若在b 列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。

根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即0!≤--j B j p B C C ，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。

方法是：设原问题 CX z =max⎩⎨⎧≥=0X bAX 设B 是一个基，令),,,(21m p p p B =，它对应的变量为Tm B x x x X ),,,(21 =当非基变量都为零时，可以得到b B X B 1-=，若在b B 1-中至少有一个负分量，设0)(1<-i b B ，并且在单纯形表的检验数行中的检验数都为负值，即对偶问题保持可行解，它的各分量是：1.对应基变量m x x x ,,,21 的检验数是m i p B C c i B i i ,,2,1,01 ==-=-σ2.对应非基变量n m m x x x ,,,21 ++的检验数是：n m m j p B C c j B j j ,,2,1,01 ++=≤-=-σ每次迭代是将基变量中的负分量l x 取出，去替换非基变量中的k x ，经基变换，所有检验数仍保持负值，原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。

二．计算步骤(1)列出初始单纯形表，若所有0≥b ，0≤j σ，则停止计算，已得到最优解。

若b 中含有负元素，则需继续计算。

(2)确定换出变量l i i ib B b B b B )(}0)(){(min 111---=<，基变量l x 为换出变量。