第二章线性规划的对偶理论

《第二章线性规划的对偶理论》由会员分享，可在线阅读，更多相关《第二章线性规划的对偶理论（51页珍藏版）》请在装配图网上搜索。

1、 第二章第二章 线性规划的对偶理论线性规划的对偶理论 Optimizing Methods 1 对偶问题的提出一、对偶问题的实例一、对偶问题的实例 产品 资源 资源 甲 乙 限制 A 3 2 65 B 2 1 40 C 0 3 75 单件利润 1500 2500 max z=1500 x1+2500 x2 s.t.3x1+2x2 65 2x1 +x2 40 (1)3x2 75 x1 ,x2 0最优解为：最优解为：x1*=5，x2*=25 zmax=70000设 y1,y2,y3 分别为分别为 A,B,C 三种资源出售的价格三种资源出售的价格3y1+2y2 15002y1+y2+3y3 2500

2、w=65y1+40y2+75y3 min w=65y1+40y2+75y3 s.t.3y1+2y2 1500 (2)2y1+y2+3y3 2500 y1,y2,y3 0最优解为：最优解为：y1*=500y2*=0，y3*=500,wmin=70000如果称（如果称（1 1）为）为LP 问题的问题的原问题，则称（原问题，则称（2 2）为（）为（1 1）的对偶问题。的对偶问题。第二章 线性规划的对偶理论二、对偶问题的形式二、对偶问题的形式 1 1、对称型对偶问题、对称型对偶问题max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nx

3、n 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 0 min

4、w=yb(D)s.t.yA c y 01 对偶问题的提出2 2、非对称型对偶问题、非对称型对偶问题 max z=cx(P)s.t.Ax=b x 0 max z=cx s.t.Ax b -Ax -b x 0引入对偶变量引入对偶变量（u,v），其中其中 u=(u1,u2,um)为对应于第一组不等式约束为对应于第一组不等式约束 Ax b 的对偶变的对偶变量，量，v=(v1,v2,vm)为对应于第二组不等式约对应于第二组不等式约束束 -Ax-b 的对偶变量，按对称型的结论：的对偶变量，按对称型的结论：min(,).(,),0bwu vbAs tu vcAu v min w=(u-v)b s.t.(u-

5、v)A c u,v 0令令 y=u-v min w=yb(D)s.t.yA c y 0 min w=yb(D)s.t.yA c y 无符号限制无符号限制第二章 线性规划的对偶理论3 3、混合型对偶问题、混合型对偶问题 max z=c1x1+c2x2(P)s.t.A11x1+A12x2 b1 A21x1+A22x2=b2 A31x1+A32x2 b3 x1 0,x2 无符号限制无符号限制其中其中 Aij 为mi nj 矩阵矩阵；bi为mi维列向量维列向量；cj为nj 维行向量；xj 为为nj 维列向量维列向量，i=1,2,3；j=1,2,且且m1+m2+m3=m,n1+n2=n令令 x2=x21

6、-x22,x21,x22 0.化原问题为标准型：化原问题为标准型：max z=c1 x1+c2(x21-x22)s.t.A11x1+A12(x21-x22)+Isxs=b1 A21x1+A22(x21-x22)=b2 A31x1+A32(x21-x22)-Itxt=b3 x1,x21,x22,xs,xt 0 min w=b1 y1+b2y2+b3y3 s.t.y1 A11+y2 A21+y3 A31 c1 y1 A12+y2 A22+y3 A32 c2 -y1 A12-y2 A22-y3 A32 -c2 y1 Is 0 -y3 It 0 y1,y2,y3无符号限制无符号限制按非对称型 min

7、w=b1 y1+b2y2+b3y3 s.t.y1 A11+y2 A21+y3 A31 c1 y1 A12+y2 A22+y3 A32=c2 y1 0,y2 无符号限制无符号限制,y3 0 1 对偶问题的提出 原问题与对偶问题的关系原问题与对偶问题的关系原问题原问题目标函数目标函数 max目标函数目标函数 minm个=n个=n n个00无符号限制m个00无符号限制目标函数的系数约束条件右端常数系数矩阵 A约束条件右端常数目标函数的系数系数矩阵 AT约束条件约束条件约束条件约束条件变变 量量变变 量量对偶问题对偶问题e.g.1 写出写出(P)(P)问题问题的的(D)(D)问题问题max z=2x1

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

9、定理)对偶问题的对偶是原问题对偶问题的对偶是原问题.互为对偶互为对偶proofTheorem 2 (弱对偶定理弱对偶定理)设设 x0 和和 y0 分别是（分别是（P）问题和）问题和（D）问题的可行解，则必有）问题的可行解，则必有 c x0 y0 b.Corollary 1 如果如果 x*和和 y*分别是（分别是（P）问题和（）问题和（D）问）问题的可行解，且题的可行解，且c x*=y*b，则则 x*和和 y*分别是（分别是（P）问）问题和（题和（D）问题的最优解。）问题的最优解。proof向前2 对偶问题的基本性质Theorem 1 (对称性定理对称性定理)proof:先将先将(D)(D)问题

