第二章 对偶问题

1、第二章 对偶问题与灵敏度分析,重点与难点：1、对偶问题的定义，对偶定理，对偶问题最优解的经济含义，由最优单纯形表求对偶问题最优解；2、对偶单纯形法的特点，对偶单纯形法求解；3、灵敏度分析：价值系数cj发生变化，右端常数bi发生变化，增加一个变量，增加一个约束，A中对应非基变量的一列元素发生变化。,OR1,1,第二章 对偶问题与灵敏度分析,要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析,OR1,2,2.1 对偶问题,2.1.1 对偶问题的提出 回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判

2、，我们的（资源的）价格底线是多少？,OR1,3,对偶模型,设每个工时收费Y1元，每设备台时费用Y2元，每单位原材料收费Y3元。 出租收入不低于生产收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120 目标：=360y1+200y2+300y3 出租收入越多越好？还是至少不低于某数？,OR1,4,原问题与对偶问题之比较,原问题： 对偶问题： maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 4y1+5y2+10y3 120 3X1+10X2 300 y1 0, y2 0, y3

3、 0 X10 X20,OR1,5,2.1.2对偶规则,原问题一般模型： 对偶问题一般模型： maxZ=CX min =Yb AX b YA C X 0 Y 0,OR1,6,对偶规则P57,.,原问题（或对偶问题）,对偶问题（或原问题）,目标函数maxz,目标函数min,n个,n个,变量,约束条件, 0,0,无约束,约束条件,变量,m个,m个, 0,0,无约束,约束条件右端项,目标函数变量的系数,目标函数变量的系数,约束条件右端项,OR1,7,例题2：写出下列原问题的对偶问题,OR1,8,例题3：写出以下模型的对偶问题,例题3 max =7y1+4y2-2y3 minZ=3x1+2x2-6x3+

4、x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x4 4 -4y1+ 2y2 -6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5无限制 y1 0y2 0y3 无约束,OR1,9,例题4：写出以下模型的对偶问题,OR1,10,例4的解法,OR1,11,2.1.3对偶问题的基本性质,1.对称性：对偶问题的对偶问题是原问题。 2.弱对偶性：若 是最大化原问题的可行解， 是对偶问题的可行解，则存 。 3.无界性：若原问题为无界解，则对偶问题无可行解。（注：该性

5、质的逆不存在。当原问题无可行解时，其对偶问题可能为无界解，也可能无可行解。） 4.最优解定理：若两互为对偶的问题均有可行解，且可行解对应的目标函数值相等，则该可行解分别为他们的最优解。,OR1,12,性质3的应用P60,已知LP问题： 试用对偶理论证明上述LP问题无最优解。,OR1,13,5.对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1。 6 .互补松弛性：在LP的最优解中，若对应某一约束条件的对偶变量值不为零，则该约束条件取严格等式；反之，若约束条件取严格等式，则其对应的对偶变量一定为零。（另一解释：在互为对偶的两

6、个问题中，若原问题的某个变量取正数，则对偶问题相应的约束条件必取“”式；若原问题的某个约束条件取不等式，则对偶问题相应的变量为零。）,OR1,14,性质6的应用P60,已知线性规划问题： 已知其对偶问题的最优解为： 试用对偶理论找出原问题的最优解。,OR1,15,7.设原问题是maxz=CX,AX+Xs=b; X, Xs0,其对偶问题是min=Yb,YA-Ys=C, Y, Ys 0,则原问题单纯形表的检验数行对应其对偶问题的一个基解CBB-1 （符号相反），其对应关系如下：,OR1,16,非基变量,基变量,XB,XN,XS,0,XS,b,B,N,I,CB,CN,0,CB,CN,初始单纯形表,X

7、N,XB,XS,I=B-1B,B-1N,B-1,CB,XB,B-1b,CB,CN,0,0,CN-CBB-1N,_-CBB-1,互为对偶问题在单纯形表间关系：1、原问题的基解对应于对偶问题的检验数。2、原问题的松弛变量对应对偶问题的决策变量。3、原问题的基变量对应对偶问题的非基变量。,OR1,17,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？ 回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的（资源的）价格底线是多少？,OR1,18,y1,y2,y3,OR1,19,2.1.4对

8、偶最优解的经济解释影子价格,OR1,20,另一种直观的解释,OR1,21,影子价格的应用,情况 某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。,情况 直接用影子价格与市场价格相比较，进行决策，决定是否买入该资源。,即：影子价格所含有的信息：1、资源紧缺状况；2、确定资源转让基价；3、取得紧缺资源的代价。,OR1,22,对偶单纯形法,设有问题maxZ=CX ， AX b ， X 0 又设B是其一个基，当非基变量都为0时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设第i个为负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对

9、偶单纯形法来进行求解。,OR1,23,对偶单纯形法的计算步骤P62,（1）根据LP问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，则进行以下计算。 （2）确定换出变量：将B-1b中最小的负分量所对应的变量确定为换出变量。 （3）确定换入变量：检查换出变量所在行（第L行）的各系数aLj。若所有的aLj 0，则无可行解 ，停止计算。若存在aLj 0，则计算 ，将其最小值所对应的变量作为换入变量。 （4）进行迭代计算。 重复14步，直至得到最优解为止。,OR1,24,对偶单纯形法举例,利用对偶单纯形

