第4章 线性规划灵敏度分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,线性规划解除有,唯一最优解,的情况外，还有如下几种情况,无可行解,退化,无穷多解,无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于基变量数,检验数中零的个数多于基变量的个数,检验数大于零，但对应列元素小于等于零，无换出变量,2,唯一最优解,否,否,否,是,是,是,添加松弛变量,、,人工变量 列出初始单纯形表,计算非基变量,各列的检验数,j,所有,j,0,基变量中,有非零的,人工变量,某非基变量检验数为零,无可行解,无穷多最优解,对任一,j,0,有,a,ik,0,无界解,令,k,=max,j,x,k,为换入变量,对所有,a,i,k,0,计算,i,=,b,i,/,a,ik,令,l,=min,i,第,l,个,基变量,为换出变量，,a,l,k,为主元素,迭代运算,.,用非基变量,x,k,替换换出变量,.,对主元素行,(,第,l,行,),令,b,l,/,a,lk,b,l,;,a,lj,/,a,lk,a,jl,对主元素列,(,第,k,列,),令,1,a,lk,;0,其它元素表中其它行列元素,令,a,ij,-a,li,/,a,lk,a,ik,a,ij,b,i,-,b,l,/,a,lk,a,ik,b,i,j,-,a,lj,/,a,lk,k,j,否,对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：,3,第四章 线性规划灵敏度分析,4.1,灵敏度分析的基本原理,4.2,目标函数系数的灵敏度分析,4.3,右端常数的灵敏度分析,4.4,技术系数的灵敏度分析,*,4.5,参数线性规划,4,线性规划的,灵敏度分析,也称为,敏感性分析,或,优化后分析,，它是研究和分析参数（,c,j,，,b,i,，,a,ij,）,的波动对最优解的影响程度，主要研究下面两个方面：,（,1,）参数在什么范围内变化时，原最优解或最优基不变,数据的稳定区间；,（,2,）当参数超出（,1,）的变化范围时，最优解或最优基有何变化,如何求出新的最优解和最优基。,当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。,4.1,灵敏度分析的基本原理,5,单纯形法：,对应于基,B,的典则形式（典式）,.,Ax=b,基变量用非基变量表示：,代入目标函数：,6,初始单纯形表,c,c,1,c,2,c,m,c,m+1,c,m+2,c,n,c,B,x,B,b,x,1,x,2,x,m,x,m+1,x,m+2,x,n,c,1,c,2,c,m,x,1,x,2,x,m,b,1,b,2,b,m,1 0 0,a,1m+1,a,1m+2,a,1n,0 1 0,a,2m+1,a,2m+2,a,2n,0 0 1,a,mm+1,a,mm+2,a,mn,-z,(0),0,0 0 ,m+1,m+2,n,7,分析 变化对最优解的影响。,C,C,B,C,N,C,B,X,B,b,X,B,X,N,C,B,X,B,B,-,1,b,I,B,-,1,N,Z,-,C,B,B,-,1,b,0,C,N,-,C,B,B,-,1,b,最优单纯形表,8,上表中,6,个常数,a,1,a,2,a,3,b,1,2,取值在什么范围可使,1,、现可行解最优，且唯一？何时不唯一？,2,、现基本解不可行；,3,、问题无可行解；,4,、无有限最优解；,5,、现基本解可行，由,x,1,取代,x,6,目标函数可改善。,c,j,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,3,4,a,1,1,0,a,2,0,b,x,4,-1,-5,0,1,-1,0,2,x,6,a,3,-3,0,0,-4,1,3,j,1,2,0,0,-3,0,9,线性规划标准形式,(1),、参数,A,，,b,，,C,在什么范围内变动，对当前方案无影响？,(2),、参数,A,，,b,，,C,中的一个,(,几个,),变动，对当前方案影响？,(3),、如果最优方案改变，如何用简便方法求新方案？,当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。,10,4.1,目标函数系数的灵敏度分析,考虑检验数,(1),若,c,j,是非基变量的系数：,11,解：最优单纯形表,例,1,试求,c,3,在多大范围内变动时，原最优解保持不变。,c,j,-2,-3,-4,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,-3,x,2,0,1,-1/5,-2/5,1/5,2/5,-2,x,1,1,0,7/5,-1/5,-2/5,11/5,j,0,0,-9/5,-8/5,-1/5,-28/5,12,从表中看到,c,3,=,-,4,3,=,-,9/5,可得到,c,3,-,3,=9/5,时，即,c,3,-,4+9/5=,-,11/5,时原最优解不变。,解：最优单纯形表,c,j,-2,-3,-4,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,-3,x,2,0,1,-1/5,-2/5,1/5,2/5,-2,x,1,1,0,7/5,-1/5,-2/5,11/5,j,0,0,-9/5,-8/5,-1/5,-28/5,13,(2),若,c,j,是基变量的系数,14,以下分两种情况讨论：,1,如果,c,r,0,上式才有可能不成立,因此有：,2,如果,c,r,0,只有,a,rj,0,，则问题的最优解将发生变化，此时对原最终表适当修改后，应用单纯形法继续计算得到问题的最优解。,16,例,2,已知问题的,最优单纯形表，,(1),求,c,2,在什么范围内变动时，原最优解保持不变；,(2),c,2,=5,时，求新的最优解。,最优单纯形表,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,最优解：,最优值：,17,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,C,i,2,3+,c,2,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3+,c,2,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2-,c,2,/2,-1/8+,c,2,/8,0,14+2,c,2,(1),求,c,2,的变动范围，使原最优解保持不变；,c,2,=c,2,+c,2,18,从表中看到,可得到,-3,c,2,1,时，原最优解不变。,C,i,2,3+,c,2,0,0,0,B,-,1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3+,c,2,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2-,c,2,/2,-1/8+,c,2,/8,0,14+2,c,2,19,C,i,2,5,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,16,0,x,5,0,0,-2,1/2,1,4,8,5,x,2,0,1,1/2,-1/8,0,2,-,j,0,0,-5/2,5/8,0,18,（,2,）,c,2,=2,，即,c,2,由,3,变为,5,时，求新的最优解,C,i,2,5,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,1,0,-1/2,2,0,x,4,0,0,-4,1,2,8,5,x,2,0,1,0,-1/8,-1/4,3,j,0,0,-2,0,-7/4,19,新的最优解：,最优值：,20,已知最优表如下,例,3,某企业利用两种资源生产三种产品的最优计划问题,归结为下列线性规划,c,j,5,4,3,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,4,5,x,2,x,1,40,20,0,1,1,0,2,3,2,1,1,1,j,260,0,0,4,3,1,21,c,j,5,4,3,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,4,5,x,2,x,1,40,20,0,1,1,0,2,3,2,1,1,1,j,260,0,0,4,3,1,最优计划是两种产品分别生产,40,单位与,20,单位，最大产值,z,*=260,单位。,（,1,）确定,x,2,的价值系数,c,2,的变化范围，使原最优解保持最优。,（,2,）,c,3,在什么范围内变化，最优解不变？,（,3,）若,c,3,从,3,变为,9,，求新的最优计划。,22,解（,1,）因为,x,2,为基变量，,c,2,的变换范围：,因此当,x,2,的价值系数在,即在区间,2.5,5,变化时，最优解不变。,23,（,2,）因为,c,3,是,非基变量,x,3,的价值系数，由公式得到,c,3,+,c,3,的变换范围：,即当,c,3,在,c,3,+c,3,3+4=7,时，最优解不变。,（,3,）当,c,3,从,3,变为,9,时，原最优解失去最优性，在表中作适当变动后（修改,c,3,的值，重新计算检验数），用单纯形法容易求得新的最优表如下：,24,c,j,5,4,9,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,4,5,x,2,x,1,40,20,0,1,1,0,2,3,2,1,1,1,j,260,0,0,2,3,1,4,9,x,2,x,3,160/3,20/3,2/3,1/3,1,0,0,1,4/3,1/3,1/3,1/3,j,820/3,2/3,0,0,7/3,5/3,故新的最优解为,X,*,=(0,160/3,20/3,0,0,）,最优值,z,*=820/3,，即随着第三种产品价格的上升，总产值上升。,25,设分量,b,r,变化为,b,r,+,b,r,，,根据前面的讨论：,最优解的基变量,X,B,=,B,-1,b,，,那么只要保持,B,-1,(,b,+,b,)0,则最优基不变，即基变量保持，只有值的变化；,否则，需要利用,对偶单纯形法,继续计算。,4.2,右端常数的灵敏度分析,26,27,例,4,已知前述例,2,的最优解及最优单纯形表,28,下表为最优单纯形表,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,29,由最优单纯形表得,:,30,31,不可行,!,用对偶单纯形法计算,将,b,代入原最优单纯形表中，运用对偶单纯形法计算最优解。,32,将,b,代入原最优单纯形表中，运用对偶单纯形法计算最优解。,经一次迭代后，求得新的最优解,:,(,4 3 2 0 0,),T,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,-4,3,x,2,0,1,1/2,-1/8,0,4,j,0,0,-3/2,-1/8,0,14,3/4,2,x,1,1,0,0,1/4,0,4,0,x,3,0,0,1,-1/4,-1/2,2,3,x,2,0,1,0,0,1/4,3,j,0,0,0,-1/2,-3/4,17,33,(1),增加一个新变量,增加一个变新量，相当于系数矩阵增加一列。,设增加变量,x,n,+1,，则有相应的,P,n,+1,c,n,+1,。,计算出,P,n+1,=,B,-1,P,n,+1,n,+1,=,c,n,+1,-,c,B,P,n,+1,填入最优单纯形表,若,n,+1,0,则 最优解不变；,否则，进一步用单纯形法求解。,4.3,技术系数的灵敏度分析,34,例,5,求当增加,x,6,P,6,=(2,6,3),T,c,6,=5,时，原最优解是否保持不变，若变动求出新的最优解。,解,:,下表为最优单纯形表,C,j,2,3,0,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,35,36,用单纯形法进一步求解，可得：,x*=(1,1.5,0,0,0,2),T,z*=16.5,C,i,2,3,0,0,0,5,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,1,0,0,1/4,0,3/2,4,8/3,0,x,5,0,0,-2,1/2,1,2,4,2,3,x,2,0,1,1/2,-1/8,0,1/4,2,8,j,0,0,-3/2,-1/8,0,5/4,14,2,x,1,1,0,3/2,-1/8,-3/4,0,1,5,x,6,0,0,-1,1/4,1/2,1,2,3,x,2,0,1,3/4,-3/16,-1/4,0,3/2,j,0,0,-1/4,-7/16,0,0,33/2,37,(2),增加一个新约束条件,增加一个新约束条件相当于在系数矩阵中增加一行。,增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为,0,，进一步用单纯形法或对偶单纯形法求解。,38,例,6,求当增加,3,x,1,+2,x,2,15,时，原最优解是否保持不变，若变动求出新的最优解。,解,:,下表为最优单纯形表,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,39,将,3,x,1,+2,x,2,+,x,6,=15,代入原最优单纯形表。,经,对偶单纯形法,迭代一步，可得：,最优解为,(,3.5,2.25,0,0,3,2,),T,，,最优值为,13.75,C,i,2,3,0,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,1,0,0,1/4,0,0,4,0,x,5,0,0,-2,1/2,1,0,4,3,x,2,0,1,1/2,-1/8,0,0,2,0,x,6,3,2,0,0,0,1,15,j,0,0,-3/2,-1/8,0,0,14,2,x,1,1,0,0,1/4,0,0,4,0,x,5,0,0,-2,1/2,1,0,4,3,x,2,0,1,1/2,-1/8,0,0,2,0,x,6,0,0,-1,-1/2,0,1,-1,j,0,0,-3/2,-1/8,0,0,14,40,(3),个别技术系数,a,ij,的改变,(,计划生产的产品工艺结构改变,),非基变量,x,j,工艺改变,只影响单纯形表,P,j,列,，,j.,关键看,j,0,?,还是,0,?,.,用增加新变量类似方法解决。,基变量,x,j,工艺改变，复杂，根据具体情况讨论。,41,分析,:,42,注,:,Y,可由最优单纯形表查得,43,最优单纯形表为,求：（,1,）,P,3,由,(,1,3),T,改为,(,1,2),T,；,（,2,）,P,1,由,(,1,2),T,改为,(1,1),T,，最优解的变化情况。,例,7,C,i,-2,-3,-4,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,-3,x,2,0,1,-1/5,-2/5,1/5,2/5,-2,x,1,1,0,7/5,-1/5,-2/5,11/5,j,0,0,-9/5,-8/5,-1/5,-28/5,44,C,i,-2,-3,-4,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,-3,x,2,0,1,-1/5,-2/5,1/5,2/5,-2,x,1,1,0,7/5,-1/5,-2/5,11/5,j,0,0,-9/5,-8/5,-1/5,-28/5,解：（,1,）,P,1,由,(,1,2),T,改为,(,1 1),T,，由最优单纯形表可知,所以原最优解不变,45,另解：（,1,）,P,3,由,(-1 3),T,改为,(-1 2),T,由最由单纯形表可知,所以原最优解不变,46,（,2,）,P,1,由,(,1,，,2),T,改为,(1,，,1),T,，,(,x,1,为基变量,),由最优单纯形表可知,代入最优单纯形表，用,P,1,代替,P,1,47,C,i,-2,-3,-4,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,-3,x,2,-3/5,1,-1/5,-2/5,1/5,2/5,-2,x,1,1/5,0,7/5,-1/5,-2/5,11/5,j,-28/5,-3,x,2,0,1,4,-1,-1,7,7/4,-2,x,1,1,0,7,-1,-2,11,11/7,j,0,0,22,-5,-7,-43,-3,x,2,-4/7,1,0,-3/7,1/7,5/7,-4,x,3,1/7,0,1,-1/7,-2/7,11/7,j,-22/7,0,0,-13/7,-5/7,-59/7,新的最优解为,:(,0,5/7,11/7,0,0,),T,最优值为：,59/7,48,最优单纯形表,C,i,2,3,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,1,1,0,0,1/4,0,4,0,x,5,0,0,-2,1/2,1,4,3,x,2,0,1,1/2,-1/8,0,2,j,0,0,-3/2,-1/8,0,14,例,8,求例,2,中,a,24,的变化范围,使最优解不变,.,49,例,8,求例,2,中,a,24,的变化范围,使最优解不变,.,解,:,50,例,9,在例,2,的基础上，企业要增加一个,新产品,每件产品需,2,个台时，原材料,A 6kg,，,原材料,B 3kg,，,利润,5,元,/,件，问如何安排各产,品的产量，使利润最大？,解：,5,3,2,利润,12,3,4,0,料B,16,6,0,4,料A,8,2,2,1,设备,b,51,表明生产新品有利,。,52,5/4,0,-1/8,-3/2,0,0,1/4,0,-1/8,1/2,1,0,2,3,2,1,1/2,-2,0,0,4,x,5,0,3/2,0,1/4,0,0,1,4,x,1,2,x,5,x,4,x,3,x,2,x,1,b,X,B,C,B,5,0,0,0,3,2,x,2,i,x,3,53,5/4,0,-1/8,-3/2,0,0,1/4,0,-1/8,1/2,1,0,2,3,2,1,1/2,-2,0,0,4,x,5,0,3/2,0,1/4,0,0,1,4,x,1,2,x,5,x,4,x,3,x,2,x,1,b,X,B,C,B,5,0,0,0,3,2,x,2,8/3,4/2,8,i,x,3,2,0,-5/8,-7/16,-1/4,0,0,0,-1/8,-3/16,3/4,1,0,3/2,3,1,1/2,1/4,-1,0,0,2,0,-3/4,-1/8,3/2,0,1,1,x,1,2,x,5,x,4,x,3,x,2,x,1,b,X,B,C,B,5,0,0,0,3,2,x,2,i,x,3,x,3,5,54,小结：灵敏度分析,55,56,综合例题：考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（,1,）将目标函数改为：,（,2,）改变右端常数为,:,57,（,3,）改变目标函数,x,3,的系数为,c,3,=1;,（,4,）改变目标函数中,x,2,的系数为,c,2,=2,；,（,5,）改变,x,2,的系数为,（,6,）改变约束（,1,）为,（,7,）增加新约束,（,8,）增加新约束,58,解：加入松弛变量,x,4,、,x,5,、,x,6,，,用单纯形法计算，得最优表,1,：,C,j,2,-1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,2,2,x,1,1,2/7,0,1/7,4/7,0,1,0,x,6,0,2,0,0,1,1,1,j,0,31/7,0,2/7,20/7,0,-10,表,1,59,最优解,X,=,（,1,，,0,，,2,，,0,，,0,，,1,），,最优值,Z,=10,，,最优基,（,1,）等价于 ，即将,c,j,改变为（,2,，,1,，,4,），其中,c,1,=,2,、,c,3,=,4,是基变量的系数，,c,2,=1,是非基变量的系数，求得检验数,60,这里表,1,的解不是最优，将上述检验数代替表,1,的检验数，再单纯形法继续迭代，计算结果如表,2,所示。,61,表,2,c,j,2,1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,2,2,x,1,1,2/7,0,1/7,4/7,0,1,0,x,6,0,2,0,0,1,1,1,j,0,31/7,0,2/7,20/7,0,1,x,2,0,1,7/5,1/5,3/5,0,14/5,2,x,1,1,0,2/5,1/5,2/5,0,1/5,0,x,6,0,0,14/5,2/5,1/5,0,33/5,j,0,0,31/5,3/5,1/5,0,1,x,2,3/2,1,2,1/2,0,0,5/2,0,x,5,5/2,0,1,1/2,1,0,1/2,0,x,6,1/2,0,3,1/2,0,1,13/2,j,1/2,0,6,1/2,0,0,最优解,62,基变量的解为,基本解不可行，将求得的,X,B,代替表,1,中的常数项，用对偶单纯形法求解，其结果见表,3,所示。,（,2,）改变右端常数为,:,63,C,j,2,1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,22/7,2,x,1,1,2/7,0,1/7,4/7,0,6/7,0,x,6,0,2,0,0,1,1,2,j,0,31/7,0,2/7,20/7,0,4,x,3,0,0,1,1/7,1/14,5/14,17/7,2,x,1,1,0,0,1/7,3/7,1/7,4/7,1,x,2,0,1,0,0,1/2,1/2,1,j,0,0,0,2/7,9/14,31/14,-69/7,表,3,最优解,64,由表,1,容易得到基变量,x,3,的系数,c,3,的增量变化范围是,而,c,3,=1,在允许的变化范围之外，故表,1,的解不是最优解。非基变量的检验数,x,4,进基，用单纯形法计算，得到表,4,。,（,3,）改变目标函数,x,3,的系数为,c,3,=1;,65,表,4,X,B,x,1,x,2,x,3,x,4,x,5,x,6,b,x,3,0,5/7,1,1/7,3/7,0,2,x,1,1,2/7,0,1/7,4/7,0,1,x,6,0,2,0,0,1,1,1,j,0,16/7,0,1/7,11/7,0,x,4,0,5,7,1,3,0,14,x,1,1,1,1,0,1,0,3,x,6,0,2,0,0,1,1,1,j,0,3,1,0,2,0,-6,最优解为,X,=,（,3,，,0,，,0,，,14,，,0,，,1,）,T,最优值,z=6,。,66,c,2,是非基变量,x,2,的系数，由表,3,知，由,1,变为,2,时，,或直接求出,x,2,的检验数,从而最优解不变，即,X=,（,1,，,0,，,2,，,0,，,0,，,1,）。,（,4,）改变目标函数中,x,2,的系数为,c,2,=2,；,67,这时目标函数的系数和约束条件的系数都变化了，同样求出,2,判别最优解是否改变。,x,2,进基，计算结果如表,5,所示,（,5,）改变,x,2,的系数为,68,表,5,C,j,2,3,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,0,1,1/7,3/7,0,2,2,x,1,1,1,0,1/7,4/7,0,1,0,x,6,0,3,0,0,1,1,1,j,0,5,0,2/7,20/7,0,x,3,0,0,1,1/7,3/7,0,2,x,1,1,0,0,1/7,5/21,1/3,4/3,x,2,0,1,0,0,1/3,1/3,1/3,j,0,0,0,2/7,25/21,5/3,-35/3,最优解,69,（,6,）第一个约束变为 实际上是改变了,a,12,及,b,1,，,这时要求,2,及,X,B,，,判断解的情况。,因为 可行，所以最优解为,70,引入松弛变量,x,7,得,x,1,、,x,3,是基变量，利用表,1,消去,x,1,、,x,3,，,得,x,7,为新的基变量，基本解,X=,（,1,，,0,，,2,，,0,，,0,，,1,，,2,）,不可行，将上式加入表,1,中用对偶单纯形法迭代得到表,6,。,（,7,）增加新约束,71,表,6,X,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,b,x,3,0,5/7,1,1/7,3/7,0,0,2,x,1,1,2/7,0,1/7,4/7,0,0,1,x,6,x,7,0,0,2,13/7,0,0,0,11/7,1,2/7,1,0,0,1,1,2,j,0,31/7,0,2/7,20/7,0,0,x,3,0,6/11,1,0,5/11,0,1/11,20/11,x,1,1,5/11,0,0,6/11,0,1/11,13/11,x,6,x,4,0,0,2,13/11,0,0,0,1,1,2/11,1,0,0,7/11,1,14/11,j,0,45/11,0,0,32/11,0,2/11,最优解,72,（,8,）将原最优解代入约束 的左边有,51,22=110,，满足新约束，故最优解不变。,上述,c,j,及,b,i,的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,1.,注意最优解与最优基不变的区别；,2.,掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；,3.,模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。,73,*,4.4,参数线性规划,在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数,C,和约束条件的右端常数,b,会随着某个参数而连续变动。,当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。,目标函数的价值系数,c,含有参数的线性规划问题,右端常数,b,含有参数的线性规划问题,74,(1),目标函数的价值系数含有参数的线性规划问题,75,求解步骤：,令,=0,，,求得最优解与最优基,B,；,根据 求得,的区间；,运用单纯形法求得其余区间的最优解。,例,1,76,解：,化为标准形；求,=0,的最优解与最优基,B,则,=0,时最优解为,(,0 100 230 0 0 20,),T,C,i,3,2,5,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,-1/4,1,0,1/2,-1/4,0,100,5,x,3,3/2,0,1,0,1/2,0,230,0,x,6,2,0,0,-2,1,1,20,j,-4,0,0,-1,-2,0,1350,77,根据 求得,的区间,即当,时最优解为,C,i,-6,-5,2,0,0,0,B,-1,b,C,i,3,2,5,0,0,0,C,B,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,-5,2,x,2,-1/4,1,0,1/2,-1/4,0,100,2,5,x,3,3/2,0,1,0,1/2,0,230,0,0,x,6,2,0,0,-2,1,1,20,j,-4,0,0,-1,-2,0,1350,j,-41/4,0,0,5/2,-9/4,0,-40,78,运用单纯形法求得其余区间的最优解,当,时,C,i,-6,-5,2,0,0,0,B,-1,b,C,i,3,2,5,0,0,0,C,B,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,-5,2,x,2,-1/4,1,0,1/2,-1/4,0,100,2,5,x,3,3/2,0,1,0,1/2,0,230,0,0,x,6,2,0,0,-2,1,1,20,j,-4,0,0,-1,-2,0,1350,j,-41/4,0,0,5/2,-9/4,0,-40,0,0,x,4,-1/2,2,0,1,-1/2,0,200,2,5,x,3,3/2,0,1,0,1/2,0,230,0,0,x,6,1,4,0,0,0,1,420,j,-9/2,2,0,0,-5/2,0,1150,j,-9,-5,0,0,-1,0,460,最优解为,79,当,时,C,i,-6,-5,2,0,0,0,B,-1,b,C,i,3,2,5,0,0,0,C,B,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,-5,2,x,2,-1/4,1,0,1/2,-1/4,0,100,2,5,x,3,3/2,0,1,0,1/2,0,230,0,0,x,6,2,0,0,-2,1,1,20,j,-4,0,0,-1,-2,0,1350,j,-41/4,0,0,5/2,-9/4,0,-40,-5,2,x,2,0,1,0,1/4,-1/8,1/8,205/2,2,5,x,3,0,0,1,3/2,-1/4,-3/4,215,-6,3,x,1,1,0,0,-1,1/2,1/2,10,j,0,0,0,5,0,0,1310,j,0,0,0,-31/4,23/8,0,-285/2,80,当,时,C,i,-6,-5,2,0,0,0,B,-1,b,C,i,3,2,5,0,0,0,C,B,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,-5,2,x,2,0,1,0,1/4,-1/8,1/8,205/2,2,5,x,3,0,0,1,3/2,-1/4,-3/4,215,-6,3,x,1,1,0,0,-1,1/2,1/2,10,j,0,0,0,5,0,0,1310,j,0,0,0,-31/4,23/8,0,-285/2,-5,2,x,2,0,1,-1/6,0,-1/12,1/4,200/3,0,0,x,4,0,0,2/3,1,-1/6,-1/2,430/3,-6,3,x,1,1,0,2/3,0,1/3,0,460/3,j,0,0,10/3,0,-5/6,-1/2,1780/3,j,0,0,31/6,0,19/12,5/4,-3760/3,81,参变量的取值范围与最优解为,82,（,2,）右端常数含有参数的线性规划问题,求解步骤：,令,=0,，,求得最优解与最优基,B,；,根据 求得,的区间；,运用对偶单纯形法求得其余区间的最优解。,83,例,2,解：,化为标准形；求,=0,的最优解与最优基,B,84,根据 求得,的区间；,则,=0,时最优解为,(,0,100,230,0,0,20,),T,C,i,3,2,5,0,0,0,B,-1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,-1/4,1,0,1/2,-1/4,0,100,5,x,3,3/2,0,1,0,1/2,0,230,0,x,6,2,0,0,-2,1,1,20,j,-4,0,0,-1,-2,0,1350,85,最优解为,C,i,3,2,5,0,0,0,B,-1,b,b*,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,-1/4,1,0,1/2,-1/4,0,100,3/2,5,x,3,3/2,0,1,0,1/2,0,230,-2,0,x,6,2,0,0,-2,1,1,20,-10,j,-4,0,0,-1,-2,0,1350,-7,86,当,时最优单纯形表为,运用单纯形法求得其余区间的最优解。,C,i,3,2,5,0,0,0,B,-1,b,b*,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,-1/4,1,0,1/2,-1/4,0,100,3/2,5,x,3,3/2,0,1,0,1/2,0,230,-2,0,x,6,2,0,0,-2,1,1,20,-10,j,-4,0,0,-1,-2,0,1350,-7,2,x,2,1/4,1,0,0,0,1/4,105,-1,5,x,3,3/2,0,1,0,1/2,0,230,-2,0,x,4,-1,0,0,1,-1/2,1/2,-10,5,j,-5,0,0,0,-5/2,-1/2,1360,-12,时，最优解为,当,87,当,时最优单纯形表为,C,i,3,2,5,0,0,0,B,-1,b,b*,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,-1/4,1,0,1/2,-1/4,0,100,3/2,5,x,3,3/2,0,1,0,1/2,0,230,-2,0,x,6,2,0,0,-2,1,1,20,-10,j,-4,0,0,-1,-2,0,1350,-7,0,x,5,1,-4,0,-2,1,0,-400,-6,5,x,3,1,2,1,1,0,0,430,1,0,x,6,1,4,0,-3/2,0,1,420,-4,j,-2,-8,0,-5,0,0,2150,5,最优解为,88,参变量的取值范围与最优解为,89,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,2,x,2,1,3,1,0,0,x,5,0,-1,-2,1,0,0,90,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,2,x,2,-1,1,3,1,0,10,0,x,5,8,0,-1,-2,1,5,0,0,-2,-2,0,20,91,C,j,-2,2,4,0,0,5,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,x,2,-1,1,3,1,0,2,10,0,x,5,8,0,-1,-2,1,-7,5,0,0,-2,-2,0,1,20,5,-1/2,1/2,3/2,1/2,0,1,5,0,x,5,9/2,7/2,19/2,3/2,1,0,40,1/2,-1/2,-7/2,-5/2,0,0,25,5,0,8/9,23/9,2/3,1/9,1,85/9,-2,x,1,1,7/9,19/9,1/3,2/9,0,80/9,0,-8/9,-41/9,-8/3,-1/9,0,265/9,92,C,B,X,B,X,1,X,2,X,3,X,4,X,5,X,6,X,7,b,0,X,5,0,1,1/4,-1,1,4,X,4,0,0,1,-1,2,5,X,2,1,0,-3/4,1,-Z,0,0,-1/4,-1,-13,93,C,B,X,B,X,1,X,2,X,3,X,4,X,5,X,6,X,7,b,0,X,5,-1,0,-27/4,0,1,1/4,-1,1,4,X,4,1,0,-2,1,0,1,-1,2,5,X,2,1,1,15/4,0,0,-3/4,1,1,-Z,-7,0,-39/4,0,0,-1/4,-1,-13,94,C,B,X,B,X,1,X,2,X,3,X,4,X,5,X,6