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

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

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

3、收入应不低于生产一件乙产品的利润。即:2力 4y33第23页第三章线性规划的对偶理论及灵敏度分析将工厂所有设备台时和资源都出租和出让，其收入为。=8y + 16y2 + 12y3对工厂来说，越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足所有产品的利润前提下, 使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：min =8y116y212y3"+4丫2工 2< 2yi +4y 3Jj> 0 , j =1,2,3我们就称（2）为模型（1）的对偶问题。一般地，设原问题为max z = c/ c2x2 c xn'aiiXi +ai2X2 + +amXn

4、 兰 ba2lXl +a22X2 +八 +a2nXn 兰 b2aaaasamiXi +am2X2 +*amnXn 兰 *Xj _0 , j =i,2, ,n则其对偶问题为：min 二 by b?y2nNiyi +a22 + +amiym A"ai2yi +a22y2 *+am2ym ®C2m-a-< ainyi +a2ny2 +amnym ®Cnyi 一0 , i =i,2, ,m矩阵形式：原问题对偶问题max z = cXmi n = Yb'AX Eb,、Ya启C （实际为ATyT CT）X >07 >0、原问题与对偶问题的关系原问题（

5、或对偶问题）对偶问题（或原问题）目标函数 max z目标函数mi neo变n个0n个约>束第24页第三章线性规划的对偶理论及灵敏度分析量<0无约束<条=件约m个束<条>件=m个变>0<0卓量 无约束约束条件右端项 目标函数变量的系数目标函数变量的系数 约束条件的右端项例1求下列问题的对偶问题min z =2x1 3x2 - 5x3 x4x1 +x2 -3x3 +x4 >52x1+2x3 x4 兰 41x2 +x3 + x4 =6捲 _ 0, x2, x3 - 0, x4无约束解：max = 5y! 4y2 6y3» +2y23 2yi*

6、3 兰 3« 3% +2y? +y3 兰 一5yi -丫2*3=1yi -02空0小无约束§ 2对偶问题的基本性质、对称性：对偶问题的对偶是原问题。证：设原问题为max z 二 cXiX 0则其对偶问题为：mi n = YbYA_ Ciy 0对上式两边取负号，得-min二-Yb第25页第三章线性规划的对偶理论及灵敏度分析YA 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

7、(°)b二、弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则存在CX 一丫 b。(0)证：X是原问题的可行解已知Y(0)是对偶问题的可行解，用Y(0)左乘上式得 Y (0)AX(0)二 Y(0)b同理Y(0)A C，用 X(0)右乘之得 丫(0)AX(0) 一 CX(0)第26页第三章线性规划的对偶理论及灵敏度分析CX(0) Y(0)AX(0) 丫b,故CX(0X Y(0)b三、无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。注意：此性质不可逆。(0) (0)四、 可行解是最优解时的性质最优性：设 X是原问题的可行解，Y是对偶问题的可行解，当(0) .

8、(0) (0) (0)CX - 丫 b时，X 、丫是最优解。五、对偶定理(强对偶性)：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。反之，若其一 无最优解，则另一也无最优解。(0) (0) (0)、 六、互补松弛性：若X 、Y分别是原问题和对偶问题的可行解，那么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)

9、= 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)AX(0) - YsX(0)= 丫AX(0)= Y(0)AX(0) Y(0)Xs必有YsX(0)= 0，丫(0)Xs =0例2已知线性规划问题maxz= xx2第27页第三章线性规划的对偶理论及灵敏度分析捲 + x2 + X3 兰 2 r2x< x2 x3 ' 1Xi, X2, X3试用对偶理论证明上述线性规划问题无最优解

10、。证：原问题存在可行解，如(0,0,0)T上述问题的对偶问题为min 二 2yy2-y< 2y 1yy2 - 1yi - y 0yi , y 0由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。七、对偶问题的经济解释-影子价格由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有z cX二 丫b 二y10)biy20)b2求z对b的偏导数得:（0）yi：z （0） 石，y2(0)，ymbm*即yi*:zbi其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。i的值代表对第i种资源的估价，这种估价是针对具体工厂的具体产

11、品而存在的一种特殊价格，称它为“影 子价格”。影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该 资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。可见，影子价格对第28页第三章线性规划的对偶理论及灵敏度分析市场有调节作用。§ 3对偶单纯形法、基本思路对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。 首先讨论这样一个问题：设原问题:maxz= cX; AX 空 b, X - 0则其对偶问题：min=Yb; YA - c; 丫- 0化为标准型：max zcX; AX Xsb;X

