第二章 线性规划的对偶理论随着线性规划应用的逐步深入，人们发现线性规划有一个有趣的特性，就是每一个线性规划问题都存在另一个与之配对、两者有密切联系的线性规划问题.称其中一个为原问题，则另一个被称为对偶问题，这个特性称为线性规划的对偶性，这不仅仅是数学上具有的理论问题，由对偶问题引伸出来的对偶解有着重要的经济意义，也是经济学中重要的概念与工具之一. 对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果.§1 对偶问题的提出一、对偶问题的实例在第一章的例1.1中，讨论了某工厂资源的合理利用问题，建立了LP 问题模型： 2125001500max x x z += s.t. 2123x x +≤65 212x x +≤4023x ≤75 （2.1） 21,x x ≥0已知最优解为：70000,25,5**2*1===z x x .现从另一个角度考虑这个问题.假定该厂的决策者考虑自己不生产甲、乙两种产品，而把原拟用于生产这两种产品的资源A,B,C 全部出售给外单位，则应如何确定这三种资源的价格.显然，该厂的决策者要考虑两个原则：第一，每种资源所收回的费用应不低于自己生产时可获得的利润；第二，定价不能太高，要对方容易接受.设321,,y y y 分别表示三种资源出售的价格，则由第一个原则，应有如下约束条件： 2123y y +≥1500 32132y y y ++≥2500 321,,y y y ≥0而把原拟用于生产甲、乙产品的三种资源全部售出，总收入为： 321754065y y y w ++=当然，对厂方而言，w 越大越好，但根据第二个原则，在保证上述条件下，应考虑使总收入即对方的总支出尽可能少才比较合理，因为只有这样，厂方不会吃亏，对方也容易接受.于是，该问题的数学模型归结为：321754065min y y y w ++= s.t. 2123y y +≥150032132y y y ++≥2500 （2.2） 321,,y y y ≥0这也是一个LP 问题，用单纯形法解之得最优解为：500,0,500*3*2*1===y y y及相应的目标函数最优值 *w =70000.如果称（2.1）给出的LP 问题为原问题，则称（2.2）式为（2.1）式的对偶问题.二、对偶问题的形式以上从一个资源利用问题，引出了对资源的估价问题，得到了对偶规划.原问题与其对偶问题之间通常有三种不同的关系形式，以下将原问题记作（P ）问题，对偶问题记作（D ）问题.1、对称型对偶问题 定义2.1 设原LP 问题为n n x c x c x c z +++= 2211max s.t. n n x a x a x a 1212111+++ ≤1bn n x a x a x a 2222121+++ ≤2b （2.3） ………………n m n m m x a x a x a +++ 2211≤m b j x ≥0 （n j ,,2,1 =） 则称下列LP 问题m m y b y b y b w +++= 2211min s.t. m m y a y a y a 1212111+++ ≤1cm m y a y a y a 2222121+++ ≤2c （2.4） ………………m m n n n y a y a y a +++ 2211≤n c i y ≥0 （m i ,,2,1 =）为其对偶问题.其中i y （m i ,,2,1 =）称为对偶变量，并称（2.3），（2.4）为一对对称型对偶问题.如果用矩阵形式来表示模型（2.3），（2.4），则可更清楚地看出两者之间的对称性. cx z =max（P ） s.t. Ax ≤b （2.5） x ≥0 yb w =min（D ） s.t. yA ≤c （2.6） y ≥0其中),,,(21m y y y y =是一行向量.即（P ）问题求极大化，（D ）问题求极小化；（P ）的约束为“≤”，（D ）的约束为“≥”；（P ）的价值系数c ，在（D ）中成为约束右端项；（P ）的约束右端项b ，在（D ）中恰好价值系数；在（P ）中，约束方程左端为Ax ，而在（D ）中，约束方程左端为yA ，决策变量x 、对偶变量y 都是非负的.例2.1 写出（P ）问题321432max x x x z +-= s.t. 321532x x x -+≥2 32173x x x ++≤3 32164x x x ++-≥5 j x ≥0 （ j = 1,2,3） 的（D ）问题.解：首先将问题化为式（2.3）的形式：321432max x x x z +-= s.t. 321532x x x +--≤－2 32173x x x ++≤3 32164x x x --≤－5 j x ≥0 （ j = 1,2,3） 再根据定义2.1，写出其（D ）问题：321532min y y y w -+-= s.t. 32132y y y ++-≥2 32143y y y -+-≥－3 321675y y y -+≥4 i y ≥0 （i = 1,2,3） 2、非对称型对偶问题如果原问题是LP 问题的标准形式，则其对偶问题形式是怎样呢？记（P ）问题为cx z =maxs.t. Ax =b （2.7） x ≥0为了利用对称型（D ）问题的结论，先将问题（2.7）等价地化为：cx z =max s.t. Ax ≤b Ax -≤－b x ≥0再引入对偶向量（u ,v ），其中),,,(21m u u u u =为对应于第一组不等式约束Ax ≤b 的对偶变量，),,,(21m v v v v =为对应于第二组不等式约束Ax -≤－b 的对偶变量，按对称型的结论，可写出其（D ）问题为：⎪⎪⎭⎫⎝⎛-=b b v u w ),(min s.t. ⎪⎪⎭⎫⎝⎛-A A v u ),(≥c u ,v ≥0 即 b v u w )(min -= s.t. A v u )(-≥c u ,v ≥0令 v u y -=为m 维行向量，则以上模型又可写成： yb w =mins.t. yA ≥ c （2.8） y 无符号限制将问题（2.7）与问题（2.8）称为一对非对称型的对偶问题.要注意的是：（P ）问题（2.7）中约束为等式，则其（D ）问题（2.8）中对偶变量无符号限制.例2.2 写出（P ）问题32123max x x x z --= s.t. 6323321=-+x x x 42321=+-x x x j x ≥0 （ j = 1,2,3） 的（D ）问题.解：由式（2.8）知其（D ）问题为 214min y by w += s.t. 213y y +≥3 2122y y -≥－1 213y y +-≥－2 21,y y 无符号限制 3、混合型对偶问题 考虑更一般的LP 问题:2211max x c x c z += s.t. 212111x A x A +≤1b2222121b x A x A =+ （2.9） 232131x A x A +≥3b1x ≥0，2x 无符号限制其中ij A 为j i xn m 矩阵，i b 为i m 维列向量，j c 为j n 维行向量，j x 为j n 维列向量，i = 1,2,3；j = 1,2，且m m m m =++321，n n n =+21.为利用非对称型（D ）问题的结论，令22212x x x -=0,2221≥x x ，引入松弛变量 t s x x ,，其中t s x x ,分别为 31,m m 维列向量. 将问题（2.9）化为标准形式：)(max 2221211x x c x c z -+=s.t. 1222112111)(b x I x x A x A s s =+-+ 2222122121)(b x x A x A =-+3222132131)(b x I x x A x A t t =--+ t s x x x x x ,,,,22211≥0再按式（2.8）写出它的（D ）问题为332211min y b y b y b w ++= s.t. 313212111A y A y A y ++≥1c 323222121A y A y A y ++≥2c 333222121A y A y A y ---≥－2c s I y 1≥0， t I y 3-≥0 即 332211min y b y b y b w ++= s.t. 313212111A y A y A y ++≥1c323222121A y A y A y ++=2c （2.10） 1y ≥0，2y 无符号限制，3y ≤0将问题（2.9）与问题（2.10）称为一对混合型对偶问题.从以上三种形式的对偶关系中，可以总结（P ）问题与（D ）问题相关数据之间的联系，即对偶规则见表2-1.显然，有了对偶规则表2-1，则上述任一形式的问题的对偶问题都可以直接利用表2-1得到.例2.3 写出（P ）问题43212max x z += s.t. 4321234x x x x +-+≥5421723x x x +-≤4 64324321=++-x x x x 1x ≤0，32,x x ≥0，4x 无符号限制 的（D ）问题.解：根据对偶规划表2-1，可直接写出上述（P ）问题的（D ）问题. 321645min y y y w ++= s.t. 321234y y y -+≤2 32132y y y +-≥3 3143y y +-≥－5 172321=++y y y1y ≤0，2y ≥0，3y 无符号限制§2 对偶问题的基本性质这一节给出对偶问题的一些性质，为叙述方便，仅在对称形式下即对（P ）问题：（D ）问题： cx z =max yb w =min s.t. Ax ≤ bs.t. yA ≥ cx ≥ 0y ≥ 0讨论.对其它形式的对偶问题也有类似结论，请读者给出并加以证明.一、对偶规划的若干问题定理2.1（对称性定理） 对偶问题的对偶是原问题. 证明： 先将（D ）问题化成原问题形式 TT y b w )('max -= s.t. T T y A )(-≤Tc - Ty ≥0由定义2.1设Tx 为它的对偶变量，写出它的对偶问题.)('min T T c x z -=s.t. )(T T A x -≥Tb -Tx ≥0即 cx z =max s.t. Ax ≤b x ≥0这就是（P ）问题. 证毕. 根据对称性定理，在一对对偶问题中，可以把其中任何一个称为原问题，则另一个称为其对偶问题.定理2.2（弱对偶定理） 设0x 和0y 分别是（P ）问题和（D ）问题的可行解，则必有0cx ≤b y 0.证明： 因为0x 是（P ）问题的可行解，故必有0Ax ≤b ，0x ≥0 （2.11）又0y 是（D ）问题的可行解，于是有A y 0≥ c ，0y ≥0 （2.12） 用0y 左乘不等式（2.11）两边，得 00Ax y ≤b y 0 用0x 右乘不等式（2.12）两边，得 00Ax y ≥0cx从而有 0cx ≤b y 0 证毕. 推论2.1 如果*x 和*y 分别是（P ）问题和（D ）问题的可行解，且*cx =b y *，则*x 、*y 分别是（P ）问题和（D ）问题的最优解.证明： 由定理2.2知，对于（P ）问题的任意一个可行解x ，必有 cx ≤b y *但*cx =b y *，故对（P ）问题的所有可行，有 cx ≤*cx 由定义知，*x 为（P ）问题的最优解.同理可证，*y 是（D ）问题的最优解. 证毕. 推论2.2 在一对对偶问题中，如果其中一个问题可行，但目标函数无界，则为另一个问题不可行.证明： 用反证法.设（P ）问题可行，但目标函数无界，而（D ）问题可行，即存在可行解0y ，则由定理2知对（P ）问题的任一可行解x 有 cx ≤b y 0即 （P ）问题的目标函数有上界，与条件矛盾. 证毕. 注意推论2.2的逆命题不一定成立，当（P ）问题（（D ）问题）无可行解时，其（D ）问题（（P ）问题）或具有无界解或无可行解.推论2.3 如果一对对偶问题都有可行解，则它们都有最优解.证明： 设0x 、0y 分别是（P ）问题与（D ）问题的可行解，对（P ）问题的任一可行解x ，由定理2.2知，必有cx ≤b y 0，即对于求极大值（P ）问题，目标函数值有上界，故必有最优解，同理，对（D ）问题的任一可行解y 有0cx ≤yb ，即对于求极小值的（D ）问题，目标函数值有下界，故必有最优解. 证毕.定理2.3（对偶定理） 如果（P ）问题（（D ）问题）有最优解，那么（D ）问题（（P ）问题）也有最优解，且目标函数值相等.证明： 先证明当（P ）问题有最优解时，（D ）问题也有最优解.设 *x 是（P ）问题的最优解，它对应的基矩阵为B ，引入松弛变量T m n n n s x x x x ),,,(21+++= ，将（P ）问题化为标准形式s ox cx z +=max s.t. b Ix Ax s =+ s x x ,≥0显然，该问题也有最优解 ⎪⎪⎭⎫ ⎝⎛=***s x x x由第一章定理1.7（最优性判别定理）必有检验数 ),(),,(1I A B c o c B -=σ≤0 令1*-=B c y B ，则有),(**y A y c --≤0， 即 A y *≥c *y ≥0.这表明1*-=B c y B 是（D ）问题的可行解，对应的目标函数值为： b B c b y w B 1**-==又因为*x 是（P ）问题的最优解，其目标函数的值为 b B c cx z B 1**-== 所以有 b y b B c cx B *1*==-.则由推论2.1知（D ）问题有最优解，且两者的目标函数的最优值相等.同理可证，当（D ）问题有最优解时，（P ）问题也有最优解且目标函数相等. 证毕. 推论2.4（单纯形乘子定理） 如果（P ）问题有最优解，最优基为B ，则1*-=B c y B 就是（D ）问题的一个最优解.证明： 由定理2.3的证明过程，已得到此推论的结论.推论 2.5 对于对称形式的（P ）问题，如果有最优解，则在其最优单纯形表中，松弛变量m n n n x x x +++,,,21 的检验数),,,(21m n n n +++σσσ 的负值即为（D ）问题的一个最优解.证明： 当（P ）问题取得最优解时，有),,,(),,,(),,,(2112121m n n n B m n n n m n n n P P P B c c c c +++-++++++-= σσσ 已知 021====+++m n n n c c c ，I P P P m n n n =+++),,,(21如果记 ),,,(**2*11*m B y y y B c y ==-则 **21)0,,0,0(),,,(y I y m n n n -=-=+++ σσσ 式 ),,,(21*m n n n y +++---=σσσ由推论2.4可知，*y 是（D ）问题的一个最优解. 证毕.在矩阵形式的最优单纯形表上更能清楚地得到推论2.5的结论.设松弛变量为初始可行基对应的基变量，B 为最优基，表2-2表示（P ）问题的初始单纯形表，表2-3表示（P ）问题的最优单纯形表.在表2-3中，还可以看到在约束方程的系数矩阵中，松弛变量对应的m ×m 子矩阵中，记录了最优基矩阵B 的逆矩阵1-B ，它在灵敏度分析中是很有用的.综上所述，（P ）问题与（D ）问题的解之间只有以下三种可能的关系：（1）两个问题都有可行解，从而都有最优解，分别设为**,y x ，则必有****w b y cx z ===； （2）一个问题为无界解，另一个问题必无可行解； （3）两个问题都无可行解.定理2.4（互补松弛定理） 设*x 和*y 分别是（P ）问题和（D ）问题的可行解，则它们分别是（P ）、（D ）问题的最优解的充要条件是：0)(**=-Ax b y ；0)(**=-x c A y 同时成立.证明： 必要性 设*x 、*y 分别是（P ）问题和（D ）问题的最优解. 则 *Ax ≤b ，*x ≥0； A y *≥c ， *y ≥0；b y cx **=， 所以由 *cx ≤**Ax y ≤b y *推出*cx =**Ax y =b y *，于是 0)(**=-Ax b y ，0)(**=-x c A y 充分性 由0)(**=-Ax b y ，0)(**=-x c A y 得 *cx =**Ax y =b y *又*x 、*y 分别是（P ）问题和（D ）问题的可行解，所以*x 、*y 分别是（P ）问题和（D ）问题的最优解. 证毕.因为，*y ≥0，*Ax ≤b ，由0)(**=-Ax b y ，有 0)(1*=-∑=nj jiji ix a b y ，i = 1,2,…, m由*x ≥0，A y *≥c ，0)(**=-x c A y ，有 0)(1=-∑=j mi j i ijx c y a，j = 1,2,…, n即一个规划的某个约束成立严格不等式（约束条件为松），对应的对偶规划中变量取0（变量是紧），当某个变量不为0时（变量是松），对应的对偶规划中约束成立等式（约束条件是紧）.二、对偶规划的求解对偶规划作为一个线性规划，自然可以用前面介绍的单纯形法求解. 但是，由本节关于对偶规划的若干定理的讨论，可以看到原问题及其对偶问题之间有着紧密的联系，那么，能否通过求解原问题找出对偶问题的解，或者相反，在此介绍两种求对偶最优解的方法.1、利用原问题的最优单纯形表求对偶最优解的方法由推论2.4已得到1*-=B c y B 是（D ）问题的一个最优解，又由推论2.5在对称形式的（P ）问题，如果有最优解，则在其最优单纯形表中，松弛变量m n n n x x x +++,,,21 的检验数),,,(21m n n n +++σσσ 的负值即为（D ）问题的一个最优解，见表2-3，所以，对对称形式的对偶问题，当用单纯形法求得（P ）问题的最优解的同时，得到了（D ）问题的最优解.例2.4 求如下LP 问题321734max x x x z ++= s.t. 32122x x x ++≤100 32133x x x ++≤100 321,,x x x ≥0 的对偶问题的最优解.解: 对偶问题为 21100100min y y w += s.t. 213y y +≥4 212y y +≥3 2132y y +≥721,y y ≥0对原问题引入松弛变量54,x x ，将原问题化为标准形式，由单纯形法求解得最优单纯形表（表2-4）.则原问题的最优解为： Tx )25,25,0(*= 其相应的目标函数最优值 250*=z由推论2.5，在表2-4中可得，对偶问题的最优解为：)2,21(*=y 其相应的目标函数最优值 250*=w .如果（P ）问题为： cx z =max s.t. b Ax = x ≥0此时矩阵A 中没有现成的单位矩阵I ，但可以通过引进人工变量，使之出现单位矩阵，再用大M 法或两阶段法求解（结果保留所有人工变量位置），那么，这时如何从最优单纯形表中，求得对偶规划的解？设 I 为初始可行基，对应的基变量I x 在目标函数中的系数向量为I c ，B 为最优基，参考 表2-3,在最优单纯形表中,I x 对应的检验数为1--=B c c B I I σ,因此1*-=-=B c c y B I I σ.例2.5 （第一章例1.10）已知（P ）问题 3213max x x x z --= s.t. 3212x x x +-≤11 32124x x x ++-≥3 1231=+-x x 321,,x x x ≥0 试求其（D ）问题的最优解.解：该问题的（D ）问题为321311min y y y w ++=s.t. 32124y y y --≥3 212y y +-≥-1 3212y y y ++≥-11y ≥0，2y ≤0，3y 无符号限制对（P ）问题，在第一章例1.10中，引进松弛变量54,x x ，人工变量76,x x ，用大M 法已解得（见表1.9）T x )9,1,4(*=，2*=z .在表1-9 Ⅳ 的检验数行中，可以看到初始基变量764,,x x x 对应的检验数为 314-=σ，M -=316σ，M -=327σ， 而764,,x x x 在原问题的目标函数中相应的系数分别为0,-M ,-M ，故（D ）问题的最优解为：31)31(004*1=--=-=σy ； 31)31(6*2-=---=--=M M M y σ；32)32(7*3-=---=--=M M M y σ，即对偶问题的最优解为：)32,31,31(*--=y其相应的目标函数最优值 2*=w .2、利用互补松弛定理求对偶最优解. 通过例子来介绍此方法. 例2.6 已知（P ）问题2134max x x z += s.t. 212x x +≤2 212x x -≤3 2132x x +≤5 21x x +≤2 213x x +≤3 21,x x ≥0 试求其（D ）问题的最优解.解：该问题的（D ）问题为5432132532min y y y y y w ++++= s.t. 5432132y y y y y ++++≥4 54321322y y y y y +++-≥3 54321,,,,y y y y y ≥0由于（P ）问题只含两个决策变量，故可用图解法求解，得最优解为：)53,54(*=x其相应的目标函数最优值 5*=z .将*x 代入约束条件，知第2、3、4个约束条件成立严格不等式，由互补松弛定理，对偶规划最优解中相应的变量有 0*4*3*2===y y y ，又因为*2*1,x x 不为0，在对偶规划中对应的约束条件为紧，因此，得到43*5*1=+y y ，32*5*1=+y y ，解得1*5*1==y y ，故（D ）问题的最优解为：)1,0,0,0,1(*=y 其相应的目标函数最优值 5*=w .注意：从前面的讨论可知，原问题与对偶问题是对称的，即互为对偶问题. 求解一个有m 个约束条件n 个变量的LP 问题，可以转化为求解一个有n 个约束条件m 个变量的对偶问题. 因此在求解一个LP 问题时，往往需要先考虑一下，究竟是解它的原问题还是解它的对偶问题比较省事，一般来说，求解一个LP 问题的计算量，是同这个问题所包含约束条件的个数有密切关系的，如果约束条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地迭代变换的计算量也愈大，根据经验，单纯形法的迭代次数大约是约束条件个数的1～1.5倍，因此，当m < n 时，用原问题求解较好；当m > n 时，则用其对偶问题求解较好. 但当m=2时，对偶问题可用图解法求解，可简化求解过程.例2.7 求解LP 问题4321342min x x x x z --+= s.t. 432122x x x x ++-≤2 43212x x x x +-+≥0 21,x x ≥0，43,x x ≤0 解： 对偶规划为2132max y y w += s.t. 21y y +≤2 212y y +-≤4 212y y -≥-3 212y y +≥-1 1y ≤0，2y ≥0 用图解法解之，得：)2,0(*=y ，6*=w .将*y 代入约束条件，第3、4个条件成立严格不等式，所以，0*4*3==x x ，又因为*2y ＞0，所以原规划第二个约束条件为等式约束，即：⎩⎨⎧=+≤-322*2*1*2*1x x x x 此时，原规划最优解不唯一，由上述不等式组得：23*2≤x ， 31*2≥x 所以，原规划有两个最优基可行解.T x )0,0,31,37(*=, )0,0,23,0('*=x原规划的最优解为：')1(**x x λ-+λ，其中0≤λ≤1，相应的目标函数最优值 6*=z .§3 对偶问题的经济解释——影子价格一、影子价格的概念 考虑一对对称的对偶问题. cx z =max yb w =min （P ） s.t. Ax ≤ b （D ） s.t. yA ≥ cx ≥ 0y ≥ 0从上节对偶问题的基本性质可知，当（P ）问题求得最优解*x 时，其（D ）问题也得到最优解*y ，且有*11***w yb xc z nj mi ii j j ===∑∑== （2.13）i b 代表第i 种资源的拥有量；对偶变量*i y 的意义代表在资源最优利用条件下对单位第i 种资源的估价.这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，称之为影子价格.资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数.由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变.不同企业，即使是相同的资源，其影子价格也不一定相同，就是同一个企业，在不同的生产周期，资源的影子价格也不完全一样.在（2.13）式中对z 求i b 的偏导数，得**iy b z =∂∂，这说明*i y 的值相当于在资源得到最优利用的生产条件下，i b z 的增量，所以，影子价格是一种边际价格例2.8 用线性规划来确定最优的产量方案.三种资源的单位消耗及资源的现有数量如表用单纯形法解这个LP 表（表2-6）.这说明最优生产方案为甲产品生产35件，乙产品生产10件，总产值达到最大为215.由上节讨论，在最优单纯形表中，不难得到对偶解，即影子价格：资源A 的影子价格01=y ；资源B 的影子价格12=y ；资源C 的影子价格33=y .资源A 的影子价格为零，说明增加这种资源不会增加总的产值，如在表2-6的初始表中的90改为91，则最优单纯形表为表2-7Ⅰ，这说明资源A 的增加不改变产品生产方案，也不增加总的产值.如果资源C 增加一个单位从45改为46，最优单纯形表为表2-7（Ⅱ）.这说明增加一个单位的资源C 以后， 最优生产方案为甲产品生产34件，乙产 品生产12件，总产值由原来215件增加 到218，增加了3个单位，即为该资源 的影子价格格或边际价格.由上节，对偶问题的互补松弛定理中有∑=<nj i jij b xa 1*时，0*=i y ；当0*>i y 时，有∑==nj i jij b xa 1*，这表明生产过程中，如果某种资源i b 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕.二、影子价格在经营管理中的应用影子价格在经营管理中的用处很多，可提供以下几个方面的信息.1、影子价格说明增加哪一种资源对增加经济效益最有利.如例2.8中的三种资源的影子价格为（0,1,3），说明首先应考虑增加资源C ，因为相比之下它能给收益带来的增加最大.2、影子价格又是一种机会成本. 企业经营决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当年i 种资源的影子价格高于市场价格时，则企业可以买进该种资源；而当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润.3、企业在新产品投产之前，可利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产.如在例2.8中，企业要生产一新产品，单件消耗三种资源的数量是（2,3,2）单位，则新产品的定价一定要大于9232)310(=⎪⎪⎪⎭⎫⎝⎛，才能增加公司的收益，如果售价低于9的话，生产是不合算的.4、利用影子价格分析现有产品价格变动时资源紧缺情况的影响，如在例2.8中，产品的售价不是（5,4），而是（5,5），则从最优单纯形表中，可计算出影子价格)500(210110521)550(=⎪⎪⎪⎭⎫⎝⎛---这说明如果产品乙的价格增加的话，资源C 将变得更紧俏了.5、利用影子价格可以帮助分析工艺改变后对资源节约的收益. 如在例2.8中，工艺过程改进后，使资源C 能节约2%，则带来的经济收益将是3×45×2%=2.7.值得指出的是，以上的分析都是在最优基不变的条件下进行的，如果最优基有变化，则应结合§5灵敏度分析的方法进行分析.正是由于影子价格在经济管理中对收益能提供大量的信息，所以对偶理论中的影子价格概念正日益受到管理人员的重视.影子价格虽然被定义为一种价格，但是还应对它有更为广义的理解，影子价格是针对约束条件而言的，并不是所有的约束条件都代表了资源的约束，如在例2.8中，还可以列入一个产量约束：两种产品的数量不超过市场上的需要量，这样的约束也有个影子价格，如果这个影子价格算出来比前面几种影子价格更大，则应理解为扩大销售量能比增加资源带来更大的经济效益.§4 对偶单纯形法一、对偶单纯形法的基本思路对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解线性规划问题的一种方法（而不能简单的将它理解为是求解对偶问题的方法），前面介绍的单纯形法可称为原始单纯形法.从理论上说原始单纯形法，可以解决一切线性规划问题，但正因为它适用范围广泛，必有不足之处，如它对于某些特殊问题，虽然也可解决，但计算量较大.例如线性规划问题cx z =max 化为标准形式 cx z -='max s.t. Ax ≥b s.t. b x Ax s =- x ≥0 s x x ,≥0在约束方程中出现了一个负单位矩阵，若将剩余变量s x 取作初始基变量，则初始基m m n n n I P P P B -==+++),,,(210 ，初始解b b I b B x m B -=-==-10)(0≤0不满足可行性.因此不能将m I -取作初始基，为了求得初始基本可行解，在第一章§6中已讲述，需在约束方程左边增加一组人工变量，通过大M 法或两阶段法进行计算，这就显得很不方便，且（m I -）也没能利用上.考察一般的标准形式的线性规划问题及其对偶问题：cx z =max yb w =min （P ） s.t. Ax=b （D ） s.t. yA ≥c x ≥0 y 无符号限制 设B 为原问题（P ）的一个基，不妨设 ),,,(21m P P P B = 则 ⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=-01)0(b B x x xN B （2.14）为原问题（P ）的一个基本解；且当b B x B 1-=≥0 （2.15） 时，则)0(x 为一个基可行解，B 为可行基；进一步若检验数满足A B c c B 1--=σ≤0 （2.16） 则)0(x为原问题（P ）的一个最优解，这时B 称为最优基.以上概念都是对原问题（P ）而言的，因此，我们更将条件（2.15）称为原始可行性条件；条件（2.16）称为原始最优性条件.原始单纯形法的基本思路是：从满足原始可行性条件（2.15）的一个基可行解出发，经过换基运算迭代到另一个基可行解，即总是保持解的可行性不变（满足条件（2.15）），变化的只是检验数向量σ，它从不满足σ≤0，逐步迭代到σ≤0成立，一旦达到σ≤0，也就得到了原问题的最优解.再从对偶的观点来解释这个问题，令1-=B c y B 代入式（2.16）得yA ≥c （2.17）即y 是对偶问题（D ）的一个可行解.条件（2.17）称为对偶可行性条件，即原始最优性条件（2.16）与对偶可行性条件（2.17）是等价的，因此，如果一个原始可行基B 是原问题（P ）的最优基，则1-=B c y B 就是对偶问题（D ）的一个可行解，此时对应的目标函数值1-==B c yb w B ，等于原问题（P ）的目标函数值，可知1-=B c y B 也是对偶问题（D ）的最优解.定义2.2 若原问题（P ）的一个基本解⎪⎪⎭⎫⎝⎛=-01b B x 对应的检验数向量满足条件（2.16）， 即）（N B c c B N N B 1,0),(--==σσσ≤0 则称x 为（P ）的一个正则解.于是可知，原问题（P ）的正则解x 与对偶问题（D ）的可行解y 是一一对应的，它们由同一个基B 所决定，我们称这一基为正则基.因此，我们可以设想另一条求解思路，即在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件，也就达到了最优解.也即在保持正则解的正则性不变条件下，在迭代过程中，使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解.这正是对偶单纯形法的思路，这个方法并不需要把原问题化为对偶问题，利用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进行运算.二、对偶单纯形法的计算步骤 求解如下标准形式线性规划问题： cx z =max s.t. Ax = b x ≥0 对偶单纯形法的计算步骤：（1）找一个正则基B 和初始正则解)0(x；将原问题化为关于基B （不妨设),,,(21m P P P B =）的典式，列初始对偶单纯形表，见表2-8.（2）若b B b 1'-=≥0，则停止计算，当前的正则解b B x 1-=，即为原问题的最优解；否则转下一步.（3）确定离（换出）基变量：令 {}m i b b i r ≤≤=1|'min '，（显然0'<r b ） 则取相应的变量，r x 为离（换出）基变量.（4）若rj a '≥0，（j = 1,2,…, n ），则停止计算，原问题无可行解.否则转下一步.（5）确定进（换入）基变量；若rkk rj rjja n j a a '1,0'|'min σσθ=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧≤≤<=，则取相应的变量k x 为进（换入）基变量.（6）以rk a '为主元进行换基运算，得到新的正则解，转（2）. 例2.9 用对偶单纯形法求解32111515min x x x z ++= s.t. 321223x x x ++≥532125x x x ++≥4321,,x x x ≥0解：先将问题化为32111515'max x x x z ---= s.t. 52234321-=+---x x x x 4255321-=+---x x x x j x ≥0 （j = 1～5） 其中54,x x 为松弛变量，取初始正则基254),(I P P B ==则问题已化为关于基B 的典式，初始正则解为：T x )4,5,0,0,0()0(--= 及目标函数值0)0(=z.列对偶单纯形表并进行迭代见表2-9，由表2-9（Ⅰ）可知，因为 {}54,5min -=- 故应取4x 为换出基变量，又因为5.2211,25,315min =⎭⎬⎫⎩⎨⎧------=θ 故应取2x 为换入基变量，以212-=a 为主元作换基运算，得表2-9（Ⅱ），又由该表可知.因为 2323,25min -=⎭⎬⎫⎩⎨⎧- 故应取5x 为换出基变量，又因为7152125,16,22215min =⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧------=θ故应取1x 为换入基变量，以27'21-=a 为主元作换基运算，得表2-9(Ⅲ)，至此，基变量的取值已全部非负，检验已全部非正，故已求得最优解T x )0,0,0,713,73(*=及相应的目标函数最优值7110'*-=z ，原问题的目标函数最优值7110*=z . 由表2-9(Ⅲ)还可以看出，其对偶问题的最优解为)715,710(*=y及目标函数最优值7110*=w .例2.10 用对偶单纯形法求解321642min x x x z ++=s.t. 3212x x x +-≥1032122x x x ++≤ 322x x -≥ j x ≥0，（j = 1,2,3）.解：先将问题化为:321642'max x x x z ---= s.t. 1024321-=+-+-x x x x 12225321=+++x x x x42632-=++-x x x j x ≥0，j = 1,2,…,6其中654,,x x x 正则基3654),,(I P P P B == 则问题已代为关于基B 始正则解为：T x )4,12,10,0,0,0()0(--=及标函数值0')0(=z .用对偶单纯形法求解、迭代过程如表2-10.由表2-10（Ⅲ）可知，基变量的取值已全部非负，检验数已全部非正，故已求得最优解:T x )0,2,0,0,2,6(*=及原问题目标函数最优值20*=z .从以上求解过程可以看到，对偶单纯形法有以下优点：（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此，可以简化计算；（2）当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此，对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解；（3）在灵敏度分析中，有时需要用对偶单纯形法，这样可以使问题的处理简便.对偶单纯形法要求初始解满足正则性（对偶可行性），而对大多数线性规划问题，这个条件得不到满足，这时，需通过引入人工约束构造一个扩充问题（有兴趣的读者可查阅有关书籍），但这样可能使问题求解变繁，这是对偶单纯形法的局限性.后面介绍的交替单纯形法是对此的一个弥补.对偶单纯形法与原始单纯形法的计算步骤类似，但又有所不同，其内在的对应关系可归结为表2-11之中.三、交替单纯形法 例2.11 求解如下LP 问题2163max x x z += s.t. 212x x +≥6 213x x + ≥9 2157x x +≤35 21,x x ≥0 解：引进松弛变量543,,x x x ，得2163max x x z +=s.t. 62321-=+--x x x 93421-=+--x x x 3557521=++x x x j x ≥0，j = 1,2,…,5 初始基本解：T x )35,9,6,0,0()0(--=此解既非原始可行，又非对偶可行.建立表2-12（Ⅰ），第一次用单纯形法迭代，第二次用对偶单纯形法迭代，得最优解：T x )0,0,423,421,45(*=及相应的目标函数最优值：。
