第二章对偶规划.ppt

《第二章对偶规划.ppt》由会员分享，可在线阅读，更多相关《第二章对偶规划.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第2 2章章 对偶规划与灵敏度分析对偶规划与灵敏度分析绪论绪论2.1 LP 2.1 LP 的对偶问题的对偶问题一、对偶问题的提出一、对偶问题的提出 每天可用能力每天可用能力 设备设备A 0 5 15 设备设备B 6 2 24 调试工序调试工序 1 1 5 利润利润 2 1两种家电各生产多少两种家电各生产多少,可获最大利润可获最大利润?绪论绪论解解:设两种家电产量分别为变量设两种家电产量分别为变量x1，x2 5x2 15 6x1+2x2 24 x1+x2 5 x1，x2 0 max Z=2x1+x2另一家公司至少应付出多少代价才能使美佳公司愿意出另一家公司至少应付出多少代价才能使美佳公司愿意出

2、让自己的资源而不组织两种产品的生产？让自己的资源而不组织两种产品的生产？解：设解：设 y1,y2,y3 分别为分别为A,B设备和调试工序工时出让的单设备和调试工序工时出让的单价。价。minW=15y1+24y2+5y3 6y2+y3 25y1+2y2+y3 1y1 y3 0项目项目每天可用能力每天可用能力设备设备A(h)设备设备B(h)调试工序调试工序(h)06152115245利润（元）利润（元）21绪论绪论二、对偶问题的形式二、对偶问题的形式 1 1、对称型对偶问题、对称型对偶问题max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x

3、2+a2nxn b2 (3)am1x1+am2x2+amnxn bm xj 0（j=1,2,n）min w=b1 y1+b2 y2+bm yms.t.a11y1+a21 y2+am1ym c1 a12y1+a22y2 +am2 ym c2 (4)a1ny1+a2ny2+amnym cn yi 0（i=1,2,m）定义定义1 1 设原设原 LP 问题为问题为则称则称下列下列 LP 问题问题为其为其对偶问题，其中对偶问题，其中 yi 0（i=1,2,m）称为对偶变量，称为对偶变量，并称（并称（3）、（）、（4）为一对对称型对偶问题）为一对对称型对偶问题 max z=cx(P)s.t.Ax b x

4、0 min w=yb(D)s.t.Ay c y 0绪论绪论项项目目原原问题问题对对偶偶问题问题A约约束系数矩束系数矩阵阵其其约约束系数矩束系数矩阵阵的的转转置置b约约束条件的右端束条件的右端项项向向量量目目标标函数中的价格系数函数中的价格系数向量向量c目目标标函数中的价格系函数中的价格系数向量数向量约约束条件的右端束条件的右端项项向量向量目目标标函数函数Max z=c XMin =Yb约约束条件束条件AX bAYcc决策决策变变量量X 0Y 0 0绪论绪论例例1 1：写出下面问题的对偶规划写出下面问题的对偶规划maxZ=5X1+6X2 3X1-2X2 74X1+X2 9X1,X2 0minW=

5、7y1+9y23y1+4y2 5-2y1+y2 6y1,y2 0绪论绪论例：写出下面问题的对偶规划例：写出下面问题的对偶规划maxZ=c1x1+c2x2+c3x3 a11x1+a12x2+a13x3 b b1 1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3 b3x1 0,x2 0,x3 无约束无约束2.“非对称型非对称型”(P)a21x1+a22x2+a23x3 b2 a21x1+a22x2+a23x3 b2-a31x1-a32x2-a33x3 -b3x2=-x2,x2 0 0 x3=-x3-x3,x3 0,x3 0绪论绪论e.g.写出写出(P)(P)问题的问题的

6、(D)(D)问题问题max z=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x4 5 2x1 +2x3 -x4 4 x2+x3+x4=6 x1 0,x2,x3 0,x4 无符号限制无符号限制min w=5y1+4y2+6y3 s.t.y1+2y2 2 y1+y3 3 -3y1+2y2+y3 -5 y1-y2+y3=1 y1 0,y20,y3无符号限制无符号限制绪论绪论2.2 LP2.2 LP的对偶理论的对偶理论讨论对称形式：讨论对称形式：（P）问题问题max z=cx s.t.Ax b x 0（D）问题问题min w=yb s.t.yA c y 0一、对偶规划的若干定理一、对偶规

