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

1、第三章线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质；2、对偶单纯形法；3、灵敏度分析。重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方 法。要求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。 1对偶问题的对称形式一、对偶问题弓侧，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A、B两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？甲乙设备128台时原材料A401

2、6kg原材料B0412kg解：设 Xi、X2 分别为甲、乙两种产品的产量则目标函数maxz 二 2x3x2x2x2 岂 8i4x1- 16i4x2 兰 12约束条件-x1,x 0(1)不再生产甲、乙产品，而将其出租或出售 3分别为出租单位设备台时的租金和出让单位原材料这时要考虑每种资源的定价问题，设A、B的附加额。作一比较：若用一个单位台时和 4个单位原材料 A生产一件产品甲，可获利 2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。即:y 4y 2同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。即:2力 4y33将工

3、厂所有设备台时和资源都出租和出让，其收入为。=8y + 16y2 + 12y3对工厂来说，越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足所有产品的利润前提下, 使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：min =8y116y212y3+4丫2工 2 0 , j =1,2,3我们就称（2）为模型（1）的对偶问题。一般地，设原问题为max z = c/ c2x2 c xnaiiXi +ai2X2 + +amXn 兰 ba2lXl +a22X2 +八 +a2nXn 兰 b2aaaasamiXi +am2X2 +*amnXn 兰 *Xj _0 , j =i,2, ,n则其对

4、偶问题为：min 二 by b?y2nNiyi +a22 + +amiym Aai2yi +a22y2 *+am2ym C2m-a-07 0、原问题与对偶问题的关系原问题（或对偶问题）对偶问题（或原问题）目标函数 max z目标函数mi neo变n个0n个约束量0无约束条=件约m个束件=m个变052x1+2x3 x4 兰 41x2 +x3 + x4 =6捲 _ 0, x2, x3 - 0, x4无约束解：max = 5y! 4y2 6y3 +2y23 2yi*3 兰 3 3% +2y? +y3 兰 一5yi -丫2*3=1yi -02空0小无约束 2对偶问题的基本性质、对称性：对偶问题的对偶是

5、原问题。证：设原问题为max z 二 cXiX 0则其对偶问题为：mi n = YbYA_ Ciy 0对上式两边取负号，得-min二-YbYA C1y0-max(-代)=minwmax(-)=_Yb-YA-JCY -0上式的对偶问题为min(v)=CX-AXJ-bX-0(两边同取负号)-min(- v)二 maxv maxv 二 CX 二 maxzAX bX 0(0)(0)cX (0) ： Y()b二、弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则存在CX 一丫 b。(0)证：X是原问题的可行解已知Y(0)是对偶问题的可行解，用Y(0)左乘上式得 Y (0)AX(0)二 Y(0)b同

6、理Y(0)A C，用 X(0)右乘之得 丫(0)AX(0) 一 CX(0)CX(0) Y(0)AX(0) 丫b,故CX(0X Y(0)b三、无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。注意：此性质不可逆。(0) (0)四、 可行解是最优解时的性质最优性：设 X是原问题的可行解，Y是对偶问题的可行解，当(0) . (0) (0) (0)CX - 丫 b时，X 、丫是最优解。五、对偶定理(强对偶性)：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。反之，若其一 无最优解，则另一也无最优解。(0) (0) (0)、 六、互补松弛性：若X 、Y分别是原问题和对偶问

7、题的可行解，那么Y Xs二0和(0) (0) YSX0，当且仅当X证：设原问题和对偶问题的标准型是max z CXAX Xs = bX,Xs - 0将 C 二 YA - Ys , b 二 AX(0)Y 为最优解。mi n = YbYA- Ys 二 CY,Ys - 0Xs分别代入原问题和对偶问题目标函数得二 YAX YXs若 YsX(0) = 0, 丫(0)Xs 二 0 ；则 Y(0)b 二 Y (0)AX (0)二 CX(0)(0) (0)由性质4知，X 、 Y为最优解。又如果X (0)、丫(0)为原问题和对偶问题的最优解，由性质4有CX(0) = Y(0)AX(0) = Y(0)b 即Y(0

8、)AX(0) - YsX(0)= 丫AX(0)= Y(0)AX(0) Y(0)Xs必有YsX(0)= 0，丫(0)Xs =0例2已知线性规划问题maxz= xx2捲 + x2 + X3 兰 2 r2x x2 x3 1Xi, X2, X3试用对偶理论证明上述线性规划问题无最优解。证：原问题存在可行解，如(0,0,0)T上述问题的对偶问题为min 二 2yy2-y 2y 1yy2 - 1yi - y 0yi , y 0由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。七、对偶问题的经济解释-影子价格由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有z c

9、X二 丫b 二y10)biy20)b2求z对b的偏导数得:（0）yi：z （0） 石，y2(0)，ymbm*即yi*:zbi其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。i的值代表对第i种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影 子价格”。影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该 资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。可见，影子价格对市场有调节作用。 3对偶单纯形法、基本思路对偶单纯形法是运用对偶原理求解原问题的一种方法

10、，而不是求解对偶问题的单纯形法。 首先讨论这样一个问题：设原问题:maxz= cX; AX 空 b, X - 0则其对偶问题：min=Yb; YA - c; 丫- 0化为标准型：max zcX; AX Xsb;X,Xs 0min 二 Yb; YA 丫眇 c; Y,Ys0设B是原问题的一个可行基，于是 A=(B|N)，原问题可改写为：maxz二 CBXB CNXBXb NXn Xs = b&b,Xn ,Xs = 0相应地对偶问题可以表示为min min 二 YbYb 飞=Cb (1)Yn - Ys = Cn (2)丫,丫0,丫5 - 0这里 Ys = (Yd%)Y$ -对应原问题中基变量 xb的

