运筹学02_对偶理论与敏感性分析

影子价格——是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。§3.对偶变量的经济解释——影子价格Shadowprice2maxz=2x1+x2s.t.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤156x1+2x2≤25x1+x2≤5x1,x2≥0b2：24→25z*：8.5→8.75z/b2=0.253若x*,y*分别为(LP)和(DP)的最优解，那么，cx*=y*b根据z*=w*=y*b=b1y1*+b2y2*++bmym*可知z*/bi=yi*yi*表示bi每单位变化对最优目标函数值z*产生的影响，称yi*为bi的影子价格。注意：若B是最优基，y*T=cBB-1为影子价格向量。影子价格的经济含义（1）影子价格是对现有资源实现最大效益时的一种估价。也是一种机会成本。企业可以根据现有资源的影子价格，做决策：第一，若租费高于某设备的影子价格，可考虑出租该设备；否则不宜出租。第二，若市价低于某设备的影子价格，可考虑买进该设备，扩大生产；否则不宜买进。（2）影子价格表明资源增加对总效益产生的影响。根据推论：当x*和y*分别为原规划(LP)和对偶规划(DP)的可行解，且cx*=bTy*时，x*和y*分别是两个问题的最优解。6因此，可以将z*看作是bi,i=1,2,…,m的函数，对bi求偏导数可得到这说明，如果右端常数bi增加一个单位，则最优目标函数值z*的增量将是影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。8（3）一种资源的影子价格，是指在其它条件都不变时，该种资源增加一个单位所产生的总利润增加量。当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。3x1+x2≤53’x1+x2≤6b2：24→25z/b20.25（4）影子价格的经济含义，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。10[0,18][18,30][30,+)x1*(b2-6)/6(b2-10)/45x2*3(30-b2)/40z*1+b2/35/2+b2/410y2*=z/b21/31/4b20随着第二种资源可使用数量b2的变化，这种资源的影子价格y2*也在变化。Excel输出的“敏感性报告”中的主要内容求解第五章案例1问题的敏感性报告见下图所示，图中“可变单元格”下的“递减成本”给出的是最优单纯形迭代中各决策变量检验数的负值；“允许的增量”和“允许的减量”则给出了在不影响当前最优解的条件下各决策变量目标函数系数cj单独变化时的可变动范围。而“约束”下的“阴影价格”则给出了各种资源的“影子价格”；“允许的增量”和“允许的减量”则给出了在不影响当前最优基的条件下各有限资源数量（约束条件右端常数）单独变化时的可变动范围。Excel输出的“敏感性报告”中的主要内容13信息的不确定性信息的变化：价值向量—市场变化右端向量—资源变化系数矩阵—技术进步认知的误差§5.灵敏度分析SensitivityAnalysis问题1：ci,bi,aij发生变化，问题的最优解如何变化？或者这些参数在多大的范围内变化，最优解仍然不变？问题2：增加一约束或变量，最优解如何变化？15灵敏度分析的基本步骤1.将参数的改变在最终单纯形表中表示出来；2.检查原问题是否可行;3.检查对偶问题是否可行；4.按照以下几种情况决定是否继续计算及计算方法16原问题对偶问题结论或继续计算的步骤可行解可行解最优基不变可行解非可行解用单纯形法继续迭代非可行解可行解用对偶单纯形法继续迭代非可行解非可行解引入人工变量，编制新的单纯形表重新计算17价值系数c发生变化：考虑检验数j=-cj+∑i=1,2,…,mcia’ij,j=1,2,……,n这里a’ij为最优单纯形表中的系数，不同于初始的aij1.c是非基变量的系数：2.c是基变量的系数：1.若ck是非基变量的系数：设ck变化为ck+ckk’=-ck-ck+∑cia’ik=k-ck只要k’≥0,即ck≤k，则最优解不变；否则，将最优单纯形表中的检验数k用k’取代，继续单纯形法的表格计算。例2.5:maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0最优单纯形表Δc3≤9/5时，原最优解不变。c3在什么范围内变化，原最优解不变？c-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5σj28/5009/58/51/52.若cs是基变量的系数：设cs变化为cs+cs，那么j’=-cj+∑iscia’ij+(cs+cs)a’sj=j+csa’sj，只要对所有非基变量，有j’≥0，即csa’sj≥-j，则最优解不变；否则，将最优单纯形表中的检验数j用j’取代，继续单纯形法的表格计算。22例2.6：某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时及A，B两种原材料的消耗如下表所示：III可用资源设备128台时原材料A4016kg原材料B0412kg已知生产1件I可以获利2元，生产1件II可获利3元，问应当如何安排计划使该工厂获利最多？例2.6：线性规划maxz=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥0有最优解的单纯形表：考虑基变量系数c2发生变化的范围，保持最优解不变？c23000cBxBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80σj-1400-1.5-1/80易得：当-3≤Δc2≤1时，原最优解不变。右端项资源向量b发生变化设分量br变化为br+br，最优解的基变量xB=B-1b，那么只要保持B-1(b+b)=B-1b+B-1b≥0则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。11100000rrBbBΔbbBΔb例2.7:例2.6中最优单纯形表如下若现在该厂从其他地方抽调4台时设备用于生产I和II，求此时的最优方案b1增加4c23000cBxBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80σj-1400-1.5-1/8000.250这里B-1=-20.510.5-0.1250各列分别对应b1,b2,b3的单一变化。因此，设b1增加4，则x1,x5,x2分别变为：4+0×4=4,4+(-2)×4=-40,2+0.5×4=4用对偶单纯形法进一步求解。得：x*=(4,3,2,0,0)T,z*=17增加一个变量增加变量xn+1，由相应的Pn+1和cn+1计算：B-1Pn+1和n+1=-cn+1+∑cia’in+1填入最优单纯形表，若n+1≥0则最优解不变；否则，进一步用单纯形法求解。29例2.8:：假设在例1中，该厂除了生产产品I和II外，还有一种新产品III。已知生产产品III每件需要消耗原材料A和B各为6kg和3kg，使用设备2台时，每件可以获利5元，问该厂是否应当生产该产品和生产多少？30例2.8:例2.6中增加x6，P6=(2,6,3)T，c6=5计算得到用单纯形法进一步求解。c230005cBxBbx1x2x3x4x5x62x141001/403/20x5400-21/21[2]3x22011/2-1/801/4σj-2000-3/2-1/805/431c230005cBxBbx1x2x3x4x5x62x141001/403/20x5400-21/21[2]3x22011/2-1/801/4σj-2000-3/2-1/805/4c230005cBxBbx1x2x3x4x5x62x11103/2-1/8-3/405x6200-11/41/213x23/2013/4-3/16-1/80σj-33/200-1/4-7/16-5/80得：x*=(1,1.5,0,0,0,2)T;z*=16.5增加一个约束增加约束一个之后，应把最优解代入新的约束。若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。例2.9：例2.6中增加3x1+2x2≤15，原最优解不满足这个约束。于是用对偶单纯形法一步继续计算。最优解x*=(3.5,2.25,0,2,3,0)T；最优值z*=13.75c230000cBxBbx1x2x3x4x5x62x141001/4000x5400-21/2103x22011/2-1/8000x6-100-1-1/201σj00-3/2-1/80034A中元素发生变化某种产品的生产工艺发生变化1.N中某一列变化：与增加变量xn+1的情况类似，假设Pj变化。那么，重新计算出单纯形表第j列(a’1j,a’2j,…,a’mj)T=B-1Pj，j=-cj+∑cia’ij，若j≥0，则最优解不变；否则，进一步用单纯形法求解。2.B中某一列变化：稍微复杂些，一般可重新列表计算，也可以用列替换的方法在原最优单纯形表上继续进行计算。36例2.10：例2.6中x2的系数P2改变为(4,0,2)T，c2改变为1。将原来x2看作x’2，新的x2看作新加入的变量，计算原最优基下的(a’12,a’22,…,a’m2)T=B-1P2，2=-c2+∑cia’i2，用单纯形法进一步求解。37得到单纯形表做一次迭代：让新变量x2进基，替换基变量x’2c232000cBxBbx1x'2x2x3x4x52x1410001/400x5400-6-21/213x'2201[2]1/2-1/80σj-1400-4-3/2-1/8038删去原变量x’2的列，得到新的最优单纯形表：最优解x*=(4,1,0,0,10)T；最优值z*=10c22000cBxBbx1x2x3x4x52x141001/400x51000-1/21/812x21011/4-1/160σj-1000-1/2-3/8039TheEnd