7、划的若干定理Theorem 1 (对称性定理对称性定理)对偶问题的对偶是原问题对偶问题的对偶是原问题.互为对偶互为对偶Theorem 2 (弱对偶定理弱对偶定理)设设 x0 和和 y0 分别是（分别是（P）问题和问题和（D）问题的可行解，则必有问题的可行解，则必有 c x0 y0 b.Corollary 1 如果如果 x*和和 y*分别是（分别是（P）问题和（问题和（D）问问题的可行解，且题的可行解，且c x*=y*b，则则 x*和和 y*分别是（分别是（P）问问题和（题和（D）问题的最优解。问题的最优解。绪论绪论Corollary 2 在一对对偶问题中，如果其中一个问题可在一对对偶问题中，如

8、果其中一个问题可行，但目标函数无界，则另一个问题不可行。行，但目标函数无界，则另一个问题不可行。Corollary 3 如果一对对偶问题都有可行解，则它们都如果一对对偶问题都有可行解，则它们都有最优解。有最优解。Theorem 3 (对偶定理对偶定理)如果（如果（P）问题（问题（D）问题）有问题）有最优解，那么（最优解，那么（D）问题（问题（P）问题）也有最优解，问题）也有最优解，且目标函数值相等。且目标函数值相等。Corollary 4 (单纯形乘子定理单纯形乘子定理)如果（如果（P）问题有最优解，问题有最优解，最优基为最优基为 B，则则 y*=cBB-1 就是就是（D）问题的一个最优问题的

9、一个最优解解。绪论绪论Corollary 5 对于对称形式（P）问题，如果有最优解，则在其最优单纯形表中，松弛变量x n+1,x n+2,x n+m的检验数（）的负值即为（D）问题的一个最优解。cBsxBsc0 xs检验数cBcN0 xBxNxsBNIcBcN0bb0cBcBxBxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB-1by*=cBB-1 是是最优解最优解此处记录了此处记录了B 的逆矩阵的逆矩阵B-1 综上所述，（综上所述，（P P）问题与（问题与（D D）问题的解之间只有以问题的解之间只有以下三种可能的关系：下三种可能的关系：（1 1）两个问题都有可行解，从而都有最优

10、解，分别）两个问题都有可行解，从而都有最优解，分别设为设为 x*，y*,则必有则必有 z*=cx*=y*b=w*；（2 2）一个问题为无界，另一个问题必无可行解；一个问题为无界，另一个问题必无可行解；（3 3）两个问题都无可行解。）两个问题都无可行解。绪论绪论Theorem 4 (互补松弛定理互补松弛定理)设设 x*和和 y*分别是（分别是（P）问题问题和（和（D）问题的可行解，则它们分别是（问题的可行解，则它们分别是（P）、）、（D）问题的最优解的充要条件是：问题的最优解的充要条件是：y*(b Ax*)=0；(y*A c)x*=0 同时成立同时成立。因为因为，y*0,Ax*b,由由 y*(b

11、 Ax*)=0，有有由由 x*0,y*A c，(y*A c)x*=0，有有绪论绪论 在线性规划问题的最优解中，如果对应某在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也不等式，则其对应的对偶变量一定为零。也即即绪论绪论二、对偶规划的求解二、对偶规划的求解1 1、利用原问题的最优单纯形表求对偶最优解的方法、利用原问题的最优单纯形表求对偶最优解的方法cBsxBsc0 xs检验数cBcN0 xBxNxsBNIcBcN0bb0

