纯形法的灵敏度分析与对偶对偶问题.ppt

分别用大M法和两阶段法求解下列线形规划问题,并指出解的类型,minZ=2x1+3x2+x3 x1+4x2+2x38S.t.3x1+2x2 6 x1,x2,x3 0时间:1:402:10,初始单纯形表格,最终单纯形表格,第六章 单纯形法的灵敏度分析与对偶,DUAL,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,1 单纯形表的灵敏度分析(重点.难点.掌握)2 线性规划的对偶问题(重点.理解.掌握)3 对偶规划的基本性质(重点.应用)4 对偶单纯形法(难点.掌握-前面已讲),学习重点与难点,1 单纯形表的灵敏度分析(重点.难点.掌握),2 线性规划的对偶问题,一、对偶问题实例,例1 某工厂生产甲、乙两种产品，要消耗A、B和C三种资源，已知每件产品对这三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润如表所示.问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？,该问题的数学模型为：max Z=1500 x1+2500 x2 s.t.3x1+2x2 65 A资源 2x1+x2 40 B资源 3x2 75 C资源 x1,x2 0,考虑：1、定价不能太高？2、定价不能太低？,假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？,咋办？,设A、B、C资源的出售价格分别为 y1、y2和y3,1500,2500,0,原问题：max Z=1500 x1+2500 x2 s.t.3x1+2x2 65 A资源 2x1+x2 40 B资源 3x2 75 C资源 x1,x2 0,对偶问题：Min W=65 y1+40 y2+75 y3 s.t.3y1+2 y2 1500 2y1+y2+3y3 2500 y1,y2,y3 0,210 3,A=,654075,b=,1500 2500,c=,2 02 1 3,A=,15002500,b=,65 40 75,c=,max,min,对偶问题 Min W=bTY s.t.ATYCT Y 0,max,b,A,C,CT,AT,bT,min,m,n,m,n,二、对偶问题的形式 1、对称型对偶问题,原问题 Max Z=cX s.t.AXb X 0,对偶关系表,由表可以看出：从行看是原问题（），从列看是对偶问题（），两个问题的变量系数矩阵互为转置矩阵。原问题（）的常数项是对偶问题（）的目标系数，反之，原问题（）的目标系数是对偶问题（）的常数项。原问题（）有n个决策变量，对偶问题（）有n个约束方程；原问题有m个约束方程，对偶问题就有m个决策变量。原问题的约束是“”型，对偶问题的约束是“”型。原问题的目标函数是求极大，对偶问题的目标是求极小。,max Z5x1+4x2,例2 请给出下列线性规划问题的对偶问题：,对称型线性规划问题,怎么样简单吧,2、非对称型对偶问题 表 对偶变换的规则,约束条件的类型(规范与否)与非负条件相互对应非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的,好难记呀！,例3：,Min z=5x1+25x2 7x1+75x2 98s.t.5x1+6x2=78 24x1+12x254 x10、x2 0,Max w=98y1+78y2+54y37y1+5y2+24y3 5s.t.75y1+6y2+12y3 25 y1 0、y2无限制、y30,怎么样，没问题吧！,对称形式线形规划问题为:,Max Z=cX s.t.AXb X 0,加上松弛变量化为标准形后为:,Max Z=cX+0Xs s.t.AX+IXs=b X 0,Xs 0,3 对偶规划的基本性质,一、单纯形法计算的矩阵描述:,检验数j,当迭代若干步，基变量为X B时，新的单纯形表:,b,XS,0,Cj,X B XN XS,B N I,CB CN 0,CB CN 0,检验数j,B-1b,XB,CB,Cj,X B XN XS,I B-1N B-1,0 CN-CB B-1N-CB B-1,CB CN 0,初始单纯形表为:,maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36,举例,最优基,最优基的逆,最优基和最优基的逆,maxZ=2x1+x2 5x215 s.t.6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3=15s.t.6x1+2x2+x4=24 x1+x2+x5=5 x1,x2,x3,x4,x5 0,例4：对称形线性规划问题：,标准型：,j,x3x1x2,021,0 0 0-1/4-1/2,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x4x5,000,15 0 5 1 0 0,24 6 2 0 1 0,5 1 1 0 0 1,2 1 0 0 0,初始单纯形表,最终单纯形表,B=(P3,P1,P2),15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,B-1=(P3,P4,P5),初表中,终表中,minZ=2x1+3x2+x3 x1+4x2+2x38S.t.3x1+2x2 6 x1,x2,x3 0,初始单纯形表格,最终单纯形表格,maxZ=50 x1+100 x2 x1+x2 300 s.t.2x1+x2 400 x2 250 x1,x2 0,maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 s.t.2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0,例5：对称形线性规划问题：,x1 x2 x3 x4 x5,CB XB b,CB,j,x3x4x5,000,300 1 1 1 0 0,400 2 1 0 1 0,250 0 1 0 0 1,50 100 0 0 0,原问题初始单纯形表,50 100 0 0 0,已知最优基的基变量为x1，x4，x2，请直接写出该线性规划问题的最终单纯形表。并给出其对偶问题的最优解,最优基为 B=（p1，p4，p2）=,B-1=（p3，p4，p5）=,b=B-1 b=,=,j=Cj-CBB-1 P j,x1 x2 x3 x4 x5,CB XB b,CB,j,x1x4x2,500100,50 1 0 1 0-1,50 0 0-2 1 1,250 0 1 0 0 1,0 0-50 0-50,原问题最终单纯形表,50 100 0 0 0,原问题初始单纯形表,x1 x2 x3 x4 x5,CB XB b,CB,j,x3x4x5,000,400 2 1 0 1 0,250 0 1 0 0 1,50 100 0 0 0,50 100 0 0 0,300 1 1 1 0 0,检验数j,当迭代若干步，基变量为X B时，新的单纯形表:,b,XS,0,Cj,X B XN XS,B N I,CB CN 0,CB CN 0,检验数j,B-1b,XB,CB,Cj,X B XN XS,I B-1N B-1,0 CN-CB B-1N-CB B-1,CB CN 0,初始单纯形表为:,对应初始单纯表中的单位矩阵I，迭代后的单纯形表中为B-1初始单纯表中的基变量Xs=b，迭代后的单纯形表中为XB=B-1b初始单纯表中的约束系数矩阵为：A,I=B,N,I 迭代后的单纯形表中约束系数矩阵为：B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1若初始矩阵中变量xj的系数向量为Pj，迭代后为Pj，则有：Pj=B-1 Pj,小结,当B为最优基时，迭代后的单纯表中检验数：CN-CB B-1N 0-CB B-1 0因XB的检验数可写 为：CB-CB B-1B 故可重写为：C-CB B-1A 0-CB B-1 0CB B-1称为单纯形乘子。若令YT=CB B-1 则：C-YT A 0 AT Y C所以：AT Y CT Y 0,可见检验数的相反数恰好是其对偶问题的一个可行解，将这个解代入对偶问题的目标函数，有：,W=YTb=CBB-1b=Z,当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，根据对偶问题的基本性质，将看到这时对偶问题的解也为最优解。所以从最优解的单纯形表中同时可以得到其对偶问题的最优解。,maxZ=2x1+x2 5x215 s.t.6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3=15 y1 s.t.6x1+2x2+x4=24 y2 x1+x2+x5=5 y3 x1,x2,x3,x4,x5 0,minW=15y1+24y2+5y3 6y2+y3-y4=2 x1s.t.5y1+2y2+y3-y5=1 x2 y1,y2,y3,y4,y5 0,minW=15y1+24y2+5y3 6y2+y32s.t.5y1+2y2+y3 1 y1,y2,y3 0,例5：对称形线性规划问题：,对偶问题：,标准型：,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,y1 y2 y3 y4 y5,CB XB b,CB,j,-15-24-5 0 0,y2y3,-24-5,1/4-5/4 1 0-1/4 1/4,1/2 15/2 0 1 1/2-3/2,-15/2 0 0-7/2-3/2,-y4-y5-y1-y2-y3,-x3-x4-x5-x1-x2,原问题最终单纯形表,对偶问题最终单纯形表,松弛变量,对偶变量,剩余变量,决策变量,例6、利用原问题的最优单纯形表求解对偶问题的最优解,s.t.100 100 0解:对偶问题为 s.t.4 3 7 0,最终单纯形表格,x4x5松弛变量,可见原问题的最优解为:X*=(0,25,25)T 其对偶问题的最优解为:y*=(1/2,2)T,为了便于讨论，下面不妨总是假设:,定理1（对称性定理）对偶问题的对偶是原问题。,根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为原问题，而把另一个称为其对偶问题。,:,对偶问题,=,:,原问题,二、对偶问题的基本性质:,证明:由前面可知对偶问题为:,等价于该问题:,可见此问题为对称型的规划问题,其对偶问题表示为:,令Z=-f,则化简为:,即为原问题,可见对偶问题的对偶是原问题。证毕,定理 2（弱对偶性定理）对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值。,证:假设X0,Y0分别为原问题和对偶问题的可行解,故有:,=,-(1),-(2),因为Y0是对偶问题的可行解,用Y0T左乘(1)得:Y0T AX0 Y0T b转置得:X0T ATY0 bT y0 因为X0是原问题的可行解,用X0左乘(2)得:X0T ATY0X0T CT 转置得:Y0T AX0 CX0可见CX0 Y0T AX0 Y0T b=bT Y0 即CX0 bT Y0,例7、应用弱对偶定理，证明下列线性规划问题的最大值不超过1.,证明：该线性问题的对偶问题为：,弱对偶定理推论,推论 1 最优解判别定理,若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相 应问题的最优解,证：由弱对偶定理可知结论是显然的,即CX0=bTY0 CX,bTY0=CX0 Yb。证毕。,推论 2 如果原max(min)问题为无界解，则其对偶 min(max)问题无可行解(反之不然),maxZ=x1+x2 x1-x2-1s.t.-x1+x2-1 x1,x20,minW=-y1-y2 y1-y2 1s.t.-y1+y2 1 y1,y2 0,原问题和对偶问题同时无可行解,推论 3原问题(max)的任何可行解目标函数值是其对偶问题(min)目标函数值的下界；原问题(min)的任何可行解目标函数值是其对偶问题(max)目标函数值的上界推论 4 如果原问题max(min)有可行解，其对偶 问题min(max)无可行解，则原问题为无界解,例8、应用对偶理论证明下列线性规划问题目标函数值无界.,s.t.,证明：,是线性问题的可行解，即该问题存在可行解；,又其对偶问题为：,定理 3 主对偶定理(强对偶性定理)如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解所对应的目标函数值相等。,证:由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。设 X0 为原问题的最优解，它所对应的基矩阵是 B，X0=B1 b，则其检验数满足 C CBB1A 0 令 Y0=CBB1，则有 Y0 A C 显然Y0为对偶问题的可行解。因此有对偶问题目标函数值,W=Y0b=CBB1 b 而原问题最优解的目标函数值为 Z=CX0=CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。,定理 4 互补松弛定理定理 设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0=V0 X0=0,证：由定理所设，可知有 A X0+U0=b X0,U0 0(1)Y0 A V0=C Y0,V0 0(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0+V0 X0=Y0 b C X0若 Y0 U0+V0 X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。,例9、考虑下列原始线性规划,(1)写出其对偶问题；(2)已知（3,2,0）是上述原始问题的最优解，根据互补松弛定理，求出对偶问题的最优解；(3)如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格.,解：（1）对偶问题：,（2）由题知原问题的最优解为,由互补松弛定理得：在对偶问题中对应第一，二个约束为紧约束，第三个约束条件为松约束，即，,对偶规划问题的最优解,（3）影子价格为 y1=4,-1,(4,-1),例 10：利用互补松弛定理,原问题检验数与对偶问题的解的总结在主对偶定理(强对偶性)的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,4 对偶单纯形法,一、对偶单纯形法的基本思路,单纯形迭代要求每步都是基本可行解达到最优解时，检验数 cjzj 0(max)但对于所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cjzj 0(max),0,0？,二、对偶单纯形法的计算步骤,对某线形规划问题存在一个对偶问题的可行基，即必须所有的cj-zj0，bi的值不要求全为正:,1、确定换出变量（离基变量）在小于0的b中找出最小者，其所对应的变量xr为换出变量2、确定换入变量（进基变量）=minj/arj|arj0=k/ark其所对应的变量xk为换入变量3、确定主元素：ark为主元素4、用换入变量替换换出变量，继续迭代得到一个新的基5、检查是否所有的bi 0，如是，找到了两者的最优解，否则返回第一步循环进行。,例12：对偶单纯形法的计算过程,x1 x2 x3 x4 x5,CB XB b,CB,j,-15-5-11 0 0,x4x5,0 0,-5-3-2-2 1 0,-4-5-1-2 0 1,-15-5-11 0 0,初始单纯形表,15/3 5/2 11/2-,j,x2x5,-5 0,5/2 3/2 1-1-1/2 0,-3/2-7/2 0-1-1/2 1,-15/2 0-6-5/2 0,15/7-6 5-,j,-5-15,13/7 0 1 4/7-5/7 3/7,3/7 1 0 2/7 1/7-2/7,0 0-27/7-10/7-15/7,x2x1,最终单纯形表,负数中最小者,比值中最小者,检验数j,当迭代若干步，基变量为X B时，新的单纯形表:,b,XS,0,Cj,X B XN XS,B N I,CB CN 0,CB CN 0,检验数j,B-1b,XB,CB,Cj,X B XN XS,I B-1N B-1,0 CN-CB B-1N-CB B-1,CB CN 0,初始单纯形表为:,1 单纯形表的灵敏度分析,灵敏度分析所研究的问题是，当某一规划的最优解已知的情况下，某数据发生变化后对最优解产生的影响。原数据发生变化的主要原因可能有原始数据不可靠或准确度不高，实际问题的条件模糊不清或被忽略，最优解执行一段时间后环境条件发生变化等。,因此我们有必要研究以下问题:,当某些系数变化，最优解改变多少?当增加或减少变量，最优解改变多少?当增加或减少约束条件时，问题的最优解改变多少?最优解不改变时，某些系数的允许变化范围又有多大?,系数包括：目标函数中的价值系数cj、约束条件中 的常数项bi、约束条件中的技术系数aij。,灵敏度分析的步骤如下：,将参数的改变通过计算反映到最终单纯表上来。检查原问题是否仍为可行解；检查对偶问题是否仍为可行解；按下表所列情况的出结论或决定继续计算的步骤,可行解 可行解,问题的最优解或最优基不变,可行解 非可行解,非可行解 可行解,非可行解 非可行解,用单纯形法继续迭代求最优解,用对偶单纯形法继续迭代求最优解,引进人工变量，编制新的单纯形表重新计算,灵敏度分析的主要内容,一、目标函数系数的灵敏度分析二、约束条件的常数项的灵敏度分析三、增加或减少决策变量的灵敏度分析四、系数矩阵的灵敏度分析五、增加或减少约束条件的灵敏度分析,一、目标函数系数的灵敏度分析,目标函数中价值系数Cj的变化只会引起检验数j的变化，所以将Cj的变化直接反映到最终单纯形表中，只可能出现表中前两种情况。,例13 佳美公司计划制造、两种产品，已知各制造一个单位产品时，分别占用的设备A、B的台时、调试时间、每天设备A、B的台时、调试工序可用于这两种产品的能力及各售出一单位时的获利情况，如表所示。1、问应怎样组织生产才能使总利润最多？2、如果产品的利润降至1.5百元/单位，而产品的利润增至2百元/单元时，最优生产计划有何变化？3、如果产品的利润不变，则产品的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,，,解：设分别表示、两种产品的生产数量，可建立如下线性规划模型：,maxZ=2x1+x2 5x215 s.t.6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3=15 s.t.6x1+2x2+x4=24 x1+x2+x5=5 x1,x2,x3,x4,x5 0,y,Y1Y2y3,j,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,可见原问题具有唯一最优解：,思考：对偶问题的最优解和最优值？,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x4x5,000,15 0 5 1 0 0,24 6 2 0 1 0,5 1 1 0 0 1,0 0 0-1/4-1/2,初表,终表,将产品、的利润变化直接反映到最终单纯形表中得表，,因非基变量的检验数大于零，故需继续用单纯形法迭代计算,2、如果产品的利润降至1.5百元/单位，而产品的利润增至2百元/单元时，最优生产计划有何变化？,x1 x2 x3 x4 x5,CB XB b,CB,j,0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,2 1,1.5 2,01.5 2,0 0 0 1/8-9/4,CB XB b,CB,j,0 0 0,x3x1x2,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,1.5 2,01.5 2,0 0 0 1/8-9/4,x1 x2 x3 x4 x5,614-,j,x4x1x2,6 0 0 4/5 1-6,2 1 0-1/5 0 1,3 0 1 1/5 0 0,01.5 2,0 0-1/10 0-3/2,可见变化后的问题具有唯一最优解,X*=(2,3)T,3、如果产品的利润不变，则产品的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,x1 x2 x3 x4 x5,CB XB b,CB,j,2 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,1,解：设产品的利润为c2元，反映到最终单纯形表中，得表：,c2,c2,0 0 0-1/2+1/4 c2 1-3/2 c2,为使表中的解仍为最优解，应有：-1/2+1/4 c2 0 1-3/2 c2 0,即产品的利润的变化范围是：2/3，2,解得：2/3 c 22,二、约束条件的常数项的灵敏度分析,在现实问题中，约束条件的右端常数项，往往代表资源的限制量。一般来说，资源的限制量不是一成不变的，而是随生产条件、市场供应情况进行变动。所以人们常常想知道，对于一个确定的优方案，当资源增加或减少多少时，对方案的影响将有多大。这种类型的灵敏度分析就是处理该类问题的方法。现假定问题的第l种资源限制。由于常数项的改变，对最优判别准则的检验数 无关。即是说，最优基对应的单纯变量表中的最后一行不发生变化。而表中的基变量 是否可行还需讨论。,所以只可能出现表中1、3两种情况,例14 在上述佳美公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化；（2）若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变.,解：（1）由题意得变化后的b为b:,所以有,B-1 b=,B-1=,由最终单纯形表得原最优基的逆矩阵:,b=,=,将其反映到最终单纯形表中,CB XB b,CB,j,x3x1x2,021,0 0 1 5/4-15/2,1 0 0 1/4-1/2,0 1 0-1/4 3/2,0 0 0-1/4-1/2,x1 x2 x3 x4 x5,2 1 0 0 0,j,15 0 5 1 0 0,5 1 1 0 0 1,2 0-4 0 1-6,0-1 0 0-2,x3x1x4,0 2 0,35/2 11/2-1/2,可见变化后的问题具有唯一最优解:X*=(5,0)T Z*=10,第二种解法 利用变化率,所以有,B-1 b=,=,将其反映到最终单纯形表中,因为B-1 b=B-1(b+b)=B-1 b+B-1 b,终表中的第三列,b=,=b+b,=,+,解：,CB XB b,CB,j,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,x1 x2 x3 x4 x5,2 1 0 0 0,j,15 0 5 1 0 0,5 1 1 0 0 1,2 0-4 0 1-6,0-1 0 0-2,x3x1x4,0 2 0,+10=35/2+2=11/2-2=-1/2,可见变化后的问题具有唯一最优解:X*=(5,0)T Z*=10,（2）若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变.,解法一:设调试工序每天可用能力为b3小时,B-1 b=,=,要使问题的最优基不变，只要其新的b列数全部大于等于零，即：,45-15/2 b3 06-1/2 b3 0-6+3/2 b3 0,4b36,由此调试工序的能力应在46小时之间,b=,解法二：设调试工序每天可用能力为5+b3,B-1 b=,=,将其反映到最终单纯形表中,其b列数字为:,B-1 b=,当B-1 b0时,问题的最优基不变,解得-1 b3 1,45+b3 6,由此调试工序的能力应在46小时之间,因为B-1 b=B-1(b+b)=B-1 b+B-1 b,终表中的第三列,b=,=b+b,=,+,三、决策变量的灵敏度分析,在讨论一个规划问题时，从资源的充分利用角度考虑，有时认为多安排一些生产项目是有利的，这反映在线性规划模型上是增添决策变量的问题。另一方面当规划执行一段时间后，资源的供应不能满足要求时，有时也要考虑少安排一些生产项目是有利的，这反映在数模上就是减少决策变量的问题。所以，决策变量个数的变化有两种情况，一是增多，一是减少。现分别在下面讨论。,(1)增加决策变量的灵敏度分析,设已知增加的新变量xj的目标函数为cj，相应的约束系数为aij（或表示为Pj），其分析步骤为：,2、计算检验数,1、计算 Pj=B-1Pj,3、若 j0，原最优解不变，只需将计算得到Pj的j和直接写入最终单纯形表中；若 j0，则按单纯形法继续迭代计算找出最优解,例15、在佳美公司例子中，设该公司又计划推出新产品，生产一单位产品，所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3百元/单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化。,解：设新产品的生产数量为x6件，有：,将其反映到最终单纯形表中得表,P6=B-1P6=,=,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,j,51/4 0 7/2 1 3/8-9/4 0,7/2 1 0 0 1/4-1/2 0,3/4 0 1/2 0-1/8 3/4 1,0-1/2 0-1/8-5/4 0,x3x1x6,0 2 3,可见变化后的问题具有唯一最优解:X*=(7/2,0)T Z*=37/4,比原方案17/2获利多，所以值得生产,-7,0,2,x6,3,1,(2)减少决策变量的灵敏度分析,若减少的决策变量不在最优解的基变量之中，是非基变量，对这种情况可以认为决策变量本来就是多余的。减少这个变量不影响最优解、最优值。,j,-5-15,13/7 0 1 4/7-5/7 3/7,3/7 1 0 2/7 1/7-2/7,0 0-27/7-10/7-15/7,x2x1,x1 x2 x3 x4 x5,CB XB b,CB,-15-5-11 0 0,减少决策变量x3，最优生产计划如何？,(2)减少决策变量的灵敏度分析,若减少的决策变量是基变量，要考虑去掉这个变量的影响，可用单纯形法或对偶单纯形法重新求解。,j,-5-15,13/7 0 1 4/7-5/7 3/7,3/7 1 0 2/7 1/7-2/7,0 0-27/7-10/7-15/7,x2x1,x1 x2 x3 x4 x5,CB XB b,CB,-15-5-11 0 0,j,-11-15,13/4 0 1 1-5/4 3/4,-1/2 1 0 0 1/2-1/2,0 0 0-25/4 3/4,x3x1,x1 x2 x3 x4 x5,CB XB b,CB,-15-5-11 0 0,引入人工变量x6，采用大M法继续求解,减少决策变量x2，最优生产计划如何？,四、系数矩阵的灵敏度分析,aij的变化使线形规划的约束系数矩阵A发生变化。若变量xj在最终单纯性表中为非基变量，其约束条件中系数aij的变化分析步骤可参照三中增加决策变量的情形；若变量xj在最终单纯性表中为基变量，其约束条件中系数aij的变化将使相应的B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需要引进人工变量先将原问题的解转化为可行解，再用单纯性法求解。,下面就变量xj在最终单纯性表中为基变量这种情形举例说明,例16、在佳美公司的例子中，若产品每单位需设备A、B和调试工时8小时、4小时、1小时，该产品的利润变为3百元/单位，试重新确定该公司最优生产计划.,解：先将生产工时变化后的产品看作是一种新产品，生产量为x2，按本节三的方法直接计算2和P2：,2=3-（0，1/4，1/2）=3/2,P6=,将其反映到最终单纯形表中得表,x1 x2 x3 x4 x5 x2,CB XB b,CB,j,2 1 0 0 0 3,x3x1x2,021,15/2 0 0 1 5/4-15/2 11/2,7/2 1 0 0 1/4-1/2 1/2,3/2 0 1 0-1/4 3/2 1/2,0 0 0-1/4-1/2 3/2,原问题与对偶问题均为非可行解，故先设法使原问题变为可行解,j,-9 0 7/2 1 4-24 0,2 1 0 0 1/2-2 0,3 0 1/2 0-1/2 3 1,0-1/2 0 1/2-5 0,x3x1x2,0 2 3,j,3/8 0-1/24-1/6 1 0 1/24,11/4 1-1/12 1/6 0 0 1/12,15/8 0 1/8 0 0 1-1/8,0-5/24-1/3 0 0-M+5/24,x5x1x2,0 2 3,j,9 0-1-4 24 0 1,2 1 0 1/2-2 0 0,3 0 0-1/2 3 1 0,0-M 1/2-4M-5+24M 0 0,x6x1x2,-M 2 3,x1 x3 x4 x5 x2 x6,CB XB b,CB,2 0 0 0 3-M,x3+4x4-24x5=-9,-x3-4x4+24x5+x6=9,可见变化后的问题具有唯一最优解:X*=(11/4,15/8)T Z*=89/8,五、增加或减少约束条件的灵敏度分析,增加一个约束条件在实际问题中相当增添一道工序，设在原线性规划问题中，增加一个新的约束条件：,代入新增加的约束条件，如果条件满足，则原问题的最优解仍为新问题的最优解，结束.,如果条件不满足，则将新增加的约束条件直接反映到最终单纯形表中再进一步分析.,则首先把已求得的原问题的最优解,例17、假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力为12小时，试分析增加该工序后的佳美公司最优生产计划.,解：环境试验工序的约束条件为：3x1+2x212 将原问题的最优解:x1=7/2,x2=3/2 代入环境试验工序的约束条件：,3*7/2+2*3/2=27/2,可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。,12,以x6为基变量将其反映到最终单纯形表中,将3x1+2x212化为标准型 3x1+2x2+x6=12,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,0 x6 12 3 2 0 0 0,0 x600010,(1)(2)(3)(4),因为表中x1、x2 列不是单位向量，所以需要进行变换,x1 x2 x3 x4 x5 x6,CB XB b,CB,j,2 1 0 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2 0,7/2 1 0 0 1/4-1/2 0,3/2 0 1 0-1/4 3/2 0,0 0 0-1/4-1/2 0,0 x6-3/2 0 0 0-1/4-3/2 1,(1)(2)(3)(4),x1 x2 x3 x4 x5 x6,CB XB b,CB,j,2 1 0 0 0 0,x3x1x2,021,15 0 0 1 5/2 0-5,4 1 0 0 1/3 0-1/3,0 0 1 0-1/2 0 1,0 0 0-1/6 0-1/3,0 x5 1 0 0 0 1/6 1-2/3,可见变化后的问题具有唯一最优解:X*=(4,0)T Z*=8,例18、假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力至少为15小时，试分析增加该工序后的佳美公司最优生产计划.,解：环境试验工序的约束条件为：3x1+2x215 将原问题的最优解:x1=7/2,x2=3/2 代入环境试验工序的约束条件：,3*7/2+2*3/2=27/2,可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。,以x6为基变量将其反映到最终单纯形表中,将3x1+2x2 15化为标准型-3x1-2x2+x6=-15,可以采用大M法，最好采用对偶单纯形法,避免用人工变量,x1 x2 x3 x4 x5,CB XB b,CB,j,2 1 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,0 x6-15-3-2 0 0 0,0 x600010,(1)(2)(3)(4),因为表中x1、x2 列不是单位向量，所以需要进行变换,x1 x2 x3 x4 x5 x6,CB XB b,CB,j,2 1 0 0 0 0,x3x1x2,021,15/2 0 0 1 5/4-15/2 0,7/2 1 0 0 1/4-1/2 0,3/2 0 1 0-1/4 3/2 0,0 0 0-1/4-1/2 0,0 x6-3/2 0 0 0 1/4 3/2 1,(1)(2)(3)(4),可见变化后的问题没有可行解，对偶问题具有无界解,减少约束条件的灵敏度分析,减少一个约束条件在实际问题中相当去掉一道工序，即在原线性规划问题中，去掉一个约束条件,反映到最终单纯形表中就是去掉一行，重新计算检验数行，可能利用单纯形法继续求解,j,x3x1x2,021,15/2 0 0 1 5/4-15/2,7/2 1 0 0 1/4-1/2,3/2 0 1 0-1/4 3/2,0 0 0-1/4-1/2,x1 x2 x3 x4 x5,CB,2 1 0 0 0,终表,CB XB b,0 1 0-1/2 1,该问题存在无界解,假如去掉调试工序，原问题的最优生产方案如何？,以上的几种灵敏度分析，仅限于某数值、变量、约束条件的变化对解的影响，这是一些基本的分析方法。若要考虑某区间上一个或几个参数作连续变化的灵敏度分析，请同学们参阅线性规划方面的资料或书籍。,对偶问题的经济解释影子价格,补充内容,30,20,10,max Z=5x1+4x2 s.t.x1+3x2 90 2x1+x2 80 x1+x2 45 x1,x2 0 由图示可知最优点为B（35，10）最优值为215,100,80,60,40,20,20,40,60,80,x1,100,B,1、影子价格含义的图解法,20,10,max Z=5x1+4x2 s.t.x1+3x2 91 2x1+x2 80 x1+x2 45 x1,x2 0 由图示可知最优点为B(35,10)最优值为215 称为资源A的影子价格为0,100,80,60,40,20,20,40,60,80,x1,100,B,30,20,10,max Z=5x1+4x2 s.t.x1+3x2 90 2x1+x2 81 x1+x2 45 x1,x2 0 由图示可知最优点为B（36，9）最优值为216称为资源B的影子价格为1,100,80,60,40,20,20,40,60,80,x1,100,B,20,10,max Z=5x1+4x2 s.t.x1+3x2 90 2x1