第三章 线性规划问题的对偶与灵敏度分析.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,运筹学,Operation,s,Research,北京理工大学珠海学院,吴浩然,线性规划的对偶问题,第三章 线性规划问题的对偶与灵敏度分析,1,对偶单纯形法,2,灵敏度分析,3,某企业可生产,A,、,B,两种产品，需消耗煤、电、油三种资源。有关数据如下表所示：,试拟订使总收入最大的生产方案。,A B,资源限量,煤,电,油,9 4,4 5,3 10,360,200,300,单位产品价格,7 12,3.1,对偶问题的提出,A B,资源限量,煤,电,油,9 4,4 5,3 10,360,200,300,单位产品价格,7 12,假若有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少，试建立购买者的线性规划模型。,原问题与对偶问题的对应关系,对称形式：,原问题：,对偶问题：,原问题,对偶问题,目标,max,型,目标,min,型,有,n,个变量,有,n,个约束,有,m,个约束,有,m,个变量,目标函数系数,约束条件右端常数,约束条件右端常数,目标函数系数,约束系数矩阵,约束系数矩阵的转置,原问题与对偶问题的对应关系,(,一,),课堂练习,请写出下述线性规划的对偶问题：,Max Z=2x,1,+3 x,2,s.t.x,1,+x,2,350,x,1,125,2x,1,+x,2,600,x,1,x,2,0,非对称形式,不具备对称形式的一对线性规划称为非对称形式的对偶规划,：,例：,s.t,原问题,对偶问题,第,j,个变量无限制,第,j,个约束为等式约束,第,i,个约束为等式约束,第,i,个变量无限制,原问题与对偶问题的对应关系,(,二,),原问题,对偶问题,目标,max,型,目标,min,型,有,n,个变量,有,n,个约束,有,m,个约束,有,m,个变量,目标函数系数,约束条件右端常数,约束条件右端常数,目标函数系数,约束系数矩阵,约束系数矩阵的转置,原问题,对偶问题,第,j,个变量无限制,第,j,个约束为等式约束,第,i,个约束为等式约束,第,i,个变量无限制,关系,(,一,),关系,(,二,),课堂练习,请写出下述线性规划的对偶问题：,Max Z=4x,1,+5 x,2,+2 x,3,s.t.3x,1,+2x,2,+x,3,20,4,x,1,-,3x,2,+3x,3,10,x,1,+x,2,+2x,3,=5,x,1,x,3,0,对偶问题的经济解释资源的影子价格,某工厂在计划期内安排,、,两种产品，生产单位产品所需资源,A,、,B,、,C,如下表所示，并且该工厂每生产一单位产品,可获利,50,元，每生产一单位产品,可获利,100,元，问工厂应分别生产多少 产品和,产品，才能使工厂获利最多？,资源限量,资源,A,1,1,300,资源,B,2,1,400,资源,C,0,1,250,资源限量,资源,A,1,1,300,资源,B,2,1,400,资源,C,0,1,250,假如有另外一个工厂要求购买该厂的资源,A,、,B,、,C,，那么应该如何确定合理的价格呢？,影子价格的经济含义,影子价格是对现有资源实现最大效益时的一种估价；,影子价格表明资源增加对总效益产生的影响；,3.2,对偶单纯形法单纯形法回顾,请用单纯形法求解下述线性规划问题：,Max Z=2x,1,+x,2,s.t.3x,1,+5x,2,15,6,x,1,+,2x,2,24,x,1,x,2,0,对偶单纯形法,适用条件,（,1,）线性规划问题初始单纯形表的,b,列中至少有一个基变量取值为负,（,2,）在同一个表格的检验数行中，全部检验数非正,步骤,例：,请用对偶单纯形法求解下述线性规划问题,Min f=3x,1,+2x,2,s.t.3x,1,+x,2,3,4,x,1,+,3x,2,6,x,1,+,3x,2,2,x,1,x,2,0,课堂练习,请用对偶单纯形法求解下述线性规划问题,Min f=x,1,+x,2,s.t.2x,1,+x,2,4,x,1,+,7x,2,7,x,1,x,2,0,课堂练习,Min Z=3x,1,+2 x,2,+,x,3,+4x,4,s.t.2x,1,+4x,2,+5x,3,+x,4,0,3,x,1,-,x,2,+7x,3,-2x,4,2,5x,1,+2x,2,+x,3,+6x,4,15,x,14,0,请用对偶单纯形法求解下述线性规划问题,3.3,灵敏度分析,已知某企业计划生产,3,种产品,A,、,B,、,C,，其资源消耗与利润如下表所示：,A,B,C,资源限量,资源甲,1,1,1,12,资源乙,1,2,2,20,利润,5,8,6,请问，该企业应该如何安排生产，才能使获利最大？,3.3,灵敏度分析,背景：,线性规划模型的,c,j,、,b,i,、,a,ij,等,系数是,估计值,：,c,j,市场条件；,b,i,资源投入量；,a,ij,工艺条件；,任务：,系数在什么范围内变化时，最优解（基）保持不变；,若系数的变化使最优解发生变化，如何,最简便,的求得新的最优解；,目标函数系数,c,j,的灵敏度分析,在保证最优解的基变量不变的情况下，分析,c,j,允许的变动范围,c,j,非基变量,对应的目标函数系数变化，不影响其它检验数；,基变量,对应的目标函数系数变化，影响所有非基变量检验数；,约束条件右端项,b,i,的灵敏度分析,分析,b,i,允许的变动范围,b,i,设,X,B,=,B,1,b,是最优解，则有,X,B,=,B,1,b,0,；,b,i,的变化不会影响检验数,；,b,i,的变化量,b,i,可能导致原最优解变为非可行解；,增加新变量的灵敏度分析,A,B,C,资源限量,资源甲,1,1,1,12,资源乙,1,2,2,20,利润,5,8,6,若新开发产品,D,，该产品需要消耗资源甲,3,个单位，乙,2,个单位，利润,10,元，请问，投产,D,是否有利？,增加新约束的灵敏度分析,A,B,C,资源限量,资源甲,1,1,1,12,资源乙,1,2,2,20,利润,5,8,6,若电力供应紧张，最多供应,13,个单位，而生产,A,、,B,、,C,每单位需要电力分别为,2,、,1,、,3,个单位，问该企业的生产方案是否需要改变？,已知,LP,问题：,Max Z=3x,1,+6x,2,s.t.-x,1,+2x,2,12,x,1,+,2x,2,7,x,1,x,2,0,(1),分别对,c,1,，,c,2,进行灵敏度分析；,(2),对,b,1,进行灵敏度分析；,(3),当,c,2,=2,时，求新的最优解；,(4),增加变量,x,5,，,c,5,=5,，,a,15,=2,，,a,25,=3,，对最优解是否有影响？,(5),增加一个约束条件：,2x,1,+,3x,2,6,，求新的最优解。,课堂练习,Thank You!,