12、cBcBxBxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB-1bB-1绪论绪论e.g.求如下求如下 LP 问题的对偶问题的最优解问题的对偶问题的最优解max z=4x1+3x2+7x3 s.t.x1+2x2+2x3 100 3x1+x2+3x3 100 x1,x2,x3 0 解：解：对偶问题为对偶问题为min w=100y1+100y2 s.t.y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,y2 0 ccBxB37x2x3检验数43700 x1x2x3x4x5-3/4103/45/401-1/4-5/200-1/2b2525-250-1/21/2-2原问题的最优

13、解和最优值为：原问题的最优解和最优值为：x*=(0,25,25)T z*=250由由推论推论5 5可知：可知：对偶问题的最优解和最优值为对偶问题的最优解和最优值为 y*=(1/2,2)w*=250绪论绪论如果（P）问题为：max z=cx(P)s.t.Ax=b x 0cBsxBsc0 xs检验数cBcN-MxBxNxRBNIcBcN-Mbb0cBcBxBxBIB-1NB-1B-1b0cN-cBB-1N-M-cBB-1-cBB-1by*=cBB-1=-M-绪论绪论2 2、利用互补松弛定理求对偶最优解、利用互补松弛定理求对偶最优解e.g.求如下求如下 LP 问题的对偶问题的最优解问题的对偶问题的最

14、优解max z=4x1+3x2 s.t.x1+2x2 2 x1-2x2 3 2x1+3x2 5 x1+x2 2 3x1+x2 3 x1,x2 0 解：解：对偶问题为对偶问题为:min w=2y1+3y2+5y3+2y4+3y5 s.t.y1+y2+2y3+y4+3y5 4 2y1-2y2+3y3+y4+y5 3 y1,y2,y3,y4,y5 0绪论绪论max z=4x1+3x2 s.t.x1+2x2 2 (1)x1-2x2 3 (2)(p)2x1+3x2 5 (3)x1+x2 2 (4)3x1+x2 3 (5)x1,x2 0 可用图解法求解（P）问题，得：x*=(4/5，3/5)T z*=5m

15、in w=2y1+3y2+5y3+2y4+3y5 s.t.y1+y2+2y3+y4+3y5 4(D)2y1-2y2+3y3+y4+y5 3 y1,y2,y3,y4,y5 0将将x*代入（代入（P）问题的约束条件，知：问题的约束条件，知：约束条件约束条件(2)(2)、(3)(3)、(4)(4)成立严格不等式成立严格不等式由由互补松弛定理知：互补松弛定理知：y2*=y3*=y4*=0又因为又因为x1*，x2*不为零不为零 所以所以 y1*+3y5*=4 2y1*+y5*=3解得：解得：y1*=y5*=1故故 y*=(1,0,0,0,1)w*=5绪论绪论Note:在求解一个在求解一个LPLP问题时，

16、往往需要先考虑一下，问题时，往往需要先考虑一下，究竟是解它的原问题还是解它的对偶问题比较省事。究竟是解它的原问题还是解它的对偶问题比较省事。一般来说，求解一个一般来说，求解一个LPLP问题的计算量，是同这个问题的计算量，是同这个问题所包含约束条件的个数有密切关系的，如果约束问题所包含约束条件的个数有密切关系的，如果约束条件的个数愈多，则基可行解中基变量的个数也随之条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地迭代变换的计算量也愈大，根据经验，增多，相应地迭代变换的计算量也愈大，根据经验，单纯形法的迭代次数大约是约束条件个数的单纯形法的迭代次数大约是约束条件个数的1 11.51.5倍

17、倍.因此，当因此，当m n 则则用其对偶问题求解较好。用其对偶问题求解较好。绪论绪论2.3 2.3 对偶单纯形法对偶单纯形法一、对偶单纯形法的基本思路一、对偶单纯形法的基本思路 对偶单纯形法是根据对偶原理和单纯形法的原理而设计出对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解来求解 LP 问题的一种方法（而不能简单地将它理解为是求解对问题的一种方法（而不能简单地将它理解为是求解对偶问题的方法）。偶问题的方法）。原始单纯形原始单纯形法法 考察如下的考察如下的 LP 问题及其对偶问题问题及其对偶问题 max z=cx(P)s.t.Ax=b x 0 min w=yb(D)s.t.yA c y