10、化成原问题形式问题化成原问题形式max().()0TTTTTTwbys tAycy （D）问题问题min w=yb s.t.yA c y 0设设 xT为它的对偶变量为它的对偶变量,写出它的对偶问题写出它的对偶问题min().()0TTTTTTzxcstxAbx max.0zcxs tAxbx即即这就是这就是(P)(P)问题问题.证毕证毕2 对偶问题的基本性质Theorem 2 (弱对偶定理弱对偶定理)proof:因为因为 x0 是是(P)问题的可行解问题的可行解,故必有故必有Ax0 b,x0 0 (1)又又y0是问题是问题(D)(D)的可行解的可行解,于是有于是有y0A c,y0 0 (2)用

11、用y0 左乘不等式左乘不等式(1)两边两边,得得y0Ax0 y0b 用用x0 左乘不等式左乘不等式(2)两边两边,得得y0Ax0 cx0 从而有从而有 cx0 y0b 证毕c x0 y0 b第二章 线性规划的对偶理论Corollary 2 在一对对偶问题中，如果其中一个问题可在一对对偶问题中，如果其中一个问题可行，但目标函数无界，则另一个问题不可行。行，但目标函数无界，则另一个问题不可行。Corollary 3 如果一对对偶问题都有可行解，则它们都如果一对对偶问题都有可行解，则它们都有最优解。有最优解。Theorem 3 (对偶定理对偶定理)如果（如果（P）问题（）问题（D）问题）有）问题）有

12、最优解，那么（最优解，那么（D）问题（）问题（P）问题）也有最优解，）问题）也有最优解，且目标函数值相等。且目标函数值相等。proofCorollary 4 (单纯形乘子定理单纯形乘子定理)如果（如果（P）问题有最优解，）问题有最优解，最优基为最优基为 B，则，则 y*=cBB-1 就是就是（D）问题的一个最优问题的一个最优解解。向前2 对偶问题的基本性质Theorem 3 (对偶定理对偶定理)proof:设设 x*是（是（P P）问题的最优解，它对应的基矩）问题的最优解，它对应的基矩阵为阵为B B，引入松弛变量，引入松弛变量 xs=(xn+1，xn+2，,xn+m)T 将将（P P）问题化为

13、标准形式）问题化为标准形式.max0.,0ssszcxxstAxIxbx x显然，该问题也有最优解显然，该问题也有最优解*sxxx由最优性判别定理知由最优性判别定理知100Bcc BAI令令1*Byc B则有*0cyAy2 对偶问题的基本性质即即*0y A cy这表明这表明1*Byc B是是（D）问题的可行解问题的可行解对应的目标函数值为对应的目标函数值为：1*Bwy bc B b又因为又因为 x*是是（P）问题的最优解，其目标函数值为：问题的最优解，其目标函数值为：1*Bzcxc B b所以有所以有1*Bcxc B by b则由则由 Corollary 1 知知（D）问题有最优解，且两者的问

14、题有最优解，且两者的目标函数的最优值相等。目标函数的最优值相等。同理可证，当同理可证，当（D）问题有最优解时，问题有最优解时，（P）问题也有问题也有最优解，且目标函数相等。最优解，且目标函数相等。证毕2 对偶问题的基本性质Corollary 5 对于对称形式对于对称形式（P）问题，如果有最优解，）问题，如果有最优解，则在其最优单纯形表中，松弛变量则在其最优单纯形表中，松弛变量x n+1,x n+2,x n+m的检验数（的检验数（）的）的 负值即为（负值即为（D）问题的问题的一个最优解一个最优解。12,nnn mcBsxBsc0 xs检验数cBcN0 xBxNxsBNIcBcN0bb0cBcBx

15、BxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB-1by*=cBB-1 是最优解是最优解此处记录了此处记录了B 的逆矩阵的逆矩阵B-1 综上所述，（综上所述，（P P）问题与（）问题与（D D）问题的解之间只有以）问题的解之间只有以下三种可能的关系：下三种可能的关系：（1 1）两个问题都有可行解，从而都有最优解，分别）两个问题都有可行解，从而都有最优解，分别设为设为 x*，y*,则必有则必有 z*=cx*=y*b=w*；（2 2）一个问题为无界，另一个问题必无可行解；）一个问题为无界，另一个问题必无可行解；（3 3）两个问题都无可行解。）两个问题都无可行解。第二章 线性规划的对