10、法求解以下线性规划问题：,OR1,25,cj,CB,XB,b,x1,x2,x3,x4,x5,-1,-3,0,0,0,-2 -3 -1,-1 -2 -2,1 0 0,0 1 0,解法,0 0 1,-3 -4 -1,x3 x4 x5,0 0 0,-1,-3,0,0,0,cj-zj,1/3,3/2,x3 x1 x5,0 1 0,1/3 2/3 -4/3,1 0 0,-2/3 -1/3 -1/3,0 0 1,cj-zj,-1/3 4/3 1/3,0,-7/3,0,-1/3,0,1/2,0 -1 0,x4 x1 x5, 3/2 1/2,0 1 0,-1/2 -3/2,-3/2 -1/2 -1/2,1 0

11、 0,0 0 1,0 -1 0,cj-zj,0,-5/2,-1/2,0,0,-3/2,此时所有的B-1b均0 ，且所有的cj-zj均0，此时已得到最优解为： X*=(3/2,0,0,1/2,1/2)T Z*=-3/2,OR1,26,总结：对偶单纯形法与单纯形法的比较,单纯形法,对偶单纯形法,保持,B-1b,0,所有的,cj-zj0,最优解时 要求,所有的,cj-zj0,B-1b,0,OR1,27,对偶单纯形法的应用时机,要求最大化时，在单纯形表中：如果检验数均非正，而 列中有负值，此时用对偶单纯形法求解。若所有 ， 中有正值，则用单纯形法求解；若 列中有负值，且 中有正值，则必须引入人工变量，

12、建立新的单纯形表，重新计算。,B-1b,B-1b,0,cj-zj,B-1b,cj-zj,OR1,28,对偶单纯形法的优点P64,（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以直接计算。 （2）当变量多于约束条件，对这样的LP问题，用对偶单纯形法计算可以减少计算工作量。因此，对变量较少，而约束条件很多的LP问题，可以先将它变换成对偶问题，然后用对偶单纯形法求解。 （3）在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。,OR1,29,2.2灵敏度分析（考研时常考的知识点）,灵敏度分析通常有两类问题：是当C,A,b中某一部分数据发

13、生给定的变化时，讨论最优解与最优值怎么变化；是研究C,A,b中数据在多大范围内波动时，使原有最优基仍为最优基，同时讨论此时最优解如何变动？,灵敏度分析的两把尺子： j =Cj-CBB-1pj 0； XB= B-1b 0,OR1,30,2.2.1右端项bi变化的灵敏度分析,bi变化到什么程度可以保持最优基不变？ 用尺度xB= B-1b 0。 问题：为什么不用尺度j =Cj-CBB-1pj 0？,OR1,31,例题：求以下模型中第二个约束条件右端项b2的变化范围。,maxZ=70X1+120X2 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20,OR1,32,

14、OR1,33,解：从最优单纯形表得出：XB=(20,24,84)T 最优基为： 注意：应为初始数据。为什么？ 还可以从单纯形表中找出B-1.,OR1,34,设b2由200变为200 b2，则b由 由此得到迭代后的单纯形表：,cj,70,120,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,i,0 1 0,0 0 1,1 0 0,-3.12 0.4 -0.12,1.16 -0.2 0.16,84-3.12 b2,20+0.4 b2,24-0,12 b2,x3 x1 x2,0 70 120,zj,j,4280+13.6 b2,70,120,0,13.6,5.2,0,0,0,-13.6,

15、-5.2,OR1,35,上述解是最优解，必须是可行解： 即： 解得：50 b2 26.9。 可知右端项系数b2的变化范围是: （20050） （20026.9),OR1,36,在此范围内j 0， B-1b 0，最优解仍有效，即最优解的基变量不变，最优解为： 最优值为：Z*=4280+13.6 b2,OR1,37,2.2.2目标函数中价值系数cj的灵敏度分析,分cj是非基变量的系数还是基变量的系数两种情况来讨论。 若cj是非基变量xj的系数，此时，当cj变化 cj后，要保证最终表中这个检验数仍小于或等于零即可。,若cj是基变量xj的系数，则引起的变化较大。见例题。,OR1,38,例题：在模型例1

16、中，求基变量x2的系数变化范围。 解：本例的最优单纯形表如下：,0 70 120,OR1,39,基变量系数c2由120变为120 c2后，可以得到迭代后的单纯形表。,cj,CB,XB,b,x3 x1 x2,84 20 24,x1,x2,x3,x4,x5,i,70,120 c2,0,0,0,0 1 0,0 0 1,1 0 0,-3.12 0.4 -0.12,1.16 -0.2 0.16,j,428024 c2,0,0,0,-13.6 +0.12 c2,-5.2-0.16 c2,0 70 120+ c2,OR1,40,要保持最优解，必须使j 0， 即： 13.6+0.12 c2 0 -5.2-0.16 c2 0 解得32.5 c2 113.3 由此可知， c2 的变化范围为： （12032.5)(120+113.3)，即87.5 c2 233.3。,OR1,41,2.2.3技术系数aij的灵敏度分析,一般地，发生变化的系数大多是非基变量的系数。它的改变不会影响到现行最优解的可行性，如果要有影响的话，那将是对现行解是否还是保持最优的问题。分两种情况进行讨论(1)非基列向量的改变；（2）某一元素的改