第6章--单纯形法的灵敏度分析与对偶ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,中华管理学习网,*,第六章 单纯形法的灵敏度分析与对偶,1,单纯形表的灵敏度分析,2,线性规划的对偶问题,3,对偶规划的基本性质,4,对偶单纯形法,1,中华管理学习网,1,单纯形表的灵敏度分析,一、目标函数中变量,C,k,系数灵敏度分析,1.,在最终的单纯形表里，,X,k,是非基变量,由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与,C,k,没有任何关系，,所以当,C,k,变成,C,k,+C,k,时，在最终单纯形表中其系数的增广矩阵不变，又因为,X,k,是非,基变量，所以基变量的目标函数的系数不变，即,C,B,不变，可知,Z,k,也不变，只是,C,k,变,成了,C,k,+C,k,。,这时,K,=C,k,-,Z,k,就变成了,C,k,+C,k,-,Z,k,=,K,+C,k,。,要使原来的最优解,仍为最优解，只要,K,+,C,k,0,即可，也就是,C,k,的增量,C,k,-,K,。,2.,在最终的单纯形表中，,X,k,是基变量,当,C,k,变成,C,k,+C,k,时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目,标函数的系数,C,B,变了，则,Z,J,(J=1,2,.,N),一般也变了，不妨设,C,B,=(C,B1,C,B2,。,C,k,，,C,Bm,),当,C,B,变成,=(C,B1,C,B2,。,C,k,+C,k,C,Bm,),则：,Z,J,=(C,B1,C,B2,。,C,k,，,C,Bm,)(,a,1j,a,2j,a,Kj,a,mj,),Z,J,=(C,B1,C,B2,。,C,k,+C,k,，,C,Bm,)(,a,1j,a,2j,a,Kj,a,mj,)=Z,J,+,C,k,a,Kj,2,中华管理学习网,1,单纯形表的灵敏度分析,根据上式可知,检验数,J,(J=1,2,.,M),变成了,J,有,J,=C,J,-Z,J,=,J,+C,K,a,Kj,。,要使最优解不变，只要当,J K,时，,J,0,，就可求出,的取值范围，也就是使得第,K,个约束条件的对偶价格不变的,b,k,的变化范围。,，,11,中华管理学习网,1,单纯形表的灵敏度分析,下面我们仍以第二章例,1,在最终单纯形表上对,b,j,进行灵敏度分析。,最终单纯形表如下所示：,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,b,50 100 0 0 0,2,X,1,50,1 0 1 0 -1,50,S,2,0,0 0 -2 1 1,50,X,2,100,0 1 0 0 1,250,Z,J,50 100 50 0 50,27500,C,J,-Z,J,0 0 -50 0 -50,12,中华管理学习网,1,单纯形表的灵敏度分析,我们对,b,1,进行灵敏度分析，因为在第一个约束方程中含有松弛变量,S,1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台,时数在,250,与,325,之间变化，则设备台时数的对偶价格不变，都为每台设备,台时,50,元。,13,中华管理学习网,1,单纯形表的灵敏度分析,三、约束方程系数矩阵,A,灵敏度分析,下面分两种情况讨论,1.,在初始单纯形表上的变量,X,k,的系数列,P,k,改变为,P,k,经过迭代后，在最终单纯形表,上,X,k,是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，,P,k,变成,P,k,仅仅影响最终单纯形表上第,k,列数据，包括,X,k,的系数列、,Z,k,以及,k,，这时最终单纯形表上的,X,k,的系数列就变成了,B,-1,P,j,而,Z,k,就变成,C,B,B,-1,P,k,，新的检验数,k,=C,k,-C,B,B,-1,P,k,。若,k,0,，则原最优解仍然为最优解。若,k,0,，则继续进行迭代以求出最优。,例,以第二章例,1,为基础，设该厂除了生产,，,种产品外，现在试制成一个新产品,，已知生产,产品,每件需要设备,2,台时，并消耗,A,原料,0.5,公斤。,B,原料,1.5,公斤，获利,150,元，问该厂应该生产该产品多少？,解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量,X,3,在初始表上的系数列的问题，,14,中华管理学习网,1,单纯形表的灵敏度分析,接上页,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,X,1,50,1 0 1 0 -1 0.5,50,S,2,0,0 0 -2 1 1 -2,50,X,2,100,0 1 0 0 1 1.5,250,Z,J,50 100 50 0 50 175,27500,C,J,-Z,J,0 0 -50 0 -50 -25,15,中华管理学习网,1,单纯形表的灵敏度分析,例 假设上例题中产品,的工艺结构有了改进，这时生产,1,件,产品需要使用,1.5,台设备，消耗原料,A,为,2,千克，原料,B,为,1,千克，每件,产品的利润为,160,元，问该厂的生产计划是否要修改,。,解：首先求出,X,3,在最终表上的系数列,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,2,X,1,50,1 0 1 0 -1 0.5,50,50/0.5,S,2,0,0 0 -2 1 1 0,50,X,2,100,0 1 0 0 1 1,250,250/1,Z,J,50 100 50 0 50 125,27500,C,J,-Z,J,0 0 -50 0 -50 35,16,中华管理学习网,1,单纯形表的灵敏度分析,接下来又可以有新的迭,代,S,3,进基，,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,3,X,3,160,2 0 2 0 -2 1,100,-,S,2,0,0 0 -2 1 1 0,50,50/1,X,2,100,-20 1 -2 0 3 0,150,250/3,Z,J,120 100 120 0 -20 160,31000,C,J,-Z,J,-70 0 -120 0 20 0,17,中华管理学习网,1,单纯形表的灵敏度分析,接上页,可知此规模的最优解,X,1,=0,X,2,=0,S,1,=0,S,2,=0,S,3,=50,X,3,=200,此时，最大目标函数为,32000,元。也就是说，该厂的新的生产计划为不生产,、,产品，生产,产品,200,件,可获得最大利润,32000,元。,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,4,X,3,160,2 0 2 0 -2 1,200,-,S,3,0,0 0 -2 1 1 0,50,50/1,X,2,100,-2 1 4 -3 0 0,0,250/3,Z,J,120 100 80 20 0 160,32000,C,J,-Z,J,-70 0 -80 -20 0 0,18,中华管理学习网,1,单纯形表的灵敏度分析,2.,在初始表上的变量,X,K,的系数,P,K,改变为,P,K,，经,过迭代后，在最终,表上,X,K,是基变量，在这种情况下,原最优解的可行性和最优解都可能被破坏，问题十分,复杂，一般不去修改原表而是直接计算。,19,中华管理学习网,1,单纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析,在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。,下面仍以第三章例,1,为例来加以说明。,例：假如该工厂除了在设备台时，原材料,A,、,B,上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为,5000,度，而生产一个,产品需要用电,10,度，而生产一个,产品需要用电,30,度。试分析此时该厂获得最大利润的生产计划？,20,中华管理学习网,1,单纯形表的灵敏度分析,解：先将原问题的最优解,=50,，,=250,代入用电量的约束条件,得：,10,50+30,250=500+75005000,所以原题的最优解不是本题的最优解。,在用电量的约束条件中加入松驰变量,S,4,后得：,把这个约束条件加入到原最终单纯形表上，其中,S,4,为基变量，得表如下：,迭代次数,基变量,b,比值,50,100,0,0,0,0,50,1,0,1,0,-1,0,50,0,0,0,-2,1,1,0,50,100,0,1,0,0,1,0,250,0,10,30,0,0,0,1,5000,50,100,50,0,50,0,27500,0,0,-50,0,-50,0,21,中华管理学习网,1,单纯形表的灵敏度分析,在上表中的,X,1,，,X,2,不是单位向量，故进行行的线性变换，得,迭代,次数,基变量,C,B,x,1,x,2,s,1,s,2,s,3,s,4,b,比值,50,100,0,0,0,0,x,1,50,1,0,1,0,-1,0,50,s,2,0,0,0,-2,1,1,0,50,x,2,100,0,1,0,0,1,0,250,s,4,0,0,0,-10,0,-20,1,-3000,z,j,50,100,50,0,50,0,27500,0,0,-50,0,-50,0,把上表中的,S,4,行的约束可以写为：,上式两边乘以（,-1,），再加上人工变量,a,1,得：,用上式替换上表中的,S,4,行，得下表：,22,中华管理学习网,1,单纯形表的灵敏度分析,迭代次数,基变量,x,1,x,2,s,1,s,2,s,3,s,4,a,1,b,比值,50,100,0,0,0,0,-M,x,1,50,1,0,1,0,-1,0,0,50,s,2,0,0,0,-2,1,(1),0,0,50,x,2,100,0,1,0,0,1,0,0,250,s,4,-M,0,0,-10,0,-20,1,1,3000,z,j,50,100,50-10M,0,50-20M,0,-M,0,0,10M-50,0,20M-50,0,0,x,1,50,1,0,-1,1,0,0,0,100,s,3,0,0,0,-2,1,1,0,0,50,x,2,100,0,1,2,-1,0,0,0,200,s,4,-M,0,0,50,-20,0,-1,1,2000,z,j,50,100,150-50M,20M-50,0,M,-M,0,50M-150,50-20M,0,-M,0,x,1,50,1,0,0,3/5,0,-1/50,1/50,140,s,3,0,0,0,0,1/5,1,-2/50,2/50,130,x,2,100,0,1,0,-1/5,0,2/50,-2/50,120,s,4,0,0,0,1,-2/5,0,-1/50,1/50,40,z,j,50,100,0,10,0,3,-3,0,0,-10,0,-3,-M+3,23,中华管理学习网,1,单纯形表的灵敏度分析,由上表可知，最优解为：,即该工厂在添加了用电限量以后的最优生产计划为,产品生产,140,件，,产品生产,120,件。,24,中华管理学习网,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。,例题,1,某工厂在计划期内安排,、,两种产品，生产单位产品所需设备,A,、,B,、,C,台时如表所示,该工厂每生产一单位产品 可获利,50,元，每生产一单位产品,可获利,100,元，问工厂应分别生产多少 产品和,产品，才能使工厂获利最多？,解：设 为产品 的计划产量，为产品,的计划产量，则有,目标函数：,Max,z,=50+100,约束条件：,，,2,线性规划的对偶问题,25,中华管理学习网,现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备,A,、,B,、,C,，,那么该厂的厂长应该如何来确定合理的租金呢？,设 分别为设备,A,、,B,、,C,的每台时的租金。为了叙述