11、剩余变量Ys2 -对应原问题中非变量Xn的剩余变量当求得原问题的一个基解Xb二Bb，其相应的检验数为Cn 一 CBB 1N与一 CBB 1。现分析这些检验数与对偶问题的解之间的关系：令 Y = CbB， 1代入、(2)得Ys 0飞=Cn CbB 1N由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：XbXnXs0Cn -CbBN-CbBJY1YS2-Y说明：在单纯形表中若在 b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验 数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。根据对偶问题的对称性，可这

12、样考虑：若保持对偶问题的解是基可行解，即Cj -CBBPj乞0，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。方法是：设原问题 maxz=CX；AX =bX艺0设B是一个基，令B =(Ph，P2,Pm)，它对应的变量为Xb =(为公2,Xm)T当非基变量都为零时，可以得到XB =B，b，若在B4b中至少有一个负分量，设 2北)：0，并且在单纯形表的检验数行中的检验数都为负值，即对偶问题保持可行解，它的各分量是：1. 对应基变量x1, x2 / ,xm的检验数是-cCbB4Pi =0, i =1,2, ,m2. 对应非基变量xm 1,xm -2/ ,xn的检验数是：j =

13、Cj -CbB Pj g j 二m 1,m 2, ,n每次迭代是将基变量中的负分量Xl取出，去替换非基变量中的 Xk，经基变换，所有检验数仍保持负值，原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。二计算步骤(1) 列出初始单纯形表，若所有 b 0， j 0，则停止计算，已得到最优解。若b中含有负元素，则需继续计算。确定换出变量叫门( B b)i (B b)i 0,则无可行解，停止计算。若存在 3|j 0,则继续计算。I貯,日 9 = min t 一 按规则，ja,ijIf Io_ka ，非基变量xk为换入变量。lk(4)以 alk为主元素进行取主变换。 例3、用对偶单

14、纯形法求解。min z = 2x3x2 4x3x2x2 x33r2x x2 3x34xi, X2, X3解：化为标准型max z 二 2x0时，b-b/air当A B原材料的消耗。ii1以引例为例，某工厂计划生产甲、乙两种产品，已知生产单位产品所需设备台时及甲乙设备128台时原材料甲4016kg原材料乙0412kg该工厂每生产一件产品甲可获利2元，生产一件乙产品可获利3元，问如何安排生产该工厂获利最多解： maxz =2为 3x2x- +2x2 8Xi,X2分别是甲、乙两种产品的产量2x1164x2 0 ,说明生产丙产品是有利的。（2）计算丙产品在最终表中对应x3的列向量-p3Orl-31 -

15、 -2 6 3*1.JO1 O并将（1）、（2）的计算结果填入最终表:230005CbXbbX1X2X3X4X5x32X14101/41/403/20X400-221/2123X32011/2-1/801/4-1.5-1/81.252X11103/2-1/8-3/405x3200-11/41/213X21.5013/4-3/16-1/80-1/4-7/16-5/8由于b列的数字无变化，原问题的解是可行解，但二3 =1.25 0 ,说明目标函数值还可改善。（3）将X3作为换入变量，X5作为换出变量，进行运算求最优解（见上表）。这时最优解 为=1, X2 = 1.5, X3 = 2 ；总利润为16

16、.5元，比原计划增加了 2.5元。例7、分析原计划生产产品的工艺结构发生变化。在引例中，若原计划生产甲产品的工艺结构有了必改进，这时有关 它的技术系数向量 p； = （2,5,2）T，每件利润4元，试分析对原最优计划有什么影响？解：设改进后的甲产品产量为01/4B -21/21/2 1/8x1，那么对应x；的列向量为1 5 =1/20 一3/8 一025/4检验数G =Ci CbBpI =4 一(5,1/8,0)(2,5,2)丁 = 38将上述结果填入最终表 x1的列向量位置得：43000CbXbbx3X2X3X4X54X145/4001/400X541/20-21/213X223/811/2

17、-1/80aj3/8-3/2-1/84x13.21000.200X52.400-20.413X20.8010.5-0.20aj-1.5-0.23.2单位，生从表中可看出，原问题和对偶问题的解都是可行解，所以表中的结果已是最优解，即应生产甲产品 产乙产品0.8单位,可获利15.2元。注：若原问题和对偶问题均为非可行解时，需要引进人工变量后重新求解。例&增减约束条件的分析。已知下列线性规划问题maxz =9为 8x250x319x43音 +2x2 +10x3 +4x4 兰1812X3十丄4兰3I2Xj 一0 (j =1,2,3,4,)其最终单纯形表：98501900CbXbbX1X2X3X4X5X19X4224/3012/3-10/350X31-1/2-1/310-1/64/3CTj-4-2/3-13/310/3如果在上述问题中增加约束条件4x3x2 5x3 2x4 _ 8试分析对原最优解有何影响？解：将原最优解 X* =(0,0,1,2,0,0)t代入新增约束条件检验：4 0 3 0 5 12 4=13 8须将该约束条件引入单纯形最优表继续迭代。加入松弛变量x7，新增约束条件变为4% +3x2 +5