16、偶理论Theorem 4 (互补松弛定理互补松弛定理)设设 x*和和 y*分别是（分别是（P）问题）问题和（和（D）问题的可行解，则它们分别是（）问题的可行解，则它们分别是（P）、）、（D）问题的最优解的充要条件是：问题的最优解的充要条件是：y*(b Ax*)=0；(y*A c)x*=0 同时成立同时成立。proof因为因为，y*0,Ax*b,由由 y*(b Ax*)=0，有有1()0,1,2,niiijjjyba xim由由 x*0,y*A c，(y*A c)x*=0，有有1()0,1,2,mijijjia ycxjn 一个规划的某个约束成立严格不等式（约束条件为一个规划的某个约束成立严格不

17、等式（约束条件为松），对应的对偶规划中变量取松），对应的对偶规划中变量取0 0（变量是紧），当（变量是紧），当某个变量不为某个变量不为0 0时（变量是松），对应的对偶规划中时（变量是松），对应的对偶规划中约束成立等式（约束条件是紧）约束成立等式（约束条件是紧）。向前2 对偶问题的基本性质Theorem 4 (互补松弛定理互补松弛定理)proof:必要性必要性设设 x*、y*分别是分别是(P)问题和问题和(D)问题的最优解问题的最优解.则则*,*0;*,*0;*,Axbxy Acycxy b所以由所以由*,cxyAxy b推出推出*,cxyAxy b于是于是*(*)0,(*)*0ybAxy A

18、c x充分性充分性由由*(*)0,(*)*0ybAxy A c x得得*,cxyAxy b 又又 x*、y*分别是分别是（P）问题和问题和（D）问题的可行解，问题的可行解，所以所以 x*、y*分别是分别是（P）问题和问题和（D）问题的最优解。问题的最优解。证毕2 对偶问题的基本性质二、对偶规划的求解二、对偶规划的求解1 1、利用原问题的最优单纯形表求对偶最优解的方法、利用原问题的最优单纯形表求对偶最优解的方法cBsxBsc0 xs检验数cBcN0 xBxNxsBNIcBcN0bb0cBcBxBxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB-1bB-1第二章 线性规划的对偶理论e

19、.g.2 求如下求如下 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检验数4 3 7 0 0 x1 x2 x3 x4 x5-3/4103/45/401-1/4-5/200-1/2b2525-250-1/21/2-2原问题的最优解和最优值为：原问题的最优解和最优值为：x*=(0,25,25)T z*=2

20、50由推论由推论5 5可知：可知：对偶问题的最优解和最优值为对偶问题的最优解和最优值为 y*=(1/2,2)w*=2502 对偶问题的基本性质如果如果（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-R第二章 线性规划的对偶理论2 2、利用互补松弛定理求对偶最优解、利用互补松弛定理求对偶最优解1()0,1,2,niiijjjyba xim1()0,1,2,mijijjia ycxjne.

21、g.3 求如下求如下 LP 问题的对偶问题的最优解问题的对偶问题的最优解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 02 对偶问题的基本性质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)x

22、1,x2 0 可用图解法求解可用图解法求解（P）问题，得：）问题，得：x*=(4/5，3/5)T z*=5min 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

23、*=y5*=1故故 y*=(1,0,0,0,1)w*=5第二章 线性规划的对偶理论Note:在求解一个在求解一个LPLP问题时，往往需要先考虑一下，问题时，往往需要先考虑一下，究竟是解它的原问题还是解它的对偶问题比较省事。究竟是解它的原问题还是解它的对偶问题比较省事。一般来说，求解一个一般来说，求解一个LPLP问题的计算量，是同这个问题的计算量，是同这个问题所包含约束条件的个数有密切关系的，如果约束问题所包含约束条件的个数有密切关系的，如果约束条件的个数愈多，则基可行解中基变量的个数也随之条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地迭代变换的计算量也愈大，根据经验，增多，相应地迭

24、代变换的计算量也愈大，根据经验，单纯形法的迭代次数大约是约束条件个数的单纯形法的迭代次数大约是约束条件个数的1 11.51.5倍倍.因此，当因此，当m n 则则用其对偶问题求解较好。用其对偶问题求解较好。但是但是，m=2，不一样（见书中例）不一样（见书中例）3 对偶问题的经济解释影子价格一、影子价格的概念一、影子价格的概念讨论对称形式：讨论对称形式：（P）问题问题max z=cx s.t.Ax b x 0（D）问题问题min w=yb s.t.yA c y 0 已知当（已知当（P P）问）问题求得最优解题求得最优解x*时，时，其（其（D D）问题也得到）问题也得到最优解最优解y*，且有，且有