18、 无符号限制无符号限制设设 B 为为(P)问题的一个基，不妨设问题的一个基，不妨设B=(p1,p2,pm)则则为为(P)问题的一个基本解；问题的一个基本解；仅当仅当 xB=B-1b 0 时时则则为为一个基可行解；一个基可行解；若若此时检验数满足此时检验数满足则则为为(P)问题一个最优解问题一个最优解原始可行性条原始可行性条件件原始最优性条原始最优性条件件绪论绪论原始单纯形法的基本思路是：原始单纯形法的基本思路是：令令 y=cBB-1，代入代入原始最优性条件原始最优性条件得得 yA c对偶可行性条对偶可行性条件件原始最优性条件与对偶可行性条件等价原始最优性条件与对偶可行性条件等价Definiti

19、on 1 若若原问题（原问题（P P）的一个基本解的一个基本解 对应的检验数向量满足对应的检验数向量满足则则称称 x为（为（P P）的一个正则解的一个正则解从满足原始可行性条件的一个基可行解出发，经从满足原始可行性条件的一个基可行解出发，经过换基运算迭代到另一个基可行解，即总是保持过换基运算迭代到另一个基可行解，即总是保持解的可行性不变，变化的只是检验数向量解的可行性不变，变化的只是检验数向量 ，它从，它从不满足不满足 00，逐步迭代到，逐步迭代到 00成立，一旦达到成立，一旦达到 00，也就得到了原问题的最优解。，也就得到了原问题的最优解。绪论绪论对偶单纯形法的基本思路是：对偶单纯形法的基本

20、思路是：在迭代过程中，始终保持对偶问题解的可行性，在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件问题的解也满足了可行性条件,也就达到了最优解。也就达到了最优解。也即在保持正则解的正则性不变条件下，在迭代也即在保持正则解的正则性不变条件下，在迭代过程中，使原问题解的不可行性逐步消失，一旦迭过程中，使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解。代到可行解时，即达到了最优解。绪论绪论二、对偶单纯形法的计算步骤二、对偶单纯形法的计算步骤 max z=cx s.t.Ax=b

21、x 0求解求解如右的如右的LP 问题：问题：对偶单纯形法的计算步骤：Step 1 找出初始正则基，列初始对偶单纯形表；找出初始正则基，列初始对偶单纯形表；x1x2xmxB-z(0)000检验数b1b2bm 100 a1m+1 a1m+2 a1n 010 a2m+1 a2m+2 a2n 001 amm+1 amm+2 amnc1c2cmb x1 x2 xm xm+1 xm+2 xncB c1 c2 cm cm+1 cm+2 cn c 小于等于零小于等于零 Step 2 若若 b=B-1b 0，则，则停止计算，当前的正则解停止计算，当前的正则解 x=B-1b 即为原问题的即为原问题的最优解，否则转

22、入下一步；最优解，否则转入下一步；绪论绪论 Step 3 确定换出基变量：确定换出基变量：则取则取 xr 为换出基变量；为换出基变量；Step 4 若若 则停止计算，原问题无则停止计算，原问题无可行解，否则可行解，否则转入下一步；转入下一步；Step 5 确定换入基变量：若确定换入基变量：若则则取取 xk为换入基变量为换入基变量转转 Step 2Step 6 以以 为主元进行换基运算，得新的正则解为主元进行换基运算，得新的正则解令令x1x2xmxB-z(0)000检验数b1b2bm 100 a1m+1 a1m+2 a1n 010 a2m+1 a2m+2 a2n 001 amm+1 amm+2

23、amnc1c2cmb x1 x2 xm xm+1 xm+2 xncB c1 c2 cm cm+1 cm+2 cn c绪论绪论e.g.5 用对偶单纯形法求解min z=2x1+4x2+6x3 s.t.2x1-x2+x3 10 x1+2x2+2x3 12 2x2-x3 4 x1，x2，x3 0解：解：将问题化为：将问题化为：max z=-2x1-4x2-6x3 s.t.-2x1+x2-x3+x4=-10 x1+2x2+2x3+x5=12 -2x2+x3+x6=-4 xj 0 (j=1,2,6)检验数ccBxB-2-4-6000 x1 x2 x3 x4 x5 x6 000 x4x5x6-21-110

