(精品)第二章第四节-第五节对偶问题的经济意义与对偶单纯形方法.ppt

《(精品)第二章第四节-第五节对偶问题的经济意义与对偶单纯形方法.ppt》由会员分享，可在线阅读，更多相关《(精品)第二章第四节-第五节对偶问题的经济意义与对偶单纯形方法.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题单位产品的利润单位产品的利润（元元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）4 对偶的经济解释对偶的经济解释-影子价格影子价格对偶问题对偶问题资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格（种资源的影

2、子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=minw1、资源影子价格的性质、资源影子价格的性质 影子价格是根据资源在生产中做出的贡献而做出影子价格是根据资源在生产中做出的贡献而做出的估价，这种估价不是资源的市场价格。的估价，这种估价不是资源的市场价格。资源的市场价格是已知数，相对比较稳定，而它资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的于企业生产任务、产品结构等情况发生变化，资源的

3、影子价格也随之变化。影子价格也随之变化。最大利润的增量最大利润的增量/第第i种资源的增量种资源的增量=第第i种资源的边际利润种资源的边际利润即：即：影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于影子价格一定等于0注：注：所以可根据影子价格来确定优先使用哪种资源来所以可根据影子价格来确定优先使用哪种资源来增加总利润。增加总利润。影子价格是一种边际价格，它的值相当于在给定影子价格是一种边际价格，

4、它的值相当于在给定的生产条件下，的生产条件下，bi每增加一个单位时，目标函数每增加一个单位时，目标函数z（总（总利润）的增量。利润）的增量。可行域如图，点（可行域如图，点（3，3）是最优解，代入目标函数）是最优解，代入目标函数z*=15。(1)如果第一个约束右端顶增加如果第一个约束右端顶增加1，变为：，变为：(3,3)(3.5,3)(2.8,3.2)0以第一章机械厂最大利润问题为例解释以第一章机械厂最大利润问题为例解释表示该约束的直线由表示该约束的直线由移至移至，最优解，最优解不变，即设备不变，即设备B的边际价格为零。的边际价格为零。图中表示该约束的直线将由图中表示该约束的直线将由移至移至，相

5、应最优解的点变为（相应最优解的点变为（3.5，3），则），则z*=16，说明设备，说明设备A的边际价格为的边际价格为1。(2)若第二个约束右端项加若第二个约束右端项加1，变为，变为(3)若第三个约束的右端项加若第三个约束的右端项加1，变为，变为 ，直线直线将移至将移至，最优解的点变为（，最优解的点变为（2.8，3.2），），z*=15.2，即设，即设备备C影子价格为影子价格为1/5。隐含成本隐含成本表示生产一件产品所消耗的资源可以增加的利润表示生产一件产品所消耗的资源可以增加的利润y1y2ym2、产品的隐含、产品的隐含(机会机会)成本成本增加单位资源可以增增加单位资源可以增加的利润加的利润生产

6、一件产品消耗的资源生产一件产品消耗的资源在纯市场经济条件下，当第在纯市场经济条件下，当第i种资源的市场价格低于其影子价格时，种资源的市场价格低于其影子价格时，可以买进这种资源；相反当市场价格高于影子价格时，就可卖出这可以买进这种资源；相反当市场价格高于影子价格时，就可卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态一直到影子价格与市场价格保持同等水平时，才处于平衡状态。隐含成本隐含成本利润利润差额成本差额成本3、产品的差额成本（、产品的差额成本（Reduced Cos

7、t）差额成本差额成本=隐含成本隐含成本-利润利润,即检验数的负值即检验数的负值.利润大于隐含成本时，有利可图，检验数为正，可以安排生产（进基）；否则利润大于隐含成本时，有利可图，检验数为正，可以安排生产（进基）；否则不安排。但该项产品的生产活动并非无限制，而是增至其检验数为不安排。但该项产品的生产活动并非无限制，而是增至其检验数为0而止。而止。检验数为检验数为0时，利润等隐含成本，表明通过生产此产品增加总利润的可能已不存时，利润等隐含成本，表明通过生产此产品增加总利润的可能已不存在（某变量出基后不再进基）在（某变量出基后不再进基）。4、互补松弛关系的经济解释、互补松弛关系的经济解释在利润最大化

8、的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品隐含成本等于利润）安排生产的产品隐含成本等于利润（4）隐含成本大于利润的产品不安排生产）隐含成本大于利润的产品不安排生产 X*、Y*分别是原问题和对偶问题最优解的充要条件是分别是原问题和对偶问题最优解的充要条件是（1）若）若 yi*0，则，则 aij xj*=bi ；（；（2）若）若 aij xj*0，则，则 aij yi*=cj ；（；（4）若）若 aij yi*cj ，则，则 xj*=0.综上所述，对线性规划问题的求