12、,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的剩余变量Ys2 -对应原问题中非变量Xn的剩余变量第29页第三章线性规划的对偶理论及灵敏度分析当求得原问题的一个基解Xb二Bb，其相应的检验数为Cn 一 CBB 1N与一 CBB 1。现分析这些检验数与对

13、偶问题的解之间的关系：令 Y = CbB， 1代入、(2)得Ys 0飞=Cn CbB 1N由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：XbXnXs0Cn -CbBN-CbBJY1YS2-Y说明：在单纯形表中若在 b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验 数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即Cj -CBBPj乞0，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。方法是：设原问题 maxz

14、=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 =Cj -CbB Pj g j 二m 1,m 2, ,n每次迭代是将基变量中的负分量Xl取出，去替换非基变量中的 Xk，经基变换，所有检验数仍保持负值，

15、原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。二计算步骤(1) 列出初始单纯形表，若所有 b 0， j ' 0，则停止计算，已得到最优解。若b中含有负元素，则需继续计算。第30页第三章线性规划的对偶理论及灵敏度分析确定换出变量叫门( B b)i (B b)i < 0 = (B b)i，基变量X|为换出变量。(3)确定换入变量检查X|行的系数aj ,若所有aij > 0,则无可行解，停止计算。若存在 3|j <0,则继续计算。I貯,日 9 = min t 一 按"规则，ja,ijIf Io<_ka ，非基变量xk为换入变量。lk

16、(4)以 alk为主元素进行取主变换。 例3、用对偶单纯形法求解。min z = 2x3x2 4x3x2x2 x33r2x< x2 3x34xi, X2, X3解：化为标准型max z 二 2x< 3x2 4x3maxz 二 -2捲 - 3x2 - 4x3 0x4 0x5- 2x2 - x3 兰-3l2xx2 3x3 '4心 X2, X30 Y O Y Y + w 兰 O12342xx2 3x3 x5 '4Xj - 0 ,厂 1,2,5CBXbb-2X1-3X2-4X30X40X50X4-3-1-2-1100X5-4-21-301-2-3-40X4-10-5/21/