24、01220100-21001-2-4-6000 b-1012-40-2 1-1/2 1/2-1/20050 x1-25/2 3/21/21070-5-1-500 x2-2-401-1/200-1/22101/4-1/2 0-1/460011/41/215/4200-15/2-10-5/2初始正则解为初始正则解为:x0=(0,0,0,-10,12,-4)T最优解为最优解为:x*=(6,2,0,0,2,0)Tz*=20绪论绪论对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 bi0所有所有 bi0?最优性检验最优性检验所有所有所有所有

25、换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解的进化原始基本解的进化可行可行 最优最优非可行非可行 可行可行(最优最优)对偶单纯形法有以下优点：对偶单纯形法有以下优点：（1 1）初始解可以是非可行解；）初始解可以是非可行解；（2 2）当变量多于约束条件，可以减少计算工作量；）当变量多于约束条件，可以减少计算工作量；（3 3）在灵敏度分析中，有时需要用对偶单纯形法，这样可以）在灵敏度分析中，有时需要用对偶单纯形法，这样可以 使问题的处理简便。使问题的处理简便。绪论绪

26、论5 5 灵敏度分析灵敏度分析一、目标函数中价值系数一、目标函数中价值系数cj 的变化分析的变化分析 灵敏度分析（灵敏度分析（Sensitivity Analysis）又称为优化又称为优化后分析（后分析（Postoptimality Analysis），），就是分析研究线就是分析研究线性规划模型参数的取值变化时，最优解或最优基的影性规划模型参数的取值变化时，最优解或最优基的影响，它在应用线性规划解决实际问题的过程中是非常响，它在应用线性规划解决实际问题的过程中是非常有用的。有用的。目标函数中价值系数目标函数中价值系数 c cj j 的变化会引起检验数的变的变化会引起检验数的变化，从而影响最优性

27、条件能否成立化，从而影响最优性条件能否成立 。绪论绪论第第二二章章 线性规划线性规划的对偶理论的对偶理论1 1、若、若cj 是非基变量的系数是非基变量的系数设设 cj 改变了改变了即即变化后的检验数为变化后的检验数为要保持最优性不变，必须满足要保持最优性不变，必须满足 cAb检验数0B-1b-cB B-1b B NcB cN I B-1N0 cN-cB B-1N绪论绪论5 5 灵敏度分析灵敏度分析2 2、若、若cr 是基变量是基变量xr 的的系数系数设设 cr 改变了改变了即即因因 ，则则其中其中 是矩阵是矩阵 的第的第r 行，行，于是变化后的检验数为：于是变化后的检验数为：要求原最优性不变，

28、则必须满足要求原最优性不变，则必须满足于是得到于是得到当当 时，有时，有 当当 时，有时，有因此，因此，的允许变化范围是：的允许变化范围是：绪论绪论，e.g.6 佳美公司计划制造佳美公司计划制造、两种产品，已知各制两种产品，已知各制造一个单位时分别占用的设备造一个单位时分别占用的设备A A、B B的台时、调试时间、的台时、调试时间、每天设备每天设备A A、B B 的台时、调试工序每天可用于这两种产的台时、调试工序每天可用于这两种产品的能力及各售出一单位时的获利情况，如表，问应怎品的能力及各售出一单位时的获利情况，如表，问应怎样组织生产才能使总利润最多。样组织生产才能使总利润最多。设备设备A(h

29、)设备设备B(h)调试工序调试工序(h)利润利润(百元)每天可每天可用能力用能力资源资源产品产品05621121152451 1、如果产品如果产品的利润降至的利润降至1.51.5百元百元/单位，而产品单位，而产品的利润增至的利润增至2 2百元百元/单元时，最优生产计划有何变化；单元时，最优生产计划有何变化；2、如果产品、如果产品的利润不变，则产品的利润不变，则产品的利润在什么范围内变化时，则该的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。公司的最优生产计划将不发生变化。绪论绪论解：设设 x1,x2 分别表示分别表示、两种产品的生产数量，两种产品的生产数量，max z=2x1+x

