第2章789对偶理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 线性规划问题,2.5,对偶理论,1,本节研究、解决三个问题：,1,、如何写出对偶问题；,2,、原问题与对偶问题之间的关系；,3,、对偶单纯形法（解线性规划问题的第,4,种方法）,2,2.5.1,对偶问题的提出,例,1,生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,产品,A,产品,B,资源限量,劳动力,设 备,原材料,9,4,3,4,5,10,360,200,300,利润,（元,/,kg,）,70,120,3,例,1,模型,问题：如何安排生产计划，使得获利最多？,步骤：,1,、确定决策变量：设生产,A,产品,x,1,kg,，,B,产品,x,2,kg,2,、,确定目标函数：,max Z=70X,1,+120X,2,3,、,确定约束条件：人力约束,9X,1,+4X,2,360,设备约束,4X,1,+5X,2,200,原材料约束,3X,1,+10X,2,300,非负性约束,X,1,0,X,2,0,4,例,1,另一角度分析：成本角度,利润大的另一方面是什么：成本越小！因此，我们可以试着从成本角度来分析生产决策者的心态！现在资源的数量已经定了，那么我们可以从价格来着手！,产品,A,产品,B,资源限制,劳动力,设备,原材料,9,4,3,4,5,10,360,200,300,单位利润,70,120,5,目 标 分 析,设,劳动力每个工时收费,Y,1,元，设备台时费用,Y,2,元，原材料附加费,Y,3,元。,现在我们的目标变成下面这个式子：,min,w=360y,1,+200y,2,+300y,3,那么约束条件是什么呢？,6,约束条件分析,单个因素的收入最大：即投入于产品,A,的资源收入要大于,A,的销售收入，投入于产品,B,的资源收入要大于,B,的销售收入，即,9y,1,+4y,2,+3y,3,70,4y,1,+5y,2,+10y,3,120,从整个问题来看，,1,、总的投入最低，,2,、投入品的价值也要得到合理体现！综合起来得到问题模型！,7,问题模型,Min,w=360y,1,+200y,2,+300y,3,s.t.9y,1,+4y,2,+3 y,3,70,4y,1,+5y,2,+10y,3,120,y,1,，y,2,，y,3,0,这个线性规划问题称为例,1,的（称为原问题）,对偶问题,。,8,一般形式的线性规划问题，写出其对偶问题的规则是什么？,课堂讲解第,44,页；,要求：看到原问题，能立即写出其对偶形式；,9,原问题与对偶问题比较,原问题：对偶问题：,maxZ,=70X,1,+120X,2,min,=360y,1,+200y,2,+300y,3,9X,1,+4X,2,360,9y,1,+4y,2,+3y,3,70,(1),4X,1,+5X,2,200,4y,1,+5y,2,+10y,3,120 (2),3X,1,+10X,2,300,X,1,0,X,2,0,y,1,0,y,2,0,y,3,0,10,2.5.2,对偶问题表示,根据上述例题可见，对于形如如下形式的线性规划问题：,我们可以马上得出,它的对偶问题：,其中：,A,T,、,b,T,分别是原,LP,中的约束条件矩阵,A,的转置矩阵与约束条件中右端向量的转置,(,即为行向量,),。,11,线性规划问题与其对偶问题的相关性,原问题的约束条件的个数,m,就是对偶问题的变量的个数；,原问题的变量的个数,n,就是对偶问题的约束条件的个数；,若原问题的目标函数是,Max,型，则对偶问题的目标函数必是,Min,型。,它们二者的最优目标函数值相等。,12,2.5.3,一般,LP,的对偶问题（书本,P45,定义,2.5.1,）,原问题（,P,）：,对偶问题（,D,）：,min,c,T,x,max,b,T,y,s.t.,a,i,T,x,=b,i,i=1,p s.t.y 0,a,i,T,x,b,i,i=p+1,m,y 0,x,j,0 j=1,q,A,j,T,y,c,x,j,0 j=q+1,n,A,j,T,y,=c,13,对偶规则,原问题有,m,个约束条件,对偶问题有,m,个变量,原问题有,n,个变量,对偶问题有,n,个约束条件,原问题的价值系数,对偶问题的右端项,原问题的右端项,对偶问题的价值系数,原问题的系数矩阵转置后为对偶问题系数矩阵,14,对偶规则,对偶问题,原问题,目标函数,max,min,目标函数,约束条件,=,变量,无约束,变量,无约束,约束条件,=,15,2.5.4,对偶问题的基本性质,对偶定理,2.5.1,：若一个,LP,问题有最优解，则它的对偶问题也有最优解，且目标函数值相等。,对称性：对偶问题与原问题互为对偶。,无界性：原问题无界，对偶问题无可行解,原问题与对偶问题：,原始 对偶,有最优解,问题无界,无可行解,有最优解,1,X,X,问题无界,X,X,3,无,可行解,X,3,2,16,2.5.5,对偶变量的经济解释,对偶变量,yi,在经济上表示原问题第,i,种资源的边际贡献，即当,第,i,种资源增加一个单位时，相应的目标,值,z,的增量。,对偶问题的最,优解,yi,*,是,原问题第,i,种资源的,影子价格,应用,:1.,出租资源或设备时，租金价格的设定,(,至少,高于该资源在企业内的影子价格,),2.,企业内资源,I,的存量,设定,(,当资源,I,的,影子价,格,市场价格时，可买进该资源；否则卖出,),3.,调整资源的分配量以增加利润,17,2.5,（,1,）对偶问题,要求：,了解,LP,对偶问题的实际意义,掌握对偶问题的建立规则与基本性质,了解对偶最优解的计算及其经济解释,18,第,2,章 线性规划问题,2.5,（,2,）对偶单纯形法,19,对偶理论,证明：定理,2.5.1,（黑板讲解）,对偶单纯形法（黑板讲解）,20,求解,LP,问题的四种方法,图解法,单纯形法,两阶段法,对偶单纯形法,21,对偶单纯形法,黑板讲解,22,2.6,灵敏度分析,黑板讲解,23,