25、bi 代表第代表第i i种资源的拥有量；对偶变量种资源的拥有量；对偶变量yi*的意义代的意义代表在资源最优利用条件下对单位第表在资源最优利用条件下对单位第i 种资源的估价。这种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。作出的贡献而作的估价。影子价格影子价格(shadow price)*11nmjjiijizc xb yw(1)由于由于*iizyb边际价格边际价格第二章 线性规划的对偶理论e.g.4 资源的合理利用问题资源的合理利用问题资源产品甲乙ABC单位利润资源限制11112354908045max z=5

26、x1+4x2 s.t.x1+3x2 90 2x1+x2 80(P)x1+x2 45 x1，x2 0min w=90y1+80y2+45y3 s.t.y1+2y2+y3 5 (D)3y1+y2+y3 4 y1，y2，y3 0c x1 x2 x3 x4 x55 4 0 0 00 0 0 -1 -3b-215cBxBx3 x1 x20 5 4 检验数 0 0 1 2 -5 1 0 0 1 -1 0 1 0 -1 225 35 10 x*=(35，10，25，0，0)Tz*=215y*=(0，1，3，0，0)w*=2153 对偶问题的经济解释影子价格二、影子价格在经营管理中的应用二、影子价格在经营管理

27、中的应用1 1、影子价格能指示企业内部挖潜的方向、影子价格能指示企业内部挖潜的方向 如如 e.g.4 中三种资源的影子价格分别为（中三种资源的影子价格分别为（0 0，1 1，3 3）重点要考虑第三种资源；重点要考虑第三种资源；2 2、影子价格在企业经营决策中的作用、影子价格在企业经营决策中的作用 企业经营决策者可以把本企业资源的影子价格与企业经营决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当当时的市场价格进行比较，当第第i 种资源的影子价格种资源的影子价格价格低于市场价格时（特别是当影子价格为零时），价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大

28、的利润；反之则企业可以卖出该种资源，以获得较大的利润；反之买入。买入。第二章 线性规划的对偶理论3 3、影子价格在新产品开发决策中的应用、影子价格在新产品开发决策中的应用 如在如在 e.g.4 中企业要生产一新产品，单件消耗三中企业要生产一新产品，单件消耗三种资源的数量为种资源的数量为（2，3，2），则新产品的价格必须），则新产品的价格必须大于大于 02+13+32=9；4 4、利用影子价格分析现有产品价格变动对资源紧缺情况的影响、利用影子价格分析现有产品价格变动对资源紧缺情况的影响 如在如在 e.g.4 中产品的售价不是（中产品的售价不是（5 5，4 4），而是），而是（5 5，5 5），则

29、影子价格为），则影子价格为1125*055011005012Byc B3 对偶问题的经济解释影子价格5 5、利用影子价格分析工艺改变后对资源影响、利用影子价格分析工艺改变后对资源影响 如在如在 e.g.4 中工艺过程改进后，使资源中工艺过程改进后，使资源 C 能节约能节约 2%，则带来经济收益是，则带来经济收益是 3 45 2%=2.7Note:1 1、以上分析都是在最优基不变的条件下进行的；、以上分析都是在最优基不变的条件下进行的；2、影子价格虽然被定义为一种价格，但是还应对影子价格虽然被定义为一种价格，但是还应对它有更为广义的理解。它有更为广义的理解。如在如在 e.g.4 中，增加约束条件

30、中，增加约束条件 x1+x2 40则对偶变量则对偶变量 y4 表示什么意思？表示什么意思？max z=5x1+4x2 s.t.x1+3x2 90 2x1+x2 80(P)x1+x2 45 x1，x2 04 对偶单纯形法一、对偶单纯形法的基本思路一、对偶单纯形法的基本思路 对偶单纯形法是根据对偶原理和单纯形法的原理而设计出对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解来求解 LP 问题的一种方法（而不能简单地将它理解为是求解问题的一种方法（而不能简单地将它理解为是求解对偶问题的方法）。对偶问题的方法）。原始单纯形原始单纯形法法 考察如下的考察如下的 LP 问题及其对偶问题问题及其对偶问

31、题 max z=cx(P)s.t.Ax=b x 0 min w=yb(D)s.t.yA c y 无符号限制无符号限制设设 B 为为(P)问题的一个基，不妨设问题的一个基，不妨设B=(p1,p2,pm)则则1(0)0BNxB bxx为为(P)问题的一个基本解；问题的一个基本解；仅当仅当 xB=B-1b 0 时时则则(0)x为一个基可行解；为一个基可行解；若此时检验数满足若此时检验数满足10Bc c B A 则则(0)x为为(P)问题一个最优解问题一个最优解原始可行性条原始可行性条件件原始最优性条原始最优性条件件第二章 线性规划的对偶理论原始单纯形法的基本思路是：原始单纯形法的基本思路是：令令 y

