1008 灵敏度分析 影子价格ppt课件

1,对偶理论是线性规划的重要内容之一。对于每个线性规划问题,都有另一个线性规划问题(对偶)与之对应。,原问题和对偶问题紧密关联，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解.由此衍生出求解线性规划问题的另一种算法-对偶单纯形法.,对偶问题的解有着重要的经济意义，据此可以作一些灵敏度分析.,上一节内容回顾,2,第五节灵敏度分析,线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。,因此有必要来分析一下当这些数据发生波动时，对目前的最优解或最优值会产生什么影响，这就是所谓的灵敏度分析(结果分析)。,3,灵敏度分析主要讨论如下二类问题：若数据发生变化，最优解会有什么变化?数据集合在什么范围内波动,最优解保持不变？,详情可以参考如下教材:清华大学出版社华中科技大学出版社,4,例1、某工厂用甲,乙两种资源生产A,B,C三产品。已知生产单位产品所需要的资源量,所获利润以及每种资源的最大供给均列于表。试问如何安排生产计划，即A,B,C三种产品各生产多少吨，可使该厂所获得利润达到最大。,5,在此基础上,进一步考虑如下问题:,1.甲乙两种资源中哪种资源的拥有量是制约利润进一步提高的因素?,2.若在市场上能按比正常价格贵0.5(千元)的单价买到资源甲和乙,问为了进一步提高净利润是否应该买?,3.若欲通过提高售价提高产品B的单位利润,问B的单位利润要提高多少(千元),才能仍在追求最大利润的目标下考虑产品B的生产?,6,由强对偶定理可知，如果原问题有最优解,对偶最优解的经济解释影子价格,那么对偶问题也有最优解,而且他们的目标函数值相等,即有:,7,8,影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量,由互补松弛定理，在对偶最优解,中，第i种资源的,影子价格,反之如果第i种资源的影子价格,那么原问题的第i个约束为严格等式,即,这表明,这表明第i种资源已经用完，成为稀缺资源。,9,资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,10,例1、某工厂用甲,乙两种资源生产A,B,C三产品。已知生产单位产品所需要的资源量,所获利润以及每种资源的最大供给均列于表。试问如何安排生产计划，即A,B,C三种产品各生产多少吨，可使该厂所获得利润达到最大。,11,在此基础上,进一步考虑如下问题:,1.甲乙两种资源中哪种资源的拥有量是制约利润进一步提高的因素?,2.若在市场上能按比正常价格贵0.5(千元)的单价买到资源甲和乙,问为了进一步提高净利润是否应该买?,3.若欲通过提高售价提高产品B的单位利润,问B的单位利润要提高多少(千元),才能仍在追求最大利润的目标下考虑产品B的生产?,12,则得如下数学模型:,化为标准形:,13,最终表格为:,因此最优解为:,14,因此最优解为:,由于标准形的最优值为-27,故此时对应的最大利润为27千元.,在此基础上,进一步考虑如下问题:,1.甲乙两种资源中哪种资源的拥有量是制约利润进一步提高的因素?,2.若在市场上能按比正常价格贵0.5(千元)的单价买到资源甲和乙,问为了进一步提高净利润是否应该买?,3.若欲通过提高售价提高产品B的单位利润,问B的单位利润要提高多少(千元),才能仍在追求最大利润的目标下考虑产品B的生产?,即最优生产计划为:生产A产品5吨,C产品3吨,不生产B产品.,15,最优解为:,1.甲乙两种资源中哪种资源的拥有量是制约利润进一步提高的因素?,解:(方法一)由最终表格知,对偶问题的最优解为,由此可看出,这两种资源的拥有量都是制约利润进一步提高的因素.,16,因此这两种资源的拥有量都是制约利润进一步提高的因素.,(当然,在上面验证最优解下约束不等式是否取等号时,也可以直接代入验证,但是不如通过观察松弛变量的取值是否为零简单.),17,紧约束:也称有效约束,指将某可行解代入约束条件后使等号成立,该约束条件对该解而言称为紧约束条件,简称紧约束.,两个基本概念,松约束:也称无效约束,指将某可行解代入约束条件后不等号成立,该约束条件对该解而言称为紧约束条件,简称紧约束.,例如:例1中这两个约束条件,对当前的最优解而言都是紧约束条件.,18,2.若在市场上能按比正常价格贵0.5(千元)的单价买到资源甲和乙,问为了进一步提高净利润是否应该买?,在在这种最优利用的条件下,资源甲增加一个单位,利润将增加1/5=0.2千元.资源乙增加一个单位,利润将增加3/5=0.6千元.,因此,为了进一步提高净利润,应该只买乙,不买甲.,而目前在市场上能按比正常价格贵0.5(千元)的单价买到资源甲和乙,且,19,即底行中第二个系数增加一个(-C)项,再注意由初始表变为最终表是经若干次把底线以上的行倍加至底行而得到,故若将同样的运算过程应用到上表格上,底线以上的行没变化,底行不含C的地方数据不变,含C的地方只需在原来最终表的基础上加上(-C)即可,即,3.若欲通过提高售价提高产品B的单位利润,问B的单位利润要提高多少(千元),才能仍在追求最大利润的目标下考虑产品B的生产?,解:解这个问题时,可以设未知数C(千元)代表产品B单位利润增加额,再修改模型,于是原初始表变为:,20,若,则上面这个表满足最优性4个特点,运算终止,最优解不变.,若,那么上面这个表中底行存在负元素,需继续迭代,才能使,作基变量,即,取值才可以不为0.,所以,本问题的回答是,21,线性规划,基本概念,线性规划模型和标准形,线性规划问题的解,可行解基本解基本可行解最优解,线性规划问题的几何意义,求解方法,图解法,单纯形法,基本单纯形法,大M法、二阶段法,灵敏度分析及应用,本章小结,对偶单纯形法,21,22,重点、难点：,学习要求：,本章要求,LP的标准形、图解法、单纯