教案7_灵敏度（改）.ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,5,对偶问题的经济解释,影子价格,(,P),的最终单纯形表中松弛变量的检验数对应,(,D),的最优解。,当,某,约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。,Z*=CX*=Y*b,=(y,1,*,y,2,*,y,m,*),b,1,b,2,b,m,=,y,1,*b,1,+y,2,*b,2,+,y,m,*,b,m,当,某个右端常数,b,i,b,i,+1,时,b,i,+1,y,i,*,+,y,i,*(b,i,+1),=,Y*b+,y,i,*,=Z*+,y,i,*,第,I,种资源的影子价格是第,i,个约束条件的右端常数增加一个单位时，目标函数增加的数量,甲 乙,可用量,机械设备,1 2,8,原材料,A,4 0,16,原材料,B,0 4,12,X,(3),=(4，2，0，0,4),T,，,z,3,=14,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,0,3,x,1,x,5,x,2,4,4,2,1,0,0,0,0,1,-2,-3/2,-1/8,1/8,0,1,0,-14,0,0,-3/2,-1/8,0,经济意义：,在其它条件不变的情况下，,单位资源变化所引起的目标函数的最优值的变化。,影子价格,产品,资源,现有资源数,钢材,1 2,100,（吨）,煤,2 2,180,（吨）,机时,1 6,240,（小时）,利润（万元）,1 3,x,1,x,2,x,3,x,4,x,5,-,z,X,B,-135,0,0,-3/4,0,-1/4,x,1,30,1,0,3/2,0,-1/2,x,4,50,0,0,-5/2,1,1/2,x,2,35,0,1,-1/4,0,1/4,X*=(30,35,0,50,0),T,Z*=135,y,1,*=3/4,y,2,*=0,y,3,*=1/4,影子价格,经济意义：,在其它条件不变的情况下，,单位资源变化所引起的目标函数的最优值的变化。,影子价格的意义,(1),影子价格客观地反映资源在系统内的稀缺程度。,如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。,(2),影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。,(3),影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。,(4),如果考虑扩大生产能力，应该从影子价格高的设备入手。,6,对偶单纯形法,保持对偶可行性，逐步改进主可行性，求解主问题。,当,b,有负分量，,A,中有一明显初始对偶可行基,(,检验数均非正,),，因而易得一初始解时，可用对偶单纯形法求解。,设,B,为一个基,基本解,X,（0）,为基本可行解的条件？,B,-1,b0,X,（0）,为,最优解的条件？,原,原始可行性条件,原始最优性条件,令,Y=C,B,B,-1,，,代入原始最优性条件，,YAC,对偶可行性条件,例 用对偶单纯形法求解,单纯形法,大,M,法,剩余变量、人工变量,用（,-1,）乘不等式两边，再引入松弛变量。,c,j,-1 -4 0 -3 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,x,5,x,6,-3,-2,-1 -2 1 -1 1 0,2 1 -4 -1 0 1,0,-1 -4 0 -3 0 0,先,选出基变量,后选进基变量,原问题，符合原始最优性条件，但不可行,c,j,-1 -4 0 -3 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,-1,0,x,1,x,6,3,-8,1 2 -1 1 -1 0,0 -3 -2 -3 2 1,3,0 -2 -1 -2 -1 0,c,j,-1 -4 0 -3 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,-1,0,x,1,x,6,3,-8,1 2 -1 1 -1 0,0 -3 -2 -3 2 1,3,0 -2 -1 -2 -1 0,-1,0,x,1,x,3,7,4,1 7/2 0 5/2 -2 -1/2,0 3/2 1 3/2 -1 -1/2,7,0 -1/2 0 -1/2 -2 -1/2,最优解,X*=（7，0，4，0）,T,Z*=-7,例6,用对偶单纯形法求解,（P）,1 -4/3 -,-1 0 -5/2 1/2 1 -1/2,2 1 -1/2 3/2 0 -1/2,0 -4 -1 0 -1,-,8/5 -2,2/5 0 1 -1/5 -2/5 1/5,11/5 1 0 7/5 -1/5 -2/5,0 0 -3/5 -8/5 -1/5,对偶单纯形法的一个应用：,增加一个约束条件的分析。,检查原最优解是否满足新的约束条件,满足，则原最优解仍为最优解，否则，,2,。,2,将约束方程带到最优单纯形表中。,max,z=,x,+,45,x,+,24,x,40,1,2,3,s.t,.,例,新,增加一个条件,7,灵敏度分析,系数,b,i,、,c,j,、,a,ij,变化，最优解的最优性、可行性是否变化？,系数在什么范围内变化，最优解或最优性不变？,如何求新的最优解？,本节重点,7.1,灵敏度分析的原理,是最优解，则,可行性条件,最优性条件,正则性,b,i,非基变量,c,j,基变量,c,B,增加新变量,一个非基变量,系数,a,ij,的变化，要视,a,ij,对应的变量是基变量或非基变量而定。,X,B,=B,-1,(b+,b)，,其中,b=(0,b,r,0,0),T,只要,X,B,0，,最终表中检验数不变（,b,变化，不影响检验数），则最优性不变，但最优解的值发生变化,X,B,成为新的最优解,.,B,-1,(b+,b)=B,-1,b+B,-1,b,0,新的最优解允许范围是,:,当某一个资源系数,b,r,发生变化，亦即,b,r,=,b,r,+,b,r,，,其他系数不变，这样最终的单纯形表中原问题的解相应地变化为,1,、,资源系数,b,r,的灵敏度变化分析,B,-1,的第,r,列,进一步得，最终表中,b,列元素,b,b,a,i,r,ir,-,D,B,-1,b,0,b,a,b,r,ir,i,D,+,i,=1，2，m,i,=1，2，m,ir,i,r,ir,a,b,b,a,;,/,0,-,D,ir,i,r,ir,a,b,b,a,/,0,-,D,x,1,x,5,x,2,是基变量，从而可得基,B,例：求第一章例题中当第二个约束条件,b,2,变化范围,b,2,。,得到公式,:,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,0,3,x,1,x,5,x,2,4,4,2,1,0,0,0,0,1,-0,-2,1/,2,1/4,1/2,-1,/8,0,1,0,-14,0,0,-3/2,-1/8,0,可得,b,2,-4/0.25=-16,b,2,-4/0.5=-8,b,2,2/0.125=16,由公式知,b,2,变化范围,-8,16,显然,b,2,变化范围,8,32,例题,:,将上面例题进行实际应用。每台设备台时的影子价格为,1.5,元。若该厂又从别处抽出,4,台时用于生产两种产品，求这时该厂生产两种产品的最优方案。,B=（x,1,x,5,x,2,),将这个结果放到最终表中得,解：先计算,B,-1,b,2 3 0 0 0,c,j,203,x,1,x,2,x,5,4+0,4-8,2+2,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,1 0 0 0.25 0,0 0 -2 0.5 1,0 1 0.5 -0.125 0,c,j,-,z,j,0 0 -1.5 -0.125 0,表中,b,列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。,最优解见下表,最优生产方案应改为第一种产品,4,件，第二种产品,3,件，获利,z=17,元。,2 3 0 0 0,c,j,203,x,1,x,2,x,3,4,2,3,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,1 0 0 0.25 0,0 0 1 -0.25 -05,0 1 0 0 0.25,c,j,-,z,j,0 0 0 -0.5 -0.75,（1,）当,c,j,是非基底变量x,j,的系数，检验数为,或,当,c,j,变化,c,j,后，检验数应要小于或等于零，即,2,、目标函数中价值系数,C,的变化,（2,）当,c,r,是基底变量,x,r,的系数，即,c,r,C,B,，,c,r,变化,c,r,后，有,a,a,a,C,A,C,B,B,A,B,C,A,B,C,rn,r,r,r,r,B,L,L,L,),(,),0,0,(,2,1,1,1,1,D,+,=,D,+,-,-,-,最优解不变,n,j,a,c,A),j,c,rj,r,j,j,L,2,1,=,D,-,-,=,s,(C,B,B,1,-,c,r,的变化范围,例8,：仍以第一章例,1,的最终表为例。设基变量,x,2,的系数,c,2,变化,c,2,，,在原最优解不变的条件下，确定,c,2,的变化范围。,解：这时最终计算表为,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,0,3,x,1,x,5,x,2,4,4,2,1,0,0,0,0,1,0,-2,0.5,0.25,0.5,-,0.125,0,1,0,c,j,-z,j,0,0,-1.5,-0.125,0,可见,c,2,-1.5/0.5;,c,2,-0.125/(-0.125),故,c,2,的,变化范围,:,-3,c,2,1,即,x,2,的价值系数,c,2,可在,0,4,之间变化，不影响原最优解。,c,j,50,30,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,30,50,x,2,x,1,20,15,0,1,1,0,1,-1/2,-2,3/2,c,j,-z,j,0,0,-5,-15,已知线性规划问题,最优单纯形表,练习,1,3,a,ij,的变化分析,(1).,a,ij,为非基变量的系数,只影响,x,j,的检验数，从而影响最优性。,例,:,第一章例,1,，增加一种新产品,，它的技术系数是,(2，6，3),T,，,利润系数是,5,。,问该厂是否应生产该产品和生产多少？,解：设新产品,的产量为,x,3,(,对于原最优解来说是非基变量,),。因,故应生产产品,。,x,3,进基,在最终表中的系数是：,原最终表成为：,用单纯形法求解得：,(2).,a,ij,为基变量系数,基变化,，影响最优性、可行性。,例,:,第一章例,1,，若生产产品,的工艺结构有改进，其技术系数变为,（,2,，,5，2),T,，,利润系数为,4,，试分析对生产计划有什么影响？,解：设产品,产量为,x,1,(,产品,产量在原最优解中是基变量,),。计算,将和所求系数填入原最终表的,x,1,列位置，得,将,x,1,的系数列向量变换为单位向量,上表中假如对偶可行，主不可行，则用对偶单纯形法求新解；假如主对偶均不可行，要加入人工变量，用单纯形法继续解。,注意：,例11,假设例,10,的产品,的技术系数向量为,p1=（4，5，2），,而每件获利仍为,4,元。试该厂应如何安排最优生产方案？,练习,2,在练习,1,中，如果新增加产品，其目标系数为,100,，消耗系数为（,9，3.5,）是否应该生产该产品,c,j,50,30,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,30,50,x,2,x,1,20,15,0,1,1,0,1,-1/2,-2,3/2,c,j,-z,j,0,0,-5,-15,最优单纯形表,(1),求线性规划问题的最优解；,(2),求对偶问题的最优解；,(3)当,b3=-150,时最优基是否发生变化？为什么？,(,4)求,C2,的灵敏度范围,;,(5),如果,x3,的系数由,1，3，5,变为,1，3，2,最优基是否改变？若改变求新的最优解,;,(6),假定新增决策变量,x8，,且,p8=(2，5，3)，C8=4，,原最优解是否改变？为什么？,线性规划综合例题,某工厂使用,5,种生产方式，生产,A,、,B,、,C,三种产品，有关每种方法的批产量数据如表,1,、资源消耗如表,2,。有一合同要求至少生产,A110,单位。,表,1,每种方法的批产量,方法,产品,1,2,3,4,5,单价,A,B,C,3,6,2,2,1,6,4,2,5,4,1,1,0,4,8,10,5,4,方法,产品,1,2,3,4,5,单价,工时,机时,成本,/,元,0,1,48,4,1,19,6,2,30,1,1,44,2,1,7,80,50,-,表,2,资源消耗,1.,若第,2,种生产方法的成本提高到,21,元，问是否改变最有解？,2.,现每工时的工资为,3,元，若加班，另附加费用,1.5,元/,h，,加班是否使利润增加？,3.,若只要另付加班费,0.3,元/,h，,加班是否有利？如果有利，可加班多少小时？,4.,若购置,1,台新机器，购价为,30,万元，每天可以增加,8,h，,机器可以用,5,年，每年,250,工作日，问是否有利？,5.,问增加,3,台新机器是否有利？,6.,公司按合同每天至少供应,110,单位,A,，,若变更合同减少供应量，是否有利？,7.第,4,种生产方法的成本要降低到什么程度才能增加利润？,8.,若第,2,种方法的批量不能超过,20,次，最优解有无变化？若不能超过,15,次呢？,