30、2 s.t.5 x215 6x1+2x224x1+x25 x1,x20max z=2x1+x2+0 x3+0 x4+0 x5 s.t.5 x2+x3=15 6x1+2x2+x4=24x1+x2+x5=5 x1,x2,x3,x4,x50用单纯形法求解得最终单纯形表用单纯形法求解得最终单纯形表ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2得得最优解为：最优解为：x*=(7/2,3/2,15/2,0,0)T zmax=8.5(百元百元)1 1、若两产品利润均改变

31、、若两产品利润均改变3/223/2 21/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x*=(2,3,0,6,0,0)Tx40 zmax=9(百元百元)ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2直接计算直接计算,得得:解得解得即产品即产品的利润的利润 c2 的变化满足的变化满足:2/3 2/3 c2 2 2 时时,该公司的最优生产计划将不发生变化该公司的最优生产计划将不发生变化绪论绪论第第二二章章 线性规划线

32、性规划的对偶理论的对偶理论二、约束条件中资源数量二、约束条件中资源数量bi 的变化分析的变化分析 检验数B-1b-cB B-1b I B-1N0cN-cB B-1N 由最终单纯形表可知，资源数量由最终单纯形表可知，资源数量 bi 的变化，会影的变化，会影响到原最优解的可行性与目标函数值。响到原最优解的可行性与目标函数值。设某个资源数量设某个资源数量 br 变化为变化为并并假设原问题的其他系数不变，则使最终单纯形表中假设原问题的其他系数不变，则使最终单纯形表中原问题的解相应地变化为原问题的解相应地变化为其中其中绪论绪论5 5 灵敏度分析灵敏度分析这时其中其中为为B-1 的第的第 r 列，列，则必

33、须则必须当当 时，有时，有当当 时，有时，有因此因此 的允许变化范围是：的允许变化范围是：若要求最优基不变，若要求最优基不变，绪论绪论 e.g.7在上述佳美公司的例子中：（在上述佳美公司的例子中：（1 1）若设备）若设备 A 和和调试工序的每天能力不变，而设备调试工序的每天能力不变，而设备 B 每天的能力增加每天的能力增加到到3232小时，分析公司最优计划的变化；（小时，分析公司最优计划的变化；（2 2）若设备）若设备A和和 B 每天可用能力不变，则调试工序能力在什么范围每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。内变化时，问题的最优基不变。解：解：(1)因因设备设备

34、 B 原原每天的能力为每天的能力为2424，所以，所以 有有进一步有进一步有加入到最终单纯形表，得加入到最终单纯形表，得：绪论绪论5 5 灵敏度分析灵敏度分析ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/235/211/2-1/2-21/2因为因为用对偶单纯形法继续计算，得用对偶单纯形法继续计算，得-1/4500 x40151015-10-2-10-41-62改变为仅生产改变为仅生产5 5个单位个单位产品产品,利润利润 z*=10(2)由此由此,调试工序的能

35、力应在调试工序的能力应在4小时小时6小时之间小时之间.绪论绪论第第二二章章 线性规划线性规划的对偶理论的对偶理论三、增加一个变量三、增加一个变量 xj 的分析的分析 增加一个变量在实际问题中反映为增加一种新的产品。增加一个变量在实际问题中反映为增加一种新的产品。设设新变量为新变量为在原在原最优单纯形表增加一列最优单纯形表增加一列及及检验数检验数若若则原则原问题最优解不变；问题最优解不变；若若则按则按单纯形法继续计算。单纯形法继续计算。绪论绪论e.g.8在佳美公司例子中，设该公司又计划推出新产品在佳美公司例子中，设该公司又计划推出新产品，生产一单位产品，生产一单位产品，所需设备，所需设备A A、