9、解是确定资源的最综上所述，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。当估价，这种估价直接涉及资源的最有效利用。如在一个大公司的内部，可借助资源的影子价格确如在一个大公司的内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如在社会上可对一些最紧缺的下属企业经营的好坏。又如在社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上资源，借助影子价格规定使用这

10、种资源一单位时必须上交的利润额，以控制一些经济效益低的企业自觉地节省交的利润额，以控制一些经济效益低的企业自觉地节省使用紧缺的资源，使有限资源发挥更大的经济效益。使用紧缺的资源，使有限资源发挥更大的经济效益。5 对偶单纯形法对偶单纯形法一一.单纯单纯形法的重新解形法的重新解释释（称（称为对为对偶可行条件）偶可行条件）X*是最大化原是最大化原LP问题最优解的充要条件是同时满足问题最优解的充要条件是同时满足（称为原始可行条件）（称为原始可行条件）因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶从不可行向可行转化，一旦对偶可行，则达到最优

11、解。偶从不可行向可行转化，一旦对偶可行，则达到最优解。根据对偶根据对偶问题的对称性，可以在保持对偶可行下，经过迭代，逐步实现原始问题的对称性，可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。可行，以求得最优解。定义：定义：设设X为原问题（为原问题（1）的一个基本解，对应的基为）的一个基本解，对应的基为B，它所对应的检验数向量，它所对应的检验数向量则称则称X为原问题（为原问题（1）的一个正则解，对应的基矩阵）的一个正则解，对应的基矩阵B称称为正则基。为正则基。Step5:以以ark为主元素作换基迭代运算，方法与单纯形法完全相同，为主元素作换基迭代运算，方法与单纯形法完全相同，得到

12、新的单纯形表，返回步骤（得到新的单纯形表，返回步骤（2）。）。二、二、对偶单纯形法的计算步骤对偶单纯形法的计算步骤对偶单纯形法的思路：对偶单纯形法的思路：从一个正则解出发，用单纯形法迭代，迭代过程始终保持解的正则从一个正则解出发，用单纯形法迭代，迭代过程始终保持解的正则性，而使解的不可行性消失，所得的第一个可行解即为最优解。性，而使解的不可行性消失，所得的第一个可行解即为最优解。Step1：给定一个初始正则解（所有检验数给定一个初始正则解（所有检验数j 0），对应基为），对应基为B，建，建立初始单纯形表；立初始单纯形表；Step2：检查：检查b列元素，如果所有列元素，如果所有bi0，则已得到最

13、优解，停止计算。，则已得到最优解，停止计算。否则转入下一步；否则转入下一步；Step3：确定离基变量：设确定离基变量：设Step5:确定进基变量：设确定进基变量：设则第则第r方程对应的原基变量为离基变量，第方程对应的原基变量为离基变量，第r 行为主行；行为主行；则则xk为进基变量变量，第为进基变量变量，第k列为主列；列为主列；Step4:检查第检查第r 行系数，若所有行系数，若所有arj0,则原问题无可行解，否则转入下则原问题无可行解，否则转入下一步；一步；注注1：对偶单纯形法与单纯形法的不同之点：对偶单纯形法与单纯形法的不同之点：不要求模型中不要求模型中b0；先确定离基变量先确定离基变量xr

14、，再确定进基变量，再确定进基变量xk .注注2：对偶单纯形法适用对象：对偶单纯形法适用对象（b无限制）无限制）(3)进行灵敏度分析时，有时会用到此法进行灵敏度分析时，有时会用到此法.(1)maxZ=CX(C0)(或或minz=CX(C0)(2)当变量个数当变量个数约束个数时，可先转化为其对偶问题，再用约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之单纯形法或对偶单纯形法解之例例5.1 用对偶单纯形法求解下述线性规划问题用对偶单纯形法求解下述线性规划问题解解 先将问题改写为求目标函数极大化，并化为如下形式有先将问题改写为求目标函数极大化，并化为如下形式有列单纯形表，并用对偶单纯形

15、法求解：列单纯形表，并用对偶单纯形法求解：-12 -16 -15 0 0 CB 基基 b y y1 1 y y2 2 y y3 3 y y4 4 y y5 5 0 y y4 4 -2 0 y5 5 -3 3 -2 -4 0 1 0 -2 0 -5 0 1cj-zj-12 -16 -15 0 0 0 y y4 4 -2-15 y3 3 3/53/5 -2 -4 0 1 0 2/5 0 1 0 -1/5 cj-zj -6 -16 0 0 -3-12 y y1 1 1-15 y3 3 1/51/5 1 2 0 -1/2 0 0 -4/5 1 1/5 -1/5 cj-zj 0 -4 0 -3 -3 最优解：最优解：y1=1,y2=0,y3=1/5;minw=15.否否算 法 过 程初始正则解初始正则解检查可行检查可行是则停止是则停止得最优解得最优解选离基变量选离基变量检查检查是否无可是否无可行解行解是则停止是则停止否否无最优解无最优解选进基变量选进基变量计算检验数计算检验数