[其它]第2章对偶理论.ppt
《[其它]第2章对偶理论.ppt》由会员分享,可在线阅读,更多相关《[其它]第2章对偶理论.ppt(146页珍藏版)》请在三一文库上搜索。
1、第2章 对 偶 理 论 (Duality Theory),对偶问题的提出,线性规划的对偶理论,对偶问题的经济解释-影子价格,对 偶 单 纯 形 法,灵 敏 度 分 析,对偶问题的提出 定义:一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题,我们将其中一个称为原问题,另一个就称为对偶问题。,应用: 在某些情况下,解对偶问题比解原问题更加容易 对偶变量有重要的经济解释(影子价格) 作为灵敏度分析的工具 对偶单纯形法(从一个非可行基出发,得到线性规划问题的最优解) 避免使用人工变量(人工变量带来很多麻烦,两阶段法则增加一倍的计算量),例1、某工厂用A、B、C、D四种原料生产甲乙
2、两种产品,生产甲乙所需各种原料的数量、在一个计划期内各种原料的现有数量及单件产品的利润见下表,问应如何安排生产才能获得最大利润?,线性规划模型,分析问题:现从另一角度讨论该问题 假如某人要租赁该厂的四种原料生产这两种产品,此时需考虑:这四种原料的加价应如何确定才便于厂方和租赁者达成协议。,对于工厂:希望定价尽可能地高,但太高了人家不会租赁,所以只能期望,尽管我不生产,但收益不能低于自己生产所得,否则,不如自己生产而不租赁出去。,对于租赁者,当然希望定价尽可能地低,至少不应超过原来实际生产所得的利润,为了便于达成协议,就必须在保证原工厂利益不降低的情况下,总的价格尽可能地低。,即出售生产两种产品
3、的原料的价格不应低于自己生产所得的利润,同时为了不亏本,各种原料加价不能为负,即:,可得线性规划模型:,线性规划问题的对偶问题,线性规划问题的原问题,两个数学模型间的关系:,(1)原问题为求最大值,而对偶问题是求最小值;,(2)原问题的约束条件为“”,而对偶问题的约束条件为“”;,(3)原问题的目标函数系数为对偶问题的约束条件右端的常数项,而原问题的约束右端常数项为对偶问题的目标函数系数;,(4)原问题的约束条件中xi 的系数为对偶问题第i个约束条件的系数,例2 合理配料问题,某饲养场用n种饲料B1,B2, Bn配置成含有m种营养成分A1,A2, Am的混合饲料,其余资料如表所示。问应如何配料
4、,才能既满足需要,又使混合饲料的总成本最低?,假设工厂想把这m 种营养成分分别制成一种营养丸销售,问如何定价,以保证总收入为最多?,解: 显然为了保证销路,价格不能太高,设含一个单位的第i种营养成分的营养丸定价为yi(i=1,2,m).因为原来的饲料中,第j种饲料每单位的价格为cj(j=1,n),而它所含第i种营养成分的量为aij,即现在要用aij个单位的第i种营养丸才能代替它,因此,为了使饲养场愿意用营养丸来代替原来的饲料,必须使营养丸的价格满足,由于每一份饲料中必须含有bi个单位的第i种营养成分,因此这样一份代替饲料的总收入为,对于工厂来说,问题是如何确定每种营养丸的售价yi(i=1,m)
5、使在满足上述约束条件下工厂的总收入达到最大,则问题可归结为,对偶问题,原问题,两个数学模型间的关系:,(1)原问题为求最小值,而对偶问题是求最大值;,(2)原问题的约束条件为“”而对偶问题的约束条件为 “” ;,(3)原问题的目标函数系数为对偶问题的约束条件右端的常数项,而原问题的约束右端常数项为对偶问题的目标函数系数;,(4)原问题的约束条件xi 的系数为对偶问题第i个约束条件的系数,对称型对偶问题,二、线性规划的对偶理论,(一)对偶问题的形式,变量均具有非负约束,其约束条件当目标函数求极大时均取“”号,当目标函数求极小时均取“”号。,P,D,矩阵形式,例1、写出线性规划问题的对偶问题,解:
6、首先将原式变形,例2、原问题,解:原问题化为,例3、求下列问题的对偶问题,原问题可化为:,对偶问题为:,综上所述,其变换形式归纳如下:,例4、线性规划问题如下:,对偶问题是,练习:,1、对称性定理:对偶问题的对偶是原问题。,(二)、对偶问题的性质,2、弱对偶原理(弱对偶性):设 和 分别是问题(P)和(D)的可行解,则必有,推论.若 和 分别是问题(P)和(D)的可行解,则 是(D)的目标函数最小值的一个下界; 是(P)的目标函数最大值的一个上界。,因,是原问题的可行解,所以满足约束条件,即,原问题的对偶问题是 min w=Yb; YA C;Y 0,推论.在一对对偶问题(P)和(D)中,若其中
7、一个问题可行但目标函数无界,则另一个问题不可行。,例1、,试估计它们目标函数的界,并验证弱对偶性原理。,(P),解,例2、已知,试用对偶理论证明原问题无界。,例3、已知,显然,这两个问题都无可行解。,3、最优性判别定理:,例如,在例1中,可找到X*=(0,0,4,4),Y*=(1.2,0.2),则Z=28,W=28.故X* ,Y*分别是 P和D 的最优解。,4、对偶定理(强对偶性): 若原问题有最优解,则对偶问题也有最优解,且目标函数的最优值相等。,综上所述,一对对偶问题的关系,只能有下面三种情况之一出现: .都有最优解,分别设为X* 和 Y*,则必有CX* =Y*b; . 一个问题无界,则另
8、一个问题无可行解; .两个都无可行解。,5、互补松弛定理: 设X*和Y*分别是问题P 和 D 的可行解,则它们分别是最优解的充要条件是,同时成立,设原问题和对偶问题的标准型是,证 由于 z=(YA-YS)X =YAX-YSX ,w=Y(AX+XS)=YAX+YXS,若Y*XS=0,YSX*=0,则Y*b=CX*,由性质3知X*,Y*是最优解。,若X*,Y*是原问题和对偶问题的最优解,根据性质4,知,CX*=Y*AX*=Y*b,必有Y*XS=0,YSX*=0.,例4、已知,试通过求对偶问题的最优解来求解原问题的最优解。,解:对偶问题为,此方程组有无穷多组解,例5、已知原问题的最优解为X* =(0
9、,0,4),Z=12 试求对偶问题的最优解。,解:,(1),(2),(3),将X* =(0 , 0 ,4)代入原问题中,有下式:,所以,根据互补松弛条件,必有y*1= y*2=0,代入对偶问题 (3)式, y3 =3。因此,对偶问题的最优解为 Y*=(0 ,0 ,3),W=12。,6、对偶问题的解,引入xs ,构建初始基变量,然后用单纯形法求解。当所有非基变量的检验数满足j0 ,则求得最优解。此时, xs对应的s 为- Y* ,故求对偶问题的最优解Y* ,只要将最优单纯形表上xs 对应的检验数反号即可。,(1),例1、,初 始 表,最终表,由上表可知: X*=(50/7 , 200/7),Z=
10、4100/7 对偶问题的最优解: Y*=(0 ,32/7 , 6/7),W=4100/7 也就是外加工时的收费标准。,此时,矩阵A中没有现成的单位矩阵I作为可行基,必须通过加入人工变量来凑一个单位矩阵,再用大M法或两阶段法求解。,CB,XB,b,CB,XB,B-1b,CB,XB,CN,XN,CI,XI,I,B-1N,B-1,-z,-CBB-1b,0,CN-CBB-1N,CI-CBB-1,例2、,所以, X*=(4 ,1 ,9),Z = 2, y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=(1/3 ,1/
11、3 , 2/3) W = 2,初始基变量的检验数4 =1/3,6 =1/3M, 7 =2/3M,三、对偶问题的经济解释影子价格,目标函数最优值变为:,也可以写成:,其经济意义是:在其它条件不变的情况下,单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。,也可以理解为目标函数最优值对资源的一阶偏导数(但问题中所有其它数据都保持不变)。,例1、某工厂用A、B、C三种原料生产甲乙两种产品,生产甲乙所需各种原料的数量、在一个计划期内各种原料的现有数量及单件产品的利润见下表,问应如何安排生产才能获得最大利润?,其对偶问题,原问题的最优解为 X*=(50/7 ,
12、 200/7),Z*=4100/7 对偶问题的最优解: Y*=(0 ,32/7 , 6/7),W*=4100/7,即原问题中第1种资源(钢材)的影子价格y1*=0,第2种资源(煤炭)的影子价格为y2*=32/7,第3种资源(设备台时)的影子价格为y3*=6/7,即在现有资源的基础上,若再增加1吨煤,可使总利润增加32/7万元,若再增加一个台时,可使总利润增加6/7万元,但若增加1吨钢材,将不会使总利润增加。,之所以出现上述几种不同情况,由互补松弛条件可知,,这说明按最优生产计划进行生产,现有资源中的煤炭和设备台时已经全部用完而没有剩余,因此,若再增加这两种资源,肯定会给工厂带来新的收益。,若再
13、增加这种资源,只能造成积压,而不会使工厂增加收益。,bi 代表第i种资源的拥有量;yi*代表在资源最优利用条件下对第i种资源的单位估价。这种估价不是资源的市场价格,而是根据资源在生产中作出的贡献而作的估价。,一、影子价格的概念,设 xj 表示第 j 种产品每天的产量,设 yj 表示第 j 种原料的收费单价,由对偶定理知当P问题求得最优解X*时,D问题也得到最优解Y*,且有,影子价格,一、影子价格的概念,由 得,说明 的值相当于在资源得到最优 利用的生产条件下, 每增加一个 单位时目标函数z的增量,边际价格,说明若某资源 未被充分利用,则该种资源的影子价格为0;,若某资源的影子价格不为0,则说明
14、已有资源已消耗完毕。,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,Y*T= CBB-1,CBB-1,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,若原料A增加1单位,该厂按最优计划安排生产可多获利200元; 若原料B增加1单位,可多获利100元; 原料C本已剩余,再增加不会带来收益。,1、指示企业内部挖潜的方向,影子价格能说明增加哪种资源对增加经济效益最有利,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,2、在企业经营决策中的作用,当某种资源的影子价 格高于市场价格时: 当某种资源的影子价 格低于市场价格时:,企业
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其它 对偶 理论
链接地址:https://www.31doc.com/p-2001904.html