北邮运筹学ch2-1 线性规划的对偶模型

,2.1,线性规划的对偶模型,Dual model of LP,Ch2 Dual Problem,Page,*,of 19,*,Chapter 2,对偶问题,Dual Problem,1.,线性规划的对偶模型,Dual Model of LP,2,.,对偶性质,Dual property,3,.,对偶单纯形法,Dual Simplex Method,4,.,灵敏度分析,Sensitivity Analysis,运筹学,Operations Research,在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。,【,例,2.1,】,某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：,产品,资源,A B C,资源限量,9 8 6,500,5 4 7,450,8 3 2,300,7 6 4,550,每件产品利润,100 80 70,建立总收益最大的数学模型。,【,解,】,设,x,1,，,x,2,，,x,3,分别为产品,A,，,B,，,C,的产量，则线性规划数学模型为：,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。,设,y,1,，,y,2,，,y,3,及,y,4,分别表示四种资源的单位增殖价格（售价成本增殖），总增殖最低可用,min,w,=500,y,1,+450,y,2,+300,y,3,+550,y,4,表示。企业生产一件产品,A,用了四种资源的数量分别是,9,，,5,，,8,和,7,个单位，利润是,100,企业出售这些数量的资源所得的利润不能少于,100,，即,同理，对产品,B,和,C,有,价格不可能小于零，即有,y,i,0,i,=1,4.,从而企业的资源价格模型为,这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。,【,例,2.2,】,某人根据医嘱，每天需补充,A,、,B,、,C,三种营养，,A,不少于,80,单位，,B,不少于,150,单位，,C,不少于,180,单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。,营养成分,一,二,三,四,五,六,需要量,A,13,25,14,40,8,11,80,B,24,9,30,25,12,15,150,C,18,7,21,34,10,0,180,食物单价（元,/100,g,）,0.5,0.4,0.8,0.9,0.3,0.2,含量 食物,【,解,】,设,x,j,为每天第,j,种食物的用量，数学模型为,现有一制药厂要生产一种包含,A,、,B,、,C,三种营养成分的合成药，如何制定价格，使得此药既要畅销又要产值最大。,设,y,i,（,i,=1,，,2,，,3,）,为第,i,种营养成分的单价，则,影子价格,(,Shadow price):,上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为,影子价格,，即对偶问题中的决策变量,y,i,的值。,由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有,即,y,i,是第,i,种资源的变化率，说明当其它资源供应量,b,k,(ki),不变时，,b,i,增加一个单位时目标值,Z,增加,y,i,个单位。,例如，第一种资源的影子价格为,y,1,=2,，,第二种资源的影子价格为,y,2,=2,，,即当第一种资源增加一个单位时，,Z,增加,2,个单位，当第二种资源增加一个单位时，,Z,增加,2,个单位。,企业可利用影子价格调节生产规模。例如，目标函数,Z,表示利润（或产值），当第,i,种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基,B,不变的条件下有上述经济含义，当某种资源增加或减少后，最优基,B,可能发生了变化，这时,y,i,的值也随之变化。,在例,2.1,中，原问题的最优解,X,（,24.24,，,0,，,46.96,）,对偶问题的最优解,Y,（,10.6,，,0.91,，,0,，,0,）,最优值,z=w=5712.12,分析,：,1.,y,1,=10.6,说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来,10.6,元的利润；如果要出售该资源，其价格至少在成本价上加,10.6,元。,2.,y,3,=0,说明增加第三种资源不会增加利润，因为第三种资源还有 没有用完。,问题,：,1.,第三、四种资源的售价是多少，是否不值钱？,2.,如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？,上面两种形式的线性规划称为对称形式。,原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。,对称形式,的定义是：,目标函数求极大值时，所有约束条件 为号，变量非负；,目标函数求极小值时，所有约束条件为号，变量非负。,对称形式的线性规划的对偶问题亦是对称形式。,以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。,【,例,2.3,】,写出下列线性规划的对偶问题,【,解,】,这是一个对称形式的线性规划，设,Y,=,（,y,1,，,y,2,），,则有,从而对偶问题为,对偶变量,y,i,也可写成,x,i,的形式。,【,例,2.4,】,写出下列线性规划的对偶问题,【,解,】,这是一个对称形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“”约束，即,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按表,2,1,中的对应关系写出非对称形式的对偶问题。,将上述原问题与对偶问题的对应关系列于表,2,1,例如，原问题是求最小值，按表,2-1,有下列关系：,1.,第,i,个约束是“”约束时，第,i,个对偶变量,y,j,0,2,第,i,个约束是“,=”,约束时，第,i,个对偶变量,y,i,无约束；,3,当,x,j,0,时，第,j,个对偶约束为“”约束，当,x,j,无约束 时，第,j,个对偶约束为“,=”,约束。,原问题（或对偶问题）,对偶问题（或原问题）,目标函数（,max,）,目标函数系数（资源限量）,约束条件系数矩阵,A,（,A,T,）,目标函数（,min,）,资源限量（目标函数系数）,约束条件系数矩阵,A,T,A,）,变,量,n,个变量,第,j,个变量,0,第,j,个变量,0,第,j,个变量无约束,约,束,n,个约束,第,j,个约束为,第,j,个约束为,第,j,个约束为,=,约,束,m,个约束,第,i,个约束,第,i,个约束,第,i,个约束为,=,变,量,m,个变量,第,i,个变量,0,第,i,个变量,0,第,i,个变量无约束,表,2,1,【,例,2.5,】,写出下列线性规划的对偶问题,【,解,】,目标函数求最小值，应将表,2,1,的右边看作原问题，左边是对偶问题，原问题有,3,个约束,4,个变量，则对偶问题有,3,个变量,4,个约束，对照表,2,1,的对应关系，对偶问题为：,本节,以实例引出对偶问题,;,介绍了如何写对称与非对称问题的对偶问题,;,1.,您应该会写任意线性规划的对偶问题；,2.,深刻领会影子价格的含义，学会用影子价格作经济活动分析。,作业：教材,P74 T2.3,（,1,）（,2,）,The End of Section 2.1,对偶性质,Exit,返回首页,