32、=cBB-1，代入代入原始最优性条件原始最优性条件10Bc c B A 得得 yA c对偶可行性条对偶可行性条件件原始最优性条件与对偶可行性条件等价原始最优性条件与对偶可行性条件等价Definition 1 若原问题（若原问题（P P）的一个基本解）的一个基本解 10B bx对应的检验数向量满足对应的检验数向量满足10Bc c B A 则称则称 x为（为（P P）的一个正则解）的一个正则解 从满足原始可行性条件的一个基可行解出发，经从满足原始可行性条件的一个基可行解出发，经过换基运算迭代到另一个基可行解，即总是保持过换基运算迭代到另一个基可行解，即总是保持解的可行性不变，变化的只是检验数向量解

33、的可行性不变，变化的只是检验数向量 ，它从，它从不满足不满足 00，逐步迭代到，逐步迭代到 00成立，一旦达到成立，一旦达到 00，也就得到了原问题的最优解。，也就得到了原问题的最优解。4 对偶单纯形法对偶单纯形法的基本思路是：对偶单纯形法的基本思路是：在迭代过程中，始终保持对偶问题解的可行性，在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件问题的解也满足了可行性条件,也就达到了最优解。也就达到了最优解。也即在保持正则解的正则性不变条件下，在迭代也即在保持正则解的正则性不变条件下，在迭代

34、过程中，使原问题解的不可行性逐步消失，一旦迭过程中，使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解。代到可行解时，即达到了最优解。第二章 线性规划的对偶理论二、对偶单纯形法的计算步骤二、对偶单纯形法的计算步骤 max z=cx s.t.Ax=b x 0求解如右的求解如右的LP 问题：问题：对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：Step 1 找出初始正则基，列初始对偶单纯形表；找出初始正则基，列初始对偶单纯形表；x1x2xmxB-z(0)0 0 0检验数检验数b1b2bm 1 0 0 a1m+1 a1m+2 a1n 0 1 0 a2m+1 a2m+2 a2n 0 0

35、1 amm+1 amm+2 amnc1c2cmb x1 x2 xm xm+1 xm+2 xncB c1 c2 cm cm+1 cm+2 cn cn2m1m 小于等于零小于等于零4 对偶单纯形法 Step 2 若若 b=B-1b 0，则停止计算，当前的正则解，则停止计算，当前的正则解 x=B-1b 即为原问题的即为原问题的最优解，否则转入下一步；最优解，否则转入下一步；Step 3 确定换出基变量：确定换出基变量：则取则取 xr 为换出基变量；为换出基变量；Step 4 若若 则停止计算，原问题无则停止计算，原问题无可行解，否则可行解，否则转入下一步；转入下一步；0(1,2,)rjajn Ste

36、p 5 确定换入基变量：若确定换入基变量：若min0,1jkrjrjrkajnaa则取则取 xk为换入基变量为换入基变量转转 Step 2Step 6 以以 为主元进行换基运算，得新的正则解为主元进行换基运算，得新的正则解rkamin1ribbim 令令第二章 线性规划的对偶理论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+

37、x5=12 -2x2+x3+x6=-4 xj 0 (j=1,2,6)检验数ccBxB-2 -4 -6 0 0 0 x1 x2 x3 x4 x5 x6 000 x4x5x6-2 1 -1 1 0 0 1 2 2 0 1 0 0 -2 1 0 0 1-2 -4 -6 0 0 0 b-1012-40-2 1-1/2 1/2-1/20050 x1-25/2 3/21/21070-5-1-50010 x2-2-401-1/200-1/22101/4-1/2 0-1/460011/41/215/4200-15/2-10-5/220初始正则解为初始正则解为:x0=(0,0,0,-10,12,-4)T最优解为

38、最优解为:x*=(6,2,0,0,2,0)Tz*=204 对偶单纯形法对偶单纯形法与原始单纯形法内在的对应关系对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 bi0所有所有 bi0?最优性检验最优性检验所有所有0j0?j所有所有换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解的进化原始基本解的进化可行可行 最优最优非可行非可行 可行可行(最优最优)对偶单纯形法有以下优点：对偶单纯形法有以下优点：三、交

39、替单纯形法三、交替单纯形法（1 1）初始解可以是非可行解；）初始解可以是非可行解；（2 2）当变量多于约束条件，可以减少计算工作量；）当变量多于约束条件，可以减少计算工作量；（3 3）在灵敏度分析中，有时需要用对偶单纯形法，这样可以）在灵敏度分析中，有时需要用对偶单纯形法，这样可以 使问题的处理简便。使问题的处理简便。5 灵敏度分析一、目标函数中价值系数一、目标函数中价值系数cj 的变化分析的变化分析 灵敏度分析（灵敏度分析（Sensitivity Analysis）又称为优化）又称为优化后分析（后分析（Postoptimality Analysis），就是分析研究线），就是分析研究线性规划模

