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

《北邮运筹学ch2-1 线性规划的对偶模型.ppt》由会员分享，可在线阅读，更多相关《北邮运筹学ch2-1 线性规划的对偶模型.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter2对偶问题对偶问题Dual Problem1.线性规划的对偶模型线性规划的对偶模型 DualModelofLP2.对偶性质对偶性质 Dualproperty3.对偶单纯形法对偶单纯形法 DualSimplexMethod4.灵敏度分析灵敏度分析 SensitivityAnalysis运筹学运筹学Operations Research2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage2of1912/20/2022在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问

2、题。【例例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：产品资源ABC资源限量986500547450832300764550每件产品利润1008070建立总收益最大的数学模型。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage3of1912/20/2022【解解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益

3、又太少。合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage4of1912/20/2022设y1，y2，y3及y4分别表示四种资源的单位增殖价格（售价成本增殖），总增殖最低可用min w=500y1+450y2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和

4、C有价格不可能小于零，即有yi0,i=1,4.从而企业的资源价格模型为2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage5of1912/20/2022这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage6of1912/20/2022【例例2.2】某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位

5、，C不少于180单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。营养成分一二三四五六需要量A1325144081180B24930251215150C1872134100180食物单价（元/100g）0.50.40.80.90.30.2含量食物2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage7of1912/20/2022【解解】设xj为每天第j种食物的用量，数学模型为现有一制药厂要生产一种包含A、B、C三种营养成分的合成药，

6、如何制定价格，使得此药既要畅销又要产值最大。设yi（i=1，2，3）为第i种营养成分的单价，则2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage8of1912/20/2022 影影子子价价格格(Shadowprice):上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影影子子价价格格，即对偶问题中的决策变量yi的值。2.1线性

7、规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage9of1912/20/2022由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有即yi是第i种资源的变化率，说明当其它资源供应量bk(ki)不变时，bi增加一个单位时目标值Z增加yi个单位。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage10of1912/20/2022例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加

8、2个单位。企业可利用影子价格调节生产规模。例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基B不变的条件下有上述经济含义，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之变化。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage11of1912/20/2022在例2.1中，原问题的最优解X（24.24，0，46.96）对偶问

9、题的最优解Y（10.6，0.91，0，0）最优值z=w=5712.12分析分析：1.y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来10.6元的利润；如果要出售该资源，其价格至少在成本价上加10.6元。2.y3=0说明增加第三种资源不会增加利润，因为第三种资源还有没有用完。问题问题：1.第三、四种资源的售价是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage12of1912/20/2022上面两种形式的线性规划称为

10、对称形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。对称形式对称形式的定义是：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。对称形式的线性规划的对偶问题亦是对称形式。以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage13of1912/20/2022【例例2.3】写出下列线性规划的对偶问题【解解】这是一个对称形式的线性规划，设Y=（y1，y2），则有2.1线性规划的对偶模型线性规划

11、的对偶模型 Dual model of LPCh2 Dual ProblemPage14of1912/20/2022从而对偶问题为对偶变量yi也可写成xi的形式。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage15of1912/20/2022【例例2.4】写出下列线性规划的对偶问题【解解】这是一个对称形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“”约束，即2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage16of1912/20/2022若给出的

12、线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按表21中的对应关系写出非对称形式的对偶问题。将上述原问题与对偶问题的对应关系列于表21例如，原问题是求最小值，按表2-1有下列关系：1.第i个约束是“”约束时，第i个对偶变量yj02第i个约束是“=”约束时，第i个对偶变量yi无约束；3当xj0时，第j个对偶约束为“”约束，当xj无约束时，第j个对偶约束为“=”约束。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage17of1912/20/2022原问题（或对偶问题）对偶问题（或原问题）目标函数（max）目标函数系数

13、（资源限量）约束条件系数矩阵A（AT）目标函数（min）资源限量（目标函数系数）约束条件系数矩阵ATA）变量n个变量第j个变量0第j个变量0第j个变量无约束约束n个约束第j个约束为第j个约束为第j个约束为=约束m个约束第i个约束第i个约束第i个约束为=变量m个变量第i个变量0第i个变量0第i个变量无约束表212.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage18of1912/20/2022【例例2.5】写出下列线性规划的对偶问题【解解】目标函数求最小值，应将表21的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表21的对应关系，对偶问题为：2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual ProblemPage19of1912/20/2022本节以实例引出对偶问题;介绍了如何写对称与非对称问题的对偶问题;1.您应该会写任意线性规划的对偶问题；2.深刻领会影子价格的含义，学会用影子价格作经济活动分析。作业：教材P74T2.3（1）（2）The End of Section 2.1对偶性质Exit返回首页