资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,对偶理论与灵敏度分析,(Dual Theories and Sensitivity Analysis),单纯形法的矩阵描述,线性规划的对偶问题,对偶问题的基本性质,对偶问题的经济解释,-,影子价格,对偶单纯形法,灵敏度分析,例,单纯形法的矩阵描述,(Matrices Description),X,B,x,1,x,2,x,3,x,4,x,5,b,x,1,1 0 0 1/4 0 4,x,5,0 0,-,2 0.5 1 4,x,2,0 1 0.5,-,1/8 0 2,-z,0,0 -3/2 -1/8 0 -14,C,B,=,2 0 3,C,N,=,0 0,单纯形法的矩阵描述,B,C,B,X,B,C,N,X,N,N,b,单纯形法的矩阵描述,单纯形法的矩阵描述,B,-1,N,B,-1,b,单纯形法的矩阵描述,考虑线性规划问题的标准型,A,C,m,n,R,(A)=m,.,可行基,相应于非基变量的系数矩阵,令,A=,(,B N,),X=,(X,B,X,N,),T,C=,(C,B,C,N,),单纯形法的矩阵描述,矩阵形式的单纯形表,X,B,X,B,X,N,b,X,B,I B,-1,N B,-1,b,- z,0,C,N,- C,B,B,-1,N - C,B,B,-1,b,单纯形表中变量,x,j,的系数列向量,：,B,-1,a,j,单纯形表中约束方程的右端项,：,B,-1,b,单纯形表中目标函数值,：,C,B,B,-1,b,单纯形表中变量,x,j,的检验数,：,C,j,- C,B,B,-1,a,j,单纯形法的矩阵描述,单纯形法的矩阵描述,继续讨论上例,X,B,x,1,x,2,x,3,x,4,x,5,b,x,1,1 0 0 1/4 0 4,x,5,0 0,-,2 0.5 1 4,x,2,0 1 0.5,-,1/8 0 2,-z,0,0 -3/2 -1/8 0 -14,C,B,=,2 0 3,C,B,B,-1,=,1.5 1/8 0,单纯形法的矩阵描述,例,用单纯形法求解下述线性规划问题,.,解,:,把原问题化为标准型,单纯形法的矩阵描述,用单纯形法求解如下,:,迭代,X,B,x,1,x,2,x,3,x,4,x,5,b R,x,3,1 2 1 0 0 8 4,x,4,4 0 0 1 0 16,-,x,5,0 4 0 0 1 12 3,-z,2,3 0 0 0 0,X,B,x,1,x,2,x,3,x,4,x,5,b R,x,3,1 0 1 0,-,0.5 2 2,x,4,4 0 0 1 0 16 4,x,2,0 1 0 0 1/4 3,-,-z,2,0 0 0 -3/4 -9,单纯形法的矩阵描述,迭代,迭代,X,*,=(4, 2),T,z,*,=14,X,B,x,1,x,2,x,3,x,4,x,5,b R,x,1,1 0 1 0,-,0.5 2,-,x,4,0 0,-,4 1 2 8 4,x,2,0 1 0 0 1/4 3 12,-z,0,0 -2 0,1/4 -13,X,B,x,1,x,2,x,3,x,4,x,5,b R,x,1,1 0 0 1/4 0 4,x,5,0 0,-,2 0.5 1 4,x,2,0 1 0.5,-,1/8 0 2,-z,0,0 -3/2 -1/8 0 -14,单纯形法的矩阵描述,线性规划问题的对偶问题,(Dual Problems),1.,对偶问题的提出,(Dual Problem),例,1,某工厂用两台机器生产三种产品,有关数据如下表,:,如何组织生产，使总利润最大？,甲,(m),乙,(m),丙,(m),限制条件,机器,I 1 1 1 135,机器,II 1 4 7 405,利润,2 3 11/3,x,1,x,2,x,3,-,分别生产甲、,乙、丙产品的数量,例,2,若另一工厂想要租赁这两台机器用于生产产品，那么该,工厂应该如何确定合理的租金呢？,线性规划问题的对偶问题,y,1,y,2,-,机器,I,与机器,II,的每台时的租金,例,1,与例,2,是一个问题的两个方面,两个线性规划模型是一对对偶问题,线性规划问题的对偶问题,2.,原问题与对偶问题的关系,对称性关系,例,3,求下列问题的对偶问题,对称性形式的对偶关系,线性规划问题的对偶问题,非对称性关系,练习：,线性规划问题的对偶问题,原,(,对偶,),问题,目标函数,max,z,=,CX,0,n,个变量,0,自由变量,m,个约束,AX,b,=,对偶,(,原,),问题,目标函数,min,w,=,Y,T,b,n,个约束,A,T,Y,C,T,=,0,m,个变量,0,自由变量,原问题与对偶问题对偶关系对照表,线性规划问题的对偶问题,例,4,求下列问题的对偶问题,线性规划问题的对偶问题,例,5,求下列问题的对偶问题,线性规划问题的对偶问题,考虑对称性关系的对偶：,对称性,对偶问题的基本性质,(Basic Properties),对偶问题的对偶是原问题。,弱对偶性,若原,(,对偶,),问题有无界解，则对偶,(,原,),问题无可行解,.,无界性,对偶问题的基本性质,原,对偶,原,对偶,不可行,不可行,无界,不可行,可行解是最优解时的性质,对偶定理,若原问题有最优解，相应的最优基为,B,则对偶问题也有最优解，且最,优解为,(,C,B,B,-,1,),T,；并且目标函数值相等，均为,C,B,B,-,1,b,.,对偶问题的基本性质,对偶问题的基本性质,变量对应关系,设原问题是,它的对偶问题是,则原问题单纯性表的检验数行对应其对偶问题的一个基解：,原问题,X,B,X,N,X,S,检验数,0,C,N,-C,B,B,-1,N,-C,B,B,-1,对偶问题,Y,T,S,1,-Y,T,S,2,-Y,T,例,已知用单纯形法求解下述线性规划问题所得最终表如下，试确,定该问题的对偶问题的最优解,.,对偶问题的基本性质,解,:,由已知得,C,B,=(2 0 3),因此，由对偶定理可得所求问题的对偶问题的最优解为：,X,B,x,1,x,2,x,3,x,4,x,5,b R,x,1,1 0 0 1/4 0 4,x,5,0 0,-,2 0.5 1 4,x,2,0 1 0.5,-,1/8 0 2,-z,0,0 -3/2 -1/8 0 -14,其中,x,3, x,4, x,5,为,松弛变量。,(,Y,*,),T,b,=?,对偶问题的基本性质,互补松弛性,令,原问题的可行解， 是对偶问题的可行解，则它们分别是原问题,与对偶问题的最优解的充要条件是,:,例,6,已知线性规划问题,且其最优解为,x*,1,=2,x*,2,=0,x*,3,=8.,试用对偶问题的性质求其对,偶问题的最优解。,对偶问题的基本性质,解,:,此线性规划问题的对偶问题是：,将,x*,1,=2,x*,2,=0,x*,3,=8,代入原线性规划问题的约束条件中，可知第一个约束,条件为严格不等式，则由互补松弛性得,y*,1,=0.,对偶问题的基本性质,又因,x*,1,x*,3,0,，,所以对偶问题的第一个约束条件以及第三个约束条件,均应取等式，即,8,y*,1,+4,y*,2,+2,y*,3,=60,，,y*,1,+1.5,y*,2,+0.5,y*,3,=20.,解之得,y*,2,=10,y*,3,=10.,因此，对偶问题的最优解为,y*,1,=0, y*,2,=10,y*,3,=10.,线性规划对偶问题的经济解释,-,影子价格,(Shadow Prices),设 与 分别是原问,题与对偶问题的最优解，则由对偶问题的基本性质有,由此，,变量 的,经济意义,是：,在其他条件不变的情况下，,第,i,种资源的单位改变量所引起的目标函数值的增加量,。,1,影子价格的解释,变量 的值代表对第,i,种资源的估价。这种估价不是资,源,i,的市场价格，而是具体工厂根据资源在生产中做出的贡,献而作的估价，称它为,“,影子价格,”,。,影子价格是对偶解的一个十分形象的名称，它既表明了对偶,解是对系统内部资源的一种客观估价，又表明它是一种虚,拟的价格，而不是真实的价格。,线性规划对偶问题的经济解释,-,影子价格,例 某工厂用三台机器生产两种产品,有关数据如下表,:,如何组织生产，使总利润最大？,甲,(m),乙,(m),可供资源,(,台时,),机器,I 1 2 8,机器,II 4 0 16,机器,III,0 4 12,利润,2 3,x,1,x,2,-,分别生产甲、,乙产品的数量,X,*,=(4, 2),T,z,*,=14,线性规划对偶问题的经济解释,-,影子价格,问题：若另一工厂想要租赁这三台机器用于生产产品，那么该,工厂应该如何确定合理的租金呢？,y,1,y,2,y,2,-,机器,I,、机器,II,与,机器,III,的每台时的租金,线性规划对偶问题的经济解释,-,影子价格,2,影子价格的作用,影子价格的大小反映了资源在系统内的稀缺程度,根据互补松弛性，某种资源的影子价格为,0,时，该种资源未充分利,用，仍有剩余；某种资源的影子价格不为,0,时，该种资源在生产中,已消耗完毕，目前比较稀缺，此时如果管理者增加该资源的供应,量，则总收益就会增加。,线性规划对偶问题的经济解释,-,影子价格,影子价格对市场有调节作用,在完全市场经济的条件下，当某种资源的市场价小于或等于影子,价格时，则企业应买进该资源以扩大再生产；反之，则应将已有,资源卖掉。所以“,影子价格,”,能为企业或部门提供今后,“,活动,”,的一,种经济信息。,线性规划对偶问题的经济解释,-,影子价格,
展开阅读全文