第二章对偶理论与灵敏度分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,LP,的对偶理论与灵敏度分析,1,线性规划的对偶问题,2,对偶规划的基本性质,3,影子价格,4,对偶单纯形法,5,灵敏度分析,对偶问题概念：,任何一个线性规划问题都有一个伴生的线性规划问,题，称为其“对偶”问题。,对偶问题,是对原问题从另一角度进行的描述，其最,优解与原问题的最优解有着密切的联系，在求得一,个线性规划最优解的同时也就得到对偶线性规划的,最优解，反之亦然。,对偶理论就是研究线性规划及其对偶问题的理论，,是线性规划理论的重要内容之一。,第一节,线性规划的对偶问题,例,1,穗羊公司的例子,I,II,每周可使用量,A,（千克）,1,2,5,B,（吨）,2,1,4,C,（百工时）,4,3,9,单位产品利润（万元）,3,2,一、对偶问题的提出,问,公司应每天制造两种产品各多少件，使获取的利润最大？,生产计划问题（,LP1,）,现在我们从另一个角度来考虑这个问题。假如有另外一个新公司要求租用穗羊公司的资源，那么,新公司愿意以多大的代价才能使穗羊出让自己所拥有的生产资源？,资源定价问题（,LP2,）,设,y,1,y,2,和,y,3,分别表示出让资源,A,，,B,和调试工序的单价，则该公司同意出让的条件将是,同意出让生产产品,I,的资源,同意出让生产产品,II,的资源,购买者希望用最少的代价获得这些资源,，因此,这样得到一个新的线性规划问题,这样从两个不同的角度来考虑同一种资源的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。,如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。,1.,求,目标函数最大值的线性规划问题中有,n,个变量,m,个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有,m,个变量,n,个约束条件，其约束条件都为大于等于不等式。,2.,原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第,i,个变量的系数就等于对偶问题中的第,i,个约束条件的右边常数项。,3.,原,问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第,i,个约束条件的右边常数项就等于零对偶问题的目标函数中的第,i,个变量的系数。,4.,对偶问题的约束条件的系数矩阵,A,是原,问题约束矩阵的转置。,设,则,二、,对称形式的,LP,问题与对偶问题的一般形式,定义：,满足下列条件的,LP,问题称为具有对称形式：,变量,：所有变量均具有非负约束,约束条件,：,最大化问题,所有约束条件都是“,”型的,最小化问题,所有约束条件都是“,”型的,对称形式的,LP,问题与对偶问题的一般形式为,对称形式的原问题对偶问题的矩阵形式,对称形式的原问题的矩阵形式,对称形式的对偶问题的矩阵形式,对称形式下的对偶关系,项目,原问题,对偶问题,A,b,C,目标函数,约束条件,决策变量,约束条件系数矩阵,约束条件右端项向量,目标函数系数向量,max,z,=,CX,AX,b,X,0,约束条件系数矩阵转置,目标函数的系数向量,约束条件的右端项向量,min,w,=,Y b,AY,C,Y,0,原问题,max z,对偶问题,min w,n,个决策变量,m,个约束条件,n,个约束条件,m,个决策变量,约束条件“,”型,决策变量,0,决策变量,0,约束条件“,”型,对称形式的对应关系,对偶问题的对偶是原问题，即对偶关系是相互对称的关系,对偶问题的特点,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,一般线性规划问题的对偶问题,2,、非对称形式下的原问题与对偶问题,(x,变,),2,、非对称形式下的原问题与对偶问题,(,方程变,),2,、,max z=2 x,1,+x,2,+3 x,3,+x,4,x,1,+x,2,+x,3,+x,4,5,s.t.2x,1,-x,2,+3 x,3,=-4,x,1,+2 x,3,+x,4,1,x,1,x,3,0,x,2,x,4,无约束,练习题：,1,、,min z=3 x,1,+2 x,2,-3 x,3,+4,x,4,x,1,-2 x,2,+3 x,3,+4,x,4,3,s.t.x,2,+3 x,3,+4,x,4,-5,2 x,1,-3 x,2,-7 x,3,-4,x,4,=2,x,1,0,x,2,0,x,3,x,4,无约束,2,、非对称形式下的原问题与对偶问题,(,方程变,),结论：,方程对变量,变量对方程,正常对正常,不正常对不正常,变量正常是非负,方程正常看目标,(max=),对称、非对称形式下的对偶关系,原问题,（对偶问题）,max z,对偶问题,（原问题）,min w,n,个决策变量,m,个约束条件,n,个约束条件,m,个决策变量,约束条件“,”型,约束条件“,”型,约束条件“,=”,型,决策变量,0,决策变量,0,决策变量无约束,决策变量,0,决策变量,0,决策变量无约束,约束条件“,”型,约束条件“,”型,约束条件“,=”,型,原问题,对偶问题,第二节,对偶问题的基本性质,1,、对偶问题的对偶问题是原问题,对偶的定义,对偶的定义,max z=CX,s.t.AXb,X 0,min w=bY,s.t.AYC,Y 0,min z=-CX,s.t.-AX-b,X 0,max w=-bY,s.t.-AY-C,Y 0,一、单纯形法的矩阵表示,添加松弛变量,X,S,将,X,B,的系数矩阵化为单位矩阵,C,B,C,N,0,X,B,X,N,X,S,0 X,S,b,B N I,c,j,-z,j,C,B,C,N,0,C,B,C,N,0,X,B,X,N,X,S,C,B,X,B,B,-1,b,I B,-1,N B,-1,c,j,-z,j,0 C,N,C,B,B,-1,N C,B,B,-1,初始单纯形表,迭代后的单纯形表,在,初始单纯形表中单位矩阵经过迭代后变为基矩阵,B,的逆,在初始单纯形表给出的解中基变量,X,s,=b,而在迭代后的表给出的解中基变量,X,B,=B,-1,b,系数矩阵的变化,:A,I,B,-1,A,I,在初始单纯形表中变量,x,j,的系数为,P,j,经过迭代后变为,P,j,并且,P,j,=B,-1,P,j,当,B,为最优基时，由上表有,C,N,-C,B,B,-1,N0,，,-C,B,B,-1,0,（,1,）,因而,x,B,的检验数应写为,C,B,-C,B,I=0,（,2,）,所以（,1,）、（,2,）可以改写为,C-C,B,B,-1,A0,，,-C,B,B,-1,0,（,3,）,C,B,B,-1,称为单纯形乘子，若令,Y=C,B,B,-1,，,（,3,）改写为,看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将此解代入对偶问题，有,w=,Yb,=C,B,B,-1,b=z,若原问题有最优解，这是对偶问题为可行解且有相同的目标值。,迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解,min w=5y,1,+4y,2,+9y,3,6 y,2,+y,3,2,st,.,5 y,1,+2 y,2,+y,3,1,y,1,y,2,y,3,0,5x,2,15,6x,1,+2x,2,24,x,1,+x,2,5,x,1,x,2,0,max z=3x,1,+2x,2,st,.,对偶变量,y,1,y,2,y,3,变量,x,1,x,2,x,1,+2x,2,+x,3,=5,2x,1,+x,2,+x,4,=4,4x,1,+3x,2,+x,5,=9,x,1,x,2,x,3,x,4,x,5,0,y,1,+2 y,2,+4 y,3,y,4,=,3,2 y,1,+y,2,+3 y,3,y,5,=,2,y,1,y,2,y,3,y,4,y,5,0,原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但,在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系,原问题,对偶问题,第,i,个约束条件中添加的松弛变量,第,i,个对偶变量,第,j,个变量,第,j,个约束条件中添加的松弛变量,注 上表中我们将松弛变量与剩余变量统称为松弛变量,推论,1,：,原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。,推论,2,：,原问题 对偶问题,无界解 无可行解,无可行解 无界解,2,、弱对偶性,如果 是原问题的可行解，是其对偶问题的可行解，则：,推论,3,：,原问题 对偶问题,无可行解,+,可行解 对偶问题有无界解,可行解,+,无可行解 原问题有无界解,3,、最优性,如果 是原问题的可行解，是其对偶问题的可行解，且有 则：是原问题和对偶问题的最优解。,4,、,强对偶性,X,*,、,Y,*,分别是原问题和对偶问题的最优解，则：,5,、互补松弛性,max z=CX,s.t.AX+X,S,=b,X,X,S,0,min w=bY,s.t.AY-Y,S,=C,Y,Y,S,0,max z=CX,s.t.AX b,X 0,min w=bY,s.t.AY C,Y0,对偶,引进松弛变量,引进松弛变量,X Y,S,=0 ,Y X,S,=0,互补松弛关系,X,Xs,Y,Ys,互补松弛性的另一种表述,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零,;,反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。,互补松弛性,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式,;,反之若一个约束条件为严格的不等式,则其对应的对偶变量为零,例,原,问题,对偶问题,将原,问题最优解,X*=(2,2,4,0),代入原问题约束条件中得,第一个约束条件：,2+6=8,，为等式,第二个约束条件：,4+2=6,，为等式,第三个约束条件：,2+4=6,，为等式,第四个约束条件：,2+2+40,得,而由,x,2,=20,得,而由,x,3,=40,得,于是得到方程组,得,对偶问题最优解为,注：原问题与对偶问题最优目标函数值都是,z*=4+8+4=16,三、对偶问题的经济解释,1,、原问题是利润最大化的生产计划问题,单位产品的利润（,元,/,件）,产品产量（件）,总利润（元）,资源限量（吨,）,单位产品消耗的资源（吨,/,件）,剩余的资源（,吨）,消耗的资源（吨）,2,、对偶问题,资源限量（吨）,资源价格（元,/,吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解,y,1,、,y,2,、,.,、,y,m,称为,m,种资源的影子价格（,Shadow Price,）,原、对偶问题都取得最优解时,最大利润,max z=min w,3,、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺,影子价格越小，说明这种资源相对不紧缺,如果最优生产计划下某种资源有剩余，这种资源的影子,价格一定等于,0,市场价格,影子价格：卖出此项资源,y,1,y,2,y,m,4,、产品的机会成本,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,5,、产品的差额成本（,Reduced Cost,）,差额成本,=,机会成本,-,利润,0,y,y,y,y,y,y,c,y,y,a,y,a,y,a,c,y,y,a,y,a,y,a,c,y,y,a,y,a,y,a,.,t,.,s,y,b,y,b,y,b,w,min,n,m,2,m,1,m,m,2,1,n,n,m,m,mn,2,n,2,1,n,1,2,2,m,m,2,m,2,22,1,12,1,1,m,m,1,m,2,21,1,11,m,m,2,2,1,1,=,-,+,+,=,-,+,+,=,-,+,+,+,+,=,+,+,+,+,+,+,L,L,L,L,L,L,L,L,L,L,L,L,5,、互补松弛关系的经济解释,在利润最大化的生产计划中,（,1,）边际利润大于,0,的资源没有剩余,（,2,）有剩余的资源边际利润等于,0,（,3,）安排生产的产品机会成本等于利润,（,4,）机会成本大于利润的产品不安排生产,影子价格,是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。,若,x,*,y,*,分别为（,LP,）,和（,DP,）,的最优解，,那么，,c,T,x,*,=,b,T,y,*,。,根据,f,=,b,T,y,*,=,b,1,y,1,*,+,b,2,y,2,*,+,+,b,m,y,m,*,可知,f,/,b,i,=,y,i,*,y,i,*,表示,b,i,变化,1,个单位对目标,f,产生的影响，称,y,i,*,为,b,i,的影子价格。,注意：,若,B,是最优基，,y,*,=(,B,T,),-1,c,B,为影子价格向量。,第三节 影子价格,影子价格的经济含义,(1),影子价格是对现有资源实现最大效益时的一种估价,.,企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,（,2,）影子价格表明资源增加对总效益产生的影响。根据推论“设,x,0,和,y,0,分别为原规划（,P,）,和对偶规划（,D,）,的可行解，当,cx,0,=,b,T,y,0,时，,x,0,、,y,0,分别是两个问题的最优解”可知，在最优解的情况下，有关系,因此，可以将,z,*,看作是,b,i,i,=1,2,，,m,的函数，对,b,i,求偏导数可得到,这说明，如果右端常数增加一个单位，则目标函数值的增量将是,影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,式中,b,i,是线性规划原问题约束条件的右端项，它代表第,i,种资源的拥有量；,对偶变量,y,i,的意义代表在资源最优利用的条件下对第,i,种资源的估价,。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为,影子价格,。,设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有,第四节 对偶单纯形法,按,对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。,单纯形法求解的基本思路,基,可行解,检验数非正,保持解的可行性,对偶单纯形法的基本思路,对偶问题基可行解,（检验数非正）,原,问题基可行解,保持对偶问题解的可行性（检验数非正,（对偶问题可行解）,对偶单纯形法的基本思想,对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,对偶单纯形法在什么情况下使用：,应用前提：,有一个基，其对应的基,满足,:,单纯形表的检验数行全部非正（对偶可行）；,变量取值可有负数（非可行解）。,注：,通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。,对偶单纯形法计算步骤,适应于求解这样的,LP,问题：,标准化后不含初始基变量，但将某些约束条件两端乘以“,-1”,后，即可找出初始基变量。,要求：,初始单纯形表中的检验数满足最优性条件,对满足上述条件的,LP,问题，对偶单纯形法的步骤是：,旋转运算。然后回到第,2,步。,作出初始单纯形表（注意要求）,检查,b,列的数据是否非负，若是，表中已经给出最优解,；否则转下一步,确定换出变量,：取,b,列最小的数对应的变量为换出变量,确定换入变量,：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量,例 用对偶单纯形法求解如下的,LP,问题,化成,标准形式,将各,约束条件两端同乘“,-1”,得,用,对偶单纯形法求解得,最优解：,x,1,=0,x,2,=1/4,x,3,=1/2,x,4,=0,x,5,=0,最优目标函数值：,w*=-8.5,（,z*=8.5,）,注：通常很少直接使用对偶单纯形法求解线性规划问题。,单纯形法和对偶单纯形法步骤,是,是,是,是,否,否,否,否,所有,所有,得到,最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以为中心元素进行迭代,以为中心元素进行迭代,停,没有最优解,没有最优解,单纯形法,对偶单纯形法,对偶单纯形法的适用范围,对偶单纯形法适合于解如下形式的线性规划问题,在引入松弛变量化为标准型之后，约束等式两侧同乘,-1,，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。,对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。,第五节 灵敏度分析,将讨论,LP,问题中的参数 中有一个或几个发生改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变,在生产计划问题的一般形式中，,A,代表企业的技术状况，,b,代表企业的资源状况，而,C,代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。,在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,当系数,A,，,b,，,C,发生改变时，目前最优基是否还最优？,为保持目前最优基还是最优，系数,A,，,b,，,C,的允许变化范围是什么？,假设每次只有一种系数变化,目标系数,C,变化,基变量系数发生变化；,非基变量系数发生变化；,右端常数,b,变化,增加一个变量,增加一个约束,技术系数,A,发生变化,C,B,X,B,c,j,C,B,C,N,x,j,b,X,B,T,X,N,T,C,B,T,X,B,B,-1,b,B,-1,B,B,-1,N,-C,B,B,-1,b,C,B,-C,B,B,-1,B,C,N,-C,B,B,-1,N,若,B,是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,研究的思路,将,个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要从头计算，而,直接检查在参数改变后最终表有什么改变,，若仍满足最终表的条件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。,灵敏度分析的步骤,将,参数的改变计算反映到最终表上来。具体计算公式可以使用,检查原问题是否仍为可行解,检查对偶问题是否仍为可行解,对检查情况按下表进行处理,原,问题,对偶问题,结论或继续计算步骤,可行解,可行解,问题的最优解或最优基不变,可行解,非,可行解,用,单纯形法继续迭代求最优解,非,可行解,可行解,用,对偶单纯形法继续迭代求最优解,非,可行解,非,可行解,引进人工变量，编制新的单纯形表重新计算,1.,价值系数,C,j,变化的灵敏度分析,目标函数系数,c,j,的变化，仅仅带来检验数 的变,化，对最优单纯形表右边向量,B,-1,b,和系数矩阵,B,-1,N,没有影响。,首先计算变化后的 ，基变量检验数,。如果所有检验数仍然满足非正数，则最优解不变，否则继续进行迭代。,例：穗羊公司根据市场调查，,（,1,）发现产品,II,的市场价需要下调,1,万，产品,I,、,II,的单位利润变为（,3,，,1,），该公司的最优生产计划有何改变；,（,2,）若产品,II,的利润不变，则产品,I,的利润在什么范围变化时，该公司的最优生产计划不发生变化,原,最终单纯形表,（,1,）改变后,新的最优解为：,最优目标函数值为：,（,2,）改变后,为使表,中的解仍为最优解必须,因此产品,II,的利润变化范围为,2.,资源常数,b,j,变化的灵敏度分析,当,b,发生改变时，对检验数、系数矩阵没有影,响，但对基变量的取值有影响。,计算 ，如果 保持非负，则原最优解不改变，；否则进行对偶单纯形迭代。,例：在第一章的例,1,中,资源,B,的使用量可以增加到,5,，分析公司最优计划的变化；,（,1,）,b,由,(5,，,4,，,9),T,变为,(5,，,5,，,9),T,后，相应地最终表中,b,列的数据变为,3.,增加一变量,x,j,：,设新产品,的产量为,x,6,件,例 该公司研发了新产品,III,，,单位产品对资源的消耗为（,3,，,0,，,2,），该产品的利润为,2,万元，原生产计划是否改变？,假设该产品的消耗系数为,P,j,，,单位利润为,c,j,计算该产品的机会成本,Y,P,j,。,如果机会成本小于单位利润，则不生产；否则，在原终表里增加新列,B,-1,P,j,，,并进行迭代。,产品,III,的机会成本,=,YP,j,=,（,0,，,1/2,1/2,）,(3,0,2)=1,最优解：,X=(2,0,3/2,0,0,，,1/2),z=7,利用,Excle,求解,LP,问题，以,P45.7(2),为例,变量，已经赋了初值,目标函数值,约束条件右端值,其他专业软件：,Lindo,与,Lingo,，,WinQSB,例如,Lingo,，启动,Lingo,后，按图中的方式输入模型，然后点击求解的图标 。就可得到所需的最优解。,