36、B B、C C调试工序的调试工序的时间分别为时间分别为3 3小时、小时、4 4小时、小时、2 2小时，该产品的预期盈利小时，该产品的预期盈利为为3 3百元百元/单位，试分析该新产品是否值得投产；如投产单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化。对该公司的最优生产计划有何变化。解：解：设设新产品新产品的生产数量为的生产数量为 x6,c6=3,p6=(3,4,2)TccBxB x1x2x3x4x5x6210003021x3x1x2检验数0015/4-15/2-71001/4-1/20010-1/43/2215/2 7/2 3/2-17/2b000-1/4-1/21x63

37、21/2-1/8 3/413/4-1/2-1/8-5/40-37/47/23/8-9/4051/4最优生产计划为最优生产计划为:每天生产产品每天生产产品 7/2单位单位;新产品新产品 3/4单位单位获利获利 37/4(37/4(百元百元)绪论绪论四、约束条件中技术系数四、约束条件中技术系数 aij 的变化分析的变化分析1 1、非基变量、非基变量 xj 的系数列向量的系数列向量 pj 的变化分析的变化分析 检验数B-1b-cB B-1b I B-1N0cN-cB B-1N此时，此时，只影响只影响问题的问题的最优性最优性设设非基变量非基变量 xj 的系数列向量的系数列向量 pj 改变为改变为则则变

38、化后的检验数为变化后的检验数为y=cBB-1是原问题的是原问题的对偶可行解对偶可行解要使原要使原最优基最优基 B 保持不变，保持不变，特别，当特别，当 时，由上式得时，由上式得当当 时，时，当当 时，时，则必须则必须绪论绪论5 5 灵敏度分析灵敏度分析2 2、基变量、基变量 xj 的系数列向量的系数列向量 pj 的变化分析的变化分析 对于最优基对于最优基 B 而言，当而言，当基变量基变量 xj 的系数列向量的系数列向量 pj 发生变化时，将使相应的发生变化时，将使相应的B，B-1-1都发生变化，因此，都发生变化，因此，它不仅影响现行最优解的可行性，也影响它的最优性。它不仅影响现行最优解的可行性

39、，也影响它的最优性。e.g.9 在佳美公司的例子中，若产品在佳美公司的例子中，若产品每单位需设备每单位需设备A A、B B和调试工时和调试工时8 8小时、小时、4 4小时、小时、1 1小时，该产品的利润变小时，该产品的利润变为为3 3百元百元/单位，试重新确定该公司最优生产计划。单位，试重新确定该公司最优生产计划。解：解：先将生产工时变化后的产品先将生产工时变化后的产品看作是一种新产品，看作是一种新产品，生产量为生产量为 ，直接计算，直接计算 ：绪论绪论第第二二章章 线性规划线性规划的对偶理论的对偶理论将其加入原最终单纯形表:ccBxB x1x2x2x3x4x5213000021x3x1x2检

40、验数0011/215/4-15/2101/201/4-1/2011/20-1/43/215/2 7/2 3/2-17/2b003/20-1/4-1/21/2绪论绪论将其将其加入原最终单纯形表加入原最终单纯形表:ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/23/223/2 21/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x40ccBxB x1x2x3x4x523000023x3x1x2检验数0015/4-15/2

41、1001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/211/21/21/23/2004-24-91/2-2201/2-5-131-1/233-24-1/24-1/613/81/601/80011/415/8x5-5/24-1/30-1/12-89/8此时已得最优解此时已得最优解:每天生产产品每天生产产品 11/4 11/4个单位个单位;新产品新产品15/815/8个个单位单位,获利获利89/8(89/8(百元百元).).绪论绪论五、增加新约束条件的分析五、增加新约束条件的分析 增加一个约束条件在实际问题中相当增添一道工增加一个约束条件在实际问题中相当

42、增添一道工序。设在原规划线性问题中，增加一个新的约束条件序。设在原规划线性问题中，增加一个新的约束条件(*)则则首先把已求得的原问题的最优解首先把已求得的原问题的最优解 代入新增加的约束条件代入新增加的约束条件(*)(*)，如果条件满足，则原，如果条件满足，则原问题的最优解问题的最优解 x*仍为新问题的最优解，结束。如果仍为新问题的最优解，结束。如果条件不满足，则将新增加的约束条件直接反映到最终条件不满足，则将新增加的约束条件直接反映到最终单纯形表中再进一步分析。单纯形表中再进一步分析。绪论绪论e.g.10仍以佳美公司为例，设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时

43、，产品每单位须2小时，又环境试验工序每天生产能力为12小时，试分析增加该工序后的佳美公司最优生产计划。解：解：ccBxB x1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/2 7/2 3/2-17/2b000-1/4-1/2增加约束条件增加约束条件 3x1+2x212 原问题的最优原问题的最优解解 x1=7/2x2=3/2 不满足不满足环环境试验工序约束，境试验工序约束，故将约束条件故将约束条件 3x1+2x2+x6=12加入单纯形表中加入单纯形表中ccBxB x1x2x3x4x5x62100000210 x3x1x2x6

44、 检验数0015/4-15/201001/4-1/20010-1/43/2032000115/27/23/212-17/2b000-1/4-1/200-3/43/23/20-1/4-3/2-3/2x5-3/21/61-2/315/20-5151/30-1/34-1/2010-1/60-1/3-8 添加环境试验工序后添加环境试验工序后,佳美公司的最优生产计划佳美公司的最优生产计划为只生产为只生产 4 4 单位产品单位产品,获利获利8(8(百元百元)绪论绪论绪论绪论Theorem 1 (对称性定理)proof:先将先将(D)(D)问题化成原问题形式问题化成原问题形式（D）问题问题min w=yb

45、s.t.yA c y 0设设 xT为它的对偶变量为它的对偶变量,写出它的对偶问题写出它的对偶问题即即这就是这就是(P)(P)问题问题.证毕证毕绪论绪论Theorem 2 (弱对偶定理)proof:因为因为 x0 是是(P)问题的可行解问题的可行解,故必有故必有Ax0 b,x0 0(1)又又y0是问题是问题(D)(D)的可行解的可行解,于是有于是有y0A c,y0 0(2)用用y0 左乘不等式左乘不等式(1)两边两边,得得y0Ax0 y0b 用用x0 左乘不等式左乘不等式(2)两边两边,得得y0Ax0 cx0 从而有从而有 cx0 y0b 证毕c x0 y0 b绪论绪论Theorem 3 (对偶

46、定理)proof:设设 x*是（是（P P）问题的最优解，它对应的基矩问题的最优解，它对应的基矩阵为阵为B B，引入松弛变量引入松弛变量 xs=(xn+1，xn+2，,xn+m)T 将将（P P）问题化为标准形式问题化为标准形式.显然，该问题也有最优解显然，该问题也有最优解由由最优性判别定理知最优性判别定理知令令则有绪论绪论即这这表明表明是是（D）问题的可行解问题的可行解对应的目标函数值为对应的目标函数值为：又又因为因为 x*是是（P）问题的最优解，其目标函数值为：问题的最优解，其目标函数值为：所以有所以有则则由由 Corollary 1 知知（D）问题有最优解，且两者的问题有最优解，且两者的目标函数的最优值相等。目标函数的最优值相等。同理可证，当同理可证，当（D）问题有最优解时，问题有最优解时，（P）问题也有问题也有最优解，且目标函数相等。最优解，且目标函数相等。证毕绪论绪论Theorem 4 (互补松弛定理)proof:必要性必要性设设 x*、y*分别是分别是(P)问题和问题和(D)问题的最优解问题的最优解.则则所以由所以由推出推出于是于是充分性充分性由由得得 又又 x*、y*分别是分别是（P）问题和问题和（D）问题的可行解，问题的可行解，所以所以 x*、y*分别是分别是（P）问题和问题和（D）问题的最优解。问题的最优解。证毕绪论绪论