40、型参数的取值变化时，最优解或最优基的影性规划模型参数的取值变化时，最优解或最优基的影响，它在应用线性规划解决实际问题的过程中是非常响，它在应用线性规划解决实际问题的过程中是非常有用的。有用的。目标函数中价值系数目标函数中价值系数 c cj j 的变化会引起检验数的变的变化会引起检验数的变化，从而影响最优性条件能否成立化，从而影响最优性条件能否成立 。1jjBjcc B p第二章 线性规划的对偶理论1 1、若、若cj 是非基变量的系数是非基变量的系数设设 cj 改变了改变了jcjjjccc即即变化后的检验数为变化后的检验数为1jjjBjccc B p要保持最优性不变，必须满足要保持最优性不变，必

41、须满足10jjjBjjjccc B pc 即 cAb检验数0B-1b-cB B-1b B NcB cN I B-1N0 cN-cB B-1N5 灵敏度分析2 2、若、若cr 是基变量是基变量xr 的系数的系数设设 cr 改变了改变了rcrrrccc即即因因 ，则，则rBcc11111112()0,0(,)BBBBBrBrrrrnccB Ac B Ac B Ac B AcB Ac B Ac aaa其中其中 是矩阵是矩阵 的第的第r 行，行，12(,)rrrnaaa1BA于是变化后的检验数为：于是变化后的检验数为：1(1,)jjBjrrjcc B pc ajmn 要求原最优性不变，则必须满足要求原

42、最优性不变，则必须满足0(1,)jjrrjc ajmn于是得到于是得到0rjajrrjca当当 时，有时，有0rjajrrjca 当当 时，有时，有因此，因此，的允许变化范围是：的允许变化范围是：rcmax0min0jjrjrrjjjrjrjacaaa 第二章 线性规划的对偶理论 ，e.g.6 佳美公司计划制造佳美公司计划制造、两种产品，已知各制两种产品，已知各制造一个单位时分别占用的设备造一个单位时分别占用的设备A A、B B的台时、调试时间、的台时、调试时间、每天设备每天设备A A、B B 的台时、调试工序每天可用于这两种产的台时、调试工序每天可用于这两种产品的能力及各售出一单位时的获利情

43、况，如表，问应怎品的能力及各售出一单位时的获利情况，如表，问应怎样组织生产才能使总利润最多。样组织生产才能使总利润最多。设备设备A(h)设备设备B(h)调试工序调试工序(h)利润利润(百元)每天可每天可用能力用能力资源资源产品产品05621121152451 1、如果产品如果产品的利润降至的利润降至1.51.5百元百元/单位，而产品单位，而产品的利润增至的利润增至2 2百元百元/单元时，最优生产计划有何变化；单元时，最优生产计划有何变化；2、如果产品、如果产品的利润不变，则产品的利润不变，则产品的利润在什么范围内变化时，则该的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。公司的最

44、优生产计划将不发生变化。5 灵敏度分析解：解：设设 x1,x2 分别表示分别表示、两种产品的生产数量，两种产品的生产数量，max z=2x1+x2 s.t.5 x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0max z=2x1+x2+0 x3+0 x4+0 x5 s.t.5 x2+x3 =15 6x1+2x2 +x4 =24 x1+x2 +x5=5 x1,x2,x3,x4,x5 0用单纯形法求解得最终单纯形表用单纯形法求解得最终单纯形表ccBxB x1 x2 x3 x4 x5 2 1 0 0 0021x3x1x2检验数0 0 1 5/4 -15/21 0 0 1/4 -1/20

45、 1 0 -1/4 3/2 15/2 7/2 3/2-17/2b 0 0 0 -1/4 -1/2得最优解为：得最优解为：x*=(7/2,3/2,15/2,0,0)T zmax=8.5(百元百元)1 1、若两产品利润均改变、若两产品利润均改变3/223/2 21444Bcc B p1/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x*=(2,3,0,6,0)Tx40 zmax=9(百元百元)ccBxB x1 x2 x3 x4 x5 2 1 0 0 0021x3x1x2检验数0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3

46、/2 15/2 7/2 3/2-17/2b 0 0 0 -1/4 -1/221c21c直接计算直接计算,得得:解得解得即产品即产品的利润的利润 c2 的变化满足的变化满足:2/3 2/3 c2 2 2 时时,该公司的最优生产计划将不发生变化该公司的最优生产计划将不发生变化4211044c 5213022c 2113c 第二章 线性规划的对偶理论二、约束条件中资源数量二、约束条件中资源数量bi 的变化分析的变化分析 检验数B-1b-cB B-1b I B-1N0 cN-cB B-1N 由最终单纯形表可知，资源数量由最终单纯形表可知，资源数量 bi 的变化，会影的变化，会影响到原最优解的可行性与目

