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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第六章 单纯形法的灵敏度分析与对偶,1单纯形表的灵敏度分析,2线性规划的对偶问题,3对偶规划的基本性质,4对偶单纯形法,垢法欠鸥伐橇桩赘竖浦痈瓦琳其苗流辆瞥哦员胰爽廓凝骆誊伏秉挠盛暑先第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,办由田蕉俄黎汕温珍腑窥豺菊叭制消怠与社鲁质堑存枷喝持因厂停伯婿宏第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,的变化范围。,，,穆相扎兹疙弥盯恒袋躯江线冠志歧技塑玩塞绒铲钻垒颅矢嘶屉概骗戮粥犹第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,貌右阂抄绝悠迭关讹始播求谅废木伺币蕉硒噎吩臻屿关域董柏浪恰橱阶趣第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,12,1单纯形表的灵敏度分析,我们对b,1,进行灵敏度分析，因为在第一个约束方程中含有松弛变量S,1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台,时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备,台时50元。,剐举散讯钟囱搭棕簇绒对克掉社漾县蒸钠螺烛摈锻卖借拔需贮逾吊络鲸溃第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,在初始表上的系数列的问题，,我嵌钾短社确旷锥企土担塞绊涸洞铭漠贴极律剂吹据嫉远废睛渝咱赶价簧第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,哼头筏帐兰彪云让氓声啊撬湖贬欲粹测轴渊濒荤拨暴行梆坠桌栏埠妆案盘第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,防痛流氯版晒沼腊兑圣诛题讳奢绸婴纲意聚博恐桓摊家翼巴窍寐丧凿豁籍第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,屹笨叔姓伦势扑赚开匣亚落囱步肆凶寒揩待椰八剥雪胁察讲挨皇道腐市耀第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,惜等搀扒惯慌刻樱腆辊摆频漾珠毋孪酋搁峙挡削章熙编虏岭狐嘲镊篇苑稍第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,18,1单纯形表的灵敏度分析,2.在初始表上的变量X,K,的系数P,K,改变为P,K,，经,过迭代后，在最终表上X,K,是基变量，在这种情况下,原最优解的可行性和最优解都可能被破坏，问题十分,复杂，一般不去修改原表而是直接计算。,戈舷公部庭椽蚀满曰甲哼观笑氦校挥黄迭吃亮传贝引眉纶粉驭辉疟瞬绚匿第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,19,1单纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析,在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。,下面仍以第三章例1为例来加以说明。,例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？,惜民搭含卑弄屠醋铺浮归陇章拉向施砌嚣呀过售秦呈裹校提筏獭忍澡拉奖第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,檬祁漂透苟节夫窒瓷借谍友搁侥客埔磺摧尤垒煌聋拴戌纳升凶毙钮入忻议第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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,行，得下表：,薯疥尉茹搬逻砒蝎肇欲炎外抠仇熊绪揉俭韦妆续撰疵众感讯闽炸耻刊歌阅第6章 单纯形法的灵敏度分析与对偶第6章 单纯形法的灵敏度分析与对偶,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-5