管理运筹学第6章单纯形法的灵敏度分析与对偶

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第六章 单纯形法的灵敏度分析与对偶,1 单纯形表的灵敏度分析,2 线性规划的对偶问题,3 对偶规划的根本性质,4 对偶单纯形法,1,1 单纯形表的灵敏度分析,一、目标函数中变量Ck系数灵敏度分析,1.在最终的单纯形表里，X k是非基变量,由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，,所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非,基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变,成了Ck+Ck。这时 K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解,仍为最优解，只要 K+Ck0即可，也就是Ck的增量 Ck-K。,2.在最终的单纯形表中，X k是基变量,当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目,标函数的系数CB变了，那么ZJ(J=1,2,.,N)一般也变了，不妨设CB=(CB1,CB2。,Ck,，CBm),当CB变成=(CB1,CB2。,Ck+Ck,CBm),那么：,ZJ=(CB1,CB2。,Ck,，CBm)(a1j,a2j,aKj ,amj),ZJ=(CB1,CB2。,Ck+Ck,，CBm)(a1j,a2j,aKj ,amj)=ZJ+Ck aKj,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 单纯形表的灵敏度分析,我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台,时数在250与325之间变化，那么设备台时数的对偶价格不变，都为每台设备,台时50元。,13,1 单纯形表的灵敏度分析,三、约束方程系数矩阵A灵敏度分析,下面分两种情况讨论,1.在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭代后，在最终单纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk，新的检验数 k=Ck-CBB-1Pk。假设 k0，那么原最优解仍然为最优解。假设 k 0，那么继续进行迭代以求出最优。,例 以第二章例1为根底，设该厂除了生产，种产品外，现在试制成一个新产品，生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？,解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，,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元，问该厂的生产方案是否要修改。,解：首先求出X3在最终表上的系数列,迭代次数,基变量,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 单纯形表的灵敏度分析,接上页,可知此规模的最优解X1=0,X2=0,S1=0,S2=0,S3=50,X3=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代入用电量的约束条件,得：1050+30250=500+75005000,所以原题的最优解不是此题的最优解。,在用电量的约束条件中参加松驰变量S4后得：,把这个约束条件参加到原最终单纯形表上，其中S4为基变量，得表如下：,迭代次数,基变量,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，再加上人工变量a1得：,用上式替换上表中的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的每台时的租金。为了表达方便，这里把租金定义为扣除本钱后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否那么就不出租还是用于生产 产品以获利50元；同样把,生产一单位 产品所需各设备的台时的总租金也不应当低于原利润100元，即,，否那么这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型：,目标函数：,约束条件：,这样从两个不同的角度来考虑同一个工厂的最大利润最小租金的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。,2 线性规划的对偶问题,26,如果我们把求目标函数最大值的线性规划问题看成原问题，那么求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。,1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶那么是求目标函数为最小值的线性规划问题，有m个变量n个约束条件