47、标函数值。响到原最优解的可行性与目标函数值。设某个资源数量设某个资源数量 br 变化为变化为rrrbbb并假设原问题的其他系数不变，则使最终单纯形表中并假设原问题的其他系数不变，则使最终单纯形表中原问题的解相应地变化为原问题的解相应地变化为1()BxBbb其中其中12(,)(0,0)TTrmrbb bbbbb 5 灵敏度分析这时这时111()BxBbbB bBb 11111100rrrrriirriirrmmrrmmrrbabbabB bBbbabbabbabbab其中其中12(,)Trrmraaa为为B-1 的第的第 r 列，列，则必须则必须00(1,2,)Biirrxbabim即0ira当

48、当 时，有时，有irirbba 0ira当当 时，有时，有irirbba 因此因此 的允许变化范围是：的允许变化范围是：max0min0iiirriririrbbabaaa rb若要求最优基不变，若要求最优基不变，第二章 线性规划的对偶理论 e.g.7 在上述佳美公司的例子中：（在上述佳美公司的例子中：（1 1）若设备）若设备 A 和和调试工序的每天能力不变，而设备调试工序的每天能力不变，而设备 B 每天的能力增加每天的能力增加到到3232小时，分析公司最优计划的变化；（小时，分析公司最优计划的变化；（2 2）若设备）若设备A和和 B 每天可用能力不变，则调试工序能力在什么范围每天可用能力不变

49、，则调试工序能力在什么范围内变化时，问题的最优基不变。内变化时，问题的最优基不变。解：解：(1)因因设备设备 B 原原每天的能力为每天的能力为2424，所以，所以 有有080Tb 进一步有进一步有115/415/2 01001/41/28201/43/202bBb 加入到最终单纯形表，得加入到最终单纯形表，得：11()*1 0*0,2,1221 7/222 1/2BBzcBbbzcBbz 5 灵敏度分析102221/2Tbz ccBxB x1 x2 x3 x4 x5 2 1 0 0 0021x3x1x2检验数0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2

50、 15/2 7/2 3/2-17/2b 0 0 0 -1/4 -1/235/211/2-1/2-21/2因为因为用对偶单纯形法继续计算，得用对偶单纯形法继续计算，得-1/4500 x40151015-10-2-10-41-62改变为仅生产改变为仅生产5 5个单位个单位产品产品,利润利润 z*=10(2)335bb11333315/415/2001/41/2001/43/2151522710223322BxBbbbBbbbbbb 311b 由此由此,调试工序的能力应在调试工序的能力应在4小时小时6小时之间小时之间.第二章 线性规划的对偶理论三、增加一个变量三、增加一个变量 xj 的分析的分析 增

51、加一个变量在实际问题中反映为增加一种新的产品。增加一个变量在实际问题中反映为增加一种新的产品。设新变量为设新变量为11111211Tnnnnnmnxcpaaa在原最优单纯形表增加一列在原最优单纯形表增加一列11111211TnnnnmnpB paaa及检验数及检验数11111111nnBnnBnnncc B pcc pcyp若若10n则原问题最优解不变；则原问题最优解不变；10n若若则按单纯形法继续计算。则按单纯形法继续计算。5 灵敏度分析e.g.8 在佳美公司例子中，设该公司又计划推出新产品在佳美公司例子中，设该公司又计划推出新产品，生产一单位产品，生产一单位产品，所需设备，所需设备A A、

52、B B、C C调试工序的调试工序的时间分别为时间分别为3 3小时、小时、4 4小时、小时、2 2小时，该产品的预期盈利小时，该产品的预期盈利为为3 3百元百元/单位，试分析该新产品是否值得投产；如投产单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化。对该公司的最优生产计划有何变化。解：解：设新产品设新产品的生产数量为的生产数量为 x6,c6=3,p6=(3,4,2)TccBxB x1 x2 x3 x4 x5 x6 2 1 0 0 0 3021x3x1x2检验数0 0 1 5/4 -15/2 -71 0 0 1/4 -1/2 00 1 0 -1/4 3/2 215/2 7/

53、2 3/2-17/2b 0 0 0 -1/4 -1/2 1166702pBp 6730,2,10102 x6321/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-1N0 cN-cB B-

54、1N此时，只此时，只影响问题影响问题的最优性的最优性设设非基变量非基变量 xj 的系数列向量的系数列向量 pj 改变为改变为jjjppp 则变化后的检验数为则变化后的检验数为11jjBjjBjjjjcc B pcc Bppy p y=cBB-1是原问题的是原问题的对偶可行解对偶可行解要使原最优基要使原最优基 B 保持不变，保持不变，特别，当特别，当 时，由上式得时，由上式得0,0Tjijpaiijjya当当 时，时，0iy jijiay0iy 当当 时，时，jijiay0jjjy p 即则必须则必须5 灵敏度分析2 2、基变量、基变量 xj 的系数列向量的系数列向量 pj 的变化分析的变化分析