17、21-1/2-2X121-1/23/20-1/2-4-1-1-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5-3/5-8/5-1/5从初始表看出，检验数行对应的对偶冋题的解是可行解，进行计算m i 3n 4)(4 取X5为 换 出 变 量- 2 min -I- 2取 Xi 为换入变量。 问题仍是可行解，而 b1 4为换出变量0,进行计算。取第31页第三章线性规划的对偶理论及灵敏度分析45/：-4- 1二 min厂，I- 5/2- 1/2J -取 X2 为换入变量。b问题的0优X*j(01/5,2/5,0,0,0)若求其对偶问题的最优解，则(%,丫2尸(8/5,

18、1/5)三对偶单纯形的优缺点优点：(1)初始解可以是非可行解，当检验数为负数时，就可以进行基的变换，这时不需加入人工变量，因此可 以简化计算；(2) 对变量多于约束条件的线性规划问题，用对偶单纯形法计算可以减少工作量；(3) 在灵敏度分析中，有时用对偶单纯形法，使问题的处理简化。缺点：对大多数线性规划问题，很难找到一个初始可行基，因而这种方法很少单独使用。§ 4灵敏度分析在以前讨论线性规划问题时，假定aq ,b, Cj都是常数。但实际上这些系数往往是估计值。如果市场条件一变，Cj值就会变化；aq往往是因为工艺条件的改变而改变；b是根据资源投入后的经济效果决定的一种决策选择。第三章线性

19、规划的对偶理论及灵敏度分析第32页所谓灵敏度分析，就是要研究初始单纯表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时，原 最优基仍然是最优的；若原最优基不是最优的，如何用最简单的方法找到新的最优解。当系数发生变化后，原结果一 般会发生变化，当然，可用单纯形法从头计算，这样很麻烦，而且也没有必要。因为在单纯形法计算时，每步运算都 和基变量的系数矩阵 B有关。因此，可把变化的系数，经计算后直接填入最终表，并进行检查和分析，可按以下几种 情况处理：原问题对偶问题结论或继续计算的步骤可行解P可行解表中的解仍为最优解可行解非可行解用单纯形法继续计算求最优解非可行解P可行解用对偶单纯形法计算求

20、最优解非可行解非可行解引入人工变量，编制新单纯形表求最优解一、资源数量（限定系数b）变化的分析设第r个约束方程的右端常数br变为b r二br 厶br ,其它系数不变，这样最终表中原问题的解XB就变为XB 二 B（b：b）=（0, ， :br,O,0）T只要Xb -0，最终表中检验数不变，则最优基不变，但最优值发生了变化。新的最优解的值可允许变化范围的确定:0 -iiiiiB （b ，b）二 B b B - b = B b BAb"aibr.0 一"ai r "i-B4baibr=B 'b =br3irJambr这时最终表中b列的所有元素b +airAbr兰

21、0, i =1,2,m即 br _-bir当 ar >0时，b-b/air当<0时，如兰-6/a于是，max'b/air air兰 Abr Emin£/air |air £ 0>ii1A B原材料的消耗。以引例为例，某工厂计划生产甲、乙两种产品，已知生产单位产品所需设备台时及甲乙设备128台时原材料甲4016kg第33页第三章线性规划的对偶理论及灵敏度分析原材料乙0412kg该工厂每生产一件产品甲可获利2元，生产一件乙产品可获利3元，问如何安排生产该工厂获利最多解： maxz =2为 3x2x- +2x2 <8Xi,X2分别是甲、乙两种产品的

22、产量2x1<164x2 <12 Xi,X2 Z0经过运算得如下最终表：4台时设备用于生产甲、乙产品，求这时该厂生产甲、乙产品的最优方案。一 01/401_0 1解：B亠Ab二_21/210=-8i1/21/80 一0 一2 J例4、在上例中，若该厂又从别处抽出将该结果反映到上表中，变为23000CBX BbX1X2X3X4X52为41001/400x5400-2 1/2 13X220 1 1/2 -1/8 0-1.5-1/823000CBXbbX1X2X3X4X52X14+01001/400X54-800-21/213X22+2011/2-1/80-1.5-1/82X141001/

23、400X32001-1/4-1/23X2301001/4-1/2-3/4X,获利 Z = 4 23 3=17 兀3第34页第三章线性规划的对偶理论及灵敏度分析二、目标函数中价值系数 Cj的变化分析分两种情况来讨论：1、若cj是非基变量 Xj的系数，它的检验数为:CTj二 CjCbBPj （或二厂 Cj 八 aij yi ）i=1当Cj变化Cj后，需保证F aj=Cj+ A c -CjCbB 1pj = 0A即Cj ypjC-Jj，才能满足原最优解的条件。2.若 Cr是基变量 Xr的系数CCb当Cr变化心Cr时，就引起 Cb 变化。7 j = Cj - CbB、= Cj - (CbCB)B1pj

24、=Cj - CbBS - (0, Cr,O)B1pj=Cj - CbB1 p Cr arjj -Cr N (p 1,2,n) -1 注: aij为B p j中第r个元素若要使原最优解不变，就须满足 匚j - 0，于是得arj0,Cr -jarj第35页第三章线性规划的对偶理论及灵敏度分析arj 0,Crarj：Cr的变化范围为maxDjJ 【arj2 j mi nt =arjj ia-I. arj例5、在引例中，设基变量x2的系数c2变化.：c2，在原最优解不变条件下，试确定解： X2 为基变量，Q即为CB3召33 二 0.5 ,目34 0.1253 1.5 , 4 0.125maxWmina

25、绍I 0.5 J1- 0.125J即，-3 -c - 1X2 的价值系数5 可在0，4之间变化，而不影响最优解。三、技术系数aij的变化(系数矩阵的变化)分三种情况讨论技术系数aij的变化:例6、分析在原计划中是否应该安排一种新产品。在引例中，设该厂除了生产产品甲、乙外，现有一种新产品丙，已知生产丙产品，每件需消耗原材料A、B各为6kg、3kg，使用设备2台时，每件可获利 5元，问该厂是否应该生产该产品和生产多少？解：分析问题的步骤:(1)设生产丙产品X3 台，其技术系数向量P3 二（2,6,3）t。第36页第三章线性规划的对偶理论及灵敏度分析对应X3的检验数为：二3 =c3 -CBBp3 =

26、5_(1.5,1/8,0)(2,6,3)t=1.25>0 ,说明生产丙产品是有利的。（2）计算丙产品在最终表中对应x3的列向量-p3Orl-31 - -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 ,说明目标函数

27、值还可改善。（3）将X3作为换入变量，X5作为换出变量，进行运算求最优解（见上表）。这时最优解 为=1, X2 = 1.5, X3 = 2 ；总利润为16.5元，比原计划增加了 2.5元。例7、分析原计划生产产品的工艺结构发生变化。在引例中，若原计划生产甲产品的工艺结构有了必改进，这时有关 它的技术系数向量 p； = （2,5,2）T，每件利润4元，试分析对原最优计划有什么影响？解：设改进后的甲产品产量为01/4B -21/2'1/2 1/8x1，那么对应x；的列向量为1 5 =1/20 一3/8 一025/4检验数第37页第三章线性规划的对偶理论及灵敏度分析G =Ci CbBpI =4 一(5,1/8,0)(2