55、 对于最优基对于最优基 B 而言，当而言，当基变量基变量 xj 的系数列向量的系数列向量 pj 发生变化时，将使相应的发生变化时，将使相应的B，B-1-1都发生变化，因此，都发生变化，因此，它不仅影响现行最优解的可行性，也影响它的最优性。它不仅影响现行最优解的可行性，也影响它的最优性。e.g.9 在佳美公司的例子中，若产品在佳美公司的例子中，若产品每单位需设备每单位需设备A A、B B和调试工时和调试工时8 8小时、小时、4 4小时、小时、1 1小时，该产品的利润变小时，该产品的利润变为为3 3百元百元/单位，试重新确定该公司最优生产计划。单位，试重新确定该公司最优生产计划。解：解：先将生产工

56、时变化后的产品先将生产工时变化后的产品看作是一种新产品，看作是一种新产品，2x生产量为生产量为 ，直接计算，直接计算 ：22p 和 第二章 线性规划的对偶理论将其加入原最终单纯形表将其加入原最终单纯形表:281 1330,44 221 215/415/2811/201/41/241/201/43/211/2p ccBxB x1 x2 x2 x3 x4 x5 2 1 3 0 0 0021x3x1x2检验数0 0 11/2 1 5/4 -15/21 0 1/2 0 1/4 -1/20 1 1/2 0 -1/4 3/2 15/2 7/2 3/2-17/2b0 0 3/2 0 -1/4 -1/21/2

57、第二章 线性规划的对偶理论将其加入原最终单纯形表将其加入原最终单纯形表:281 1330,44 221 215/415/2811/201/41/241/201/43/211/2p ccBxB x1 x2 x3 x4 x5 2 1 0 0 0021x3x1x2检验数0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/2-17/2b 0 0 0 -1/4 -1/23/223/2 21/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x40ccBxB x1 x2 x3 x4 x5 2 3 0 0 002

58、3x3x1x2检验数0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/2-17/2b 0 0 0 -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(百元百元).).5 灵敏度分析五、增加新约束条件的分析五、增加新约束条

59、件的分析 增加一个约束条件在实际问题中相当增添一道工增加一个约束条件在实际问题中相当增添一道工序。设在原规划线性问题中，增加一个新的约束条件序。设在原规划线性问题中，增加一个新的约束条件1,1 11,221,1mmmnnmaxaxaxb(*)则则首先把已求得的原问题的最优解首先把已求得的原问题的最优解*12(,)Tnxx xx 代入新增加的约束条件代入新增加的约束条件(*)，如果条件满足，则原，如果条件满足，则原问题的最优解问题的最优解 x*仍为新问题的最优解，结束。如果仍为新问题的最优解，结束。如果条件不满足，则将新增加的约束条件直接反映到最终条件不满足，则将新增加的约束条件直接反映到最终单

60、纯形表中再进一步分析。单纯形表中再进一步分析。第二章 线性规划的对偶理论e.g.10 仍以佳美公司为例，设产品仍以佳美公司为例，设产品、经调试后，经调试后，还需经过一道环境试验工序，产品还需经过一道环境试验工序，产品每单位须环境试每单位须环境试验验3 3小时，产品小时，产品每单位须每单位须2 2小时，又环境试验工序每小时，又环境试验工序每天生产能力为天生产能力为1212小时，试分析增加该工序后的佳美公小时，试分析增加该工序后的佳美公司最优生产计划。司最优生产计划。解：解：ccBxB x1 x2 x3 x4 x5 2 1 0 0 0021x3x1x2检验数0 0 1 5/4 -15/21 0 0

61、 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/2-17/2b 0 0 0 -1/4 -1/2增加约束条件增加约束条件 3x1+2x2 12 原问题的最优原问题的最优解解 x1=7/2x2=3/2 不满足不满足环环境试验工序约束，境试验工序约束，故将约束条件故将约束条件 3x1+2x2+x6=12加入单纯形表中加入单纯形表中ccBxB x1 x2 x3 x4 x5 x6 2 1 0 0 0 00210 x3x1x2x6 检验数 0 0 1 5/4 -15/2 0 1 0 0 1/4 -1/2 0 0 1 0 -1/4 3/2 0 3 2 0 0 0 115/2 7/2 3/2 12-17/2b0 0 0 -1/4 -1/2 00-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(百元百元)完 第二章第二章 线性规划的对偶理论线性规划的对偶理论