第三章对偶理论及灵敏度分析.ppt

《第三章对偶理论及灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《第三章对偶理论及灵敏度分析.ppt（117页珍藏版）》请在三一文库上搜索。

1、第三章 对偶理论及灵敏度分析,3.1.1 线性规划对偶问题 3.1.2 对偶问题的基本性质 3.1.3 影子价格 3.1.4 对偶单纯形法 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 3.2.3 参数线性规划,返回,继续,3.1.1 线性规划的对偶问题,一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系,实例：某家电厂家利用现有资源生产两种 产品， 有关数据如下表：,一、对偶问题的提出,如何安排生产， 使获利最多？,厂 家,设 产量 产量,设：设备A 元时 设备B 元时 调试工序 元时,收 购,付出的代价最小， 且对方能接受。,出让代价应不低于 用

2、同等数量的资源 自己生产的利润。,厂家能接受的条件： 收购方的意愿：,出让代价应不低于 用同等数量的资源 自己生产的利润。,厂 家,对 偶 问 题,原 问 题,收 购,厂 家,一对对偶问题,3个约束 2个变量,2个约束 3个变量,一般规律,特点： 1 2限定向量b 价值向量C （资源向量） 3一个约束 一个变量。 4 的LP约束“ ” 的 LP是“ ”的约束。 5变量都是非负限制。,其它形式 的对偶 ?,二、原问题与对偶问题的数学模型,1对称形式的对偶 当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。,情形一：,原问题,对偶问题,化为标准对称型,情形二：,证明,对偶,2、 非对称形式的

3、对偶 若原问题的约束条件是等式，则,原问题,对偶问题,推导:,原问题,根据对称形式的对偶模型,可直接写出上述问题的对偶问题:,令 ，得对偶问题为：,证毕。,三、原问题与对偶问题的对应关系,例:,对偶问题为,返回,结束,线性规划的对偶问题,返回,继续,3.1.2 对偶问题的基本性质,引例 对称性 弱对偶性 最优性 对偶性（强对偶性） 互补松弛性,对 偶 问 题,原 问 题,收 购,厂 家,引例,原问题化为极小问题，最终单纯形表：,对偶问题用两阶段法求解的最终的单纯形表,化为极小问题,原问题 最优解,对偶问题 最优解,原问题化为极小问题，最终单纯形表：,两个问题作一比较: 1.两者的最优值相同 2

4、.变量的解在两个单纯形表中互相包含 原问题最优解（决策变量） 对偶问题最优解（决策变量）,从引例中可见： 原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。,理论证明： 原问题与对偶问题解的关系,对偶问题的基本性质,一、对称定理： 定理： 对偶问题的对偶是原问题。,设原问题（1） 对偶问题（2）,二、弱对偶性定理： 若 和 分别是原问题（1）及对偶问题（2）的可行解，则有,证明：,对偶问题的基本性质,从弱对偶性可得到以下重要结论：,（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 （2）极小化问题（对偶问题

5、）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 （3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。,（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。 （5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 （6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,原问题,对偶问题,三、最优性定理： 若 和 分别是（1）和（2）的 可行解，且有 则 分别是（1）和（2）的最优解 。,则 为（1）的最优解， 反过来可知： 也是（2）的最优解。,证明：因为（1）的任一可行解 均满足,对偶问题的基本性质,四、对偶定理（强对偶性）： 若原

6、问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,对偶问题的基本性质,五、互补松弛性： 若 分别是原问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则： 即：,为最优解,原问题第i条约束,A的第i行,说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,另一方面：,对偶问题的第j条约束,互补松弛定理应用： （1）从已知的最优对偶解，求原问题最优解，反之亦然。 （2）证实原问题可行解是否为最优解。 （3）从不同假设来进行试算，从而研究原始、对

7、偶问题最优解的一般性质。 （4）非线性的方面的应用。,以上性质同样适用于非对称形式。,返回,结束,对偶问题的基本性质,返回,继续,3.1.3 影子价格,在单纯形法的每步迭代中，目标函数取值 ， 和检验数 中都有乘子 ，那么Y的经济意义是什么？,当线性规划原问题求得最优解 时，其对偶问题也得到最优解 ，且代入各自的目标函数后有：,是线性规划原问题约束条件的 右端项，它代表第 种资源的拥有量；,（3）,对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。,影子价格

8、的定义,1资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。,影子价格的经济意义,影子价格的经济意义,2影子价格是一种边际价格。 在（3）式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。,几何解释：引例图解法分析。,影子价格的经济意义,3资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化

9、，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,4在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,5从影子价格的含义上考察单纯形表的 检验数的经济意义。,（4）,影子价格的经济意义,6一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。,经济学研究如何管理 自己的稀缺资源,返回,结束,影子价格,3.1.4 对偶单纯形法,对偶单纯形法的基本思路 对偶单纯形法的计算步骤,返回,继续,对偶单纯

10、形法的基本思路,单纯形法的基本思路： 原问题基可行解 最优解判断,对偶问题的可行解,对偶问题 最优解判断,对偶单纯形法 基本思路,对偶单纯形法的计算步骤,线性规划问题,不妨设 为对偶问题的 初始可行基，则 。,若 ，即表中原问题和 对偶问题均为最优解，否则换基。,换基方法：,确定换出基变量 对应变量 为换出基的变量,确定换入基变量 为主元素， 为换入基变量,初始可行基,例、用对偶单纯形法求解线性规划问题：,对偶问题的 初始可行基,例、用对偶单纯形法求解线性规划问题：,使对偶问题基变量可行,换出,例、用对偶单纯形法求解线性规划问题：,最优解,例、用对偶单纯形法求解线性规划问题：,对偶单纯形法的优

11、点： 不需要人工变量； 当变量多于约束时，用对偶单纯形法可减少迭代次数； 在灵敏度分析中，有时需要用对偶单纯形法处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。,练习,用对偶单纯形法求解线性规划问题：,返回,结束,对偶单纯形法,3.2.1 灵敏度问题及其图解法,灵敏度问题 灵敏度分析图解法,灵敏度问题,背景： 线性规划问题中， 都是常数，但这些系数是估计值和预测值。 市场的变化 值变化； 工艺的变化 值变化； 资源的变化 值变化。,问题： 当这些系数中的一个或多个发生变化时，原最优解会怎样变化？ 当这些系数

12、在什么范围内变化时，原最优解仍保持不变？ 若最优解发生变化，如何用最简单的方法找到现行的最优解？,研究内容： 研究线性规划中， 的变化对最优解的影响。,研究方法： 图解法 对偶理论分析,仅适用于含2个变量的线性规划问题,在单纯形表中进行分析,线性规划模型,灵敏度分析图解法,x2,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),最优解 (3,6),4x1+ 6x2=48 2x1+ 2x

13、2 =18,灵敏度分析图解法,灵敏度分析 图解法,灵敏度分析 图解法,若 c1增加（c2 不变）,新的最优解,灵敏度分析 图解法,若 c1减少,新的最优解,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E,(斜率 = - 1),(斜率 = - 2/3),灵敏度分析 图解法,3.2.1 灵敏度问题及其图解法,结束,3.2.2 灵敏度分析,一、分析 的变化 二、分析 的变化 三、增加一个变量 的分析 四、增加一个约束

14、条件的分析 五、分析 的变化,研究内容： 研究线性规划中， 的变化对最优解的影响。,常用公式：,实例： 某家电厂家利用现有资源生产两种产品，有关数据如下表：,如何安排生产， 使获利最多？,厂 家,设 产量 产量,原问题 最优解,对偶问题最优解 （相差负号）,原问题的最终单纯形表：,一、分析 的变化,的变化仅影响 的变化。,1.5,2,问题1：当 该公司最优生 产计划有何变化？,最终单纯形表,最终单纯形表,换基后单纯形表为,最优解,问题2：设产品II利润为 ， 求原最优解不变时 的范围。,产品II利润为 时的最终单纯形表,二、分析 的变化,的变化仅影响 ，即原最优解的可行性可能会变化：,可行性不

15、变，则原最优解不变。,可行性改变，则原最优解改变， 用对偶单纯形法，找出最优解。,问题3：设备B的能力增加到32小时， 原最优计划有何变化？,代入单纯形表中,可行性改变，用对偶单纯形法换基求解。,主元,新的最优解,换基迭代得：,问题4：设调试工序可用时间为 小时，求 ，原最优解保持不变。,原最优解保持不变，则,三、增加一个变量 的分析,增加一个变量相当于增加一种产品。 分析步骤： 1、计算 2、计算 3、若 ，原最优解不变； 若 ，则按单纯形表继续迭代 计算找出最优解。,问题5：设生产第三种产品，产量为 件， 对应的 求最优生产计划。,解：,代入最终原单纯形表中,主元,换基后有：,四、增加一个

16、约束条件的分析,增加一个约束条件相当于增添一道工序。,分析方法：,将最优解代入新的约束中,（1）若满足要求，则原最优解不变；,（2）若不满足要求，则原最优解改变， 将新增的约束条件添入最终的 单纯形表中继续分析。,五、分析 的变化,若 对应的 变量 为基变量， B将改变。需引入人工变量求出 可行解，再用单纯形法求解。,若 对应的变量 为非基变量， 参见三的分析。,灵敏度分析的步骤归纳如下：,（1）将参数的改变计算反映到最终 单纯形表上； （2）检查原问题是否仍为可行解； （3）检查对偶问题是否仍为可行解； （4）按下表所列情况得出结论和决 定继续计算的步骤。,总之,练习：,某厂计划生产甲、乙、

17、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表：,单位产品 甲 乙 丙 可使用资源量 劳动力 1/3 1/3 1/3 1 材料 1/3 4/3 7/3 3 利润（元） 2 3 1,（1）确定最优的生产方案； （2）当 增大至多少时，丙产品安排生产； （3）增加3个劳动力，最优解是否改变？ （4）劳动力在哪个范围内变化，对利润值 的改变有利； （5）增加新的产品丁，需1个劳动力，1个 单位原料，利润3元。确定最优的生产方案。 （6）添加新约束： 最优解是否改变？,解：初始及最终单纯形表为,3.2.2 灵敏度分析,结束,3.2.3 参数线性规划,参数线性规划概念,当参数 或 沿某一

18、方向连续变动时，目标函数值z将随 或 的变动而呈线性变动，z是这个变动参数的线性函数，因而称为参数线性规划。,模型,目标函数的系数含有参数的线性规划模型,约束条件右端的常数项含有参数的LP模型,参数线性规划问题的分析步骤：,（1）令 求解得最终单纯形表； （2）将 或 项反映到最终单纯形表中去； （3）随 值的增大或减小，观察原问题或对偶 问题。 （4）重复第（3）步，一直到 值继续增大或减小 时，表中的解（基）不再出现变化时为止。,确定现有解（基）允许的 的变动范围；,当 的变动超出这个范围时，用单纯 形法或对偶单纯形法求新的解。,举例分析目标函数的系数 含有参数的线性规划问题,分析 值变化

19、时，下述参数线性规划 问题最优解的变化。,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优解保持不变的条件,当 时,当 时，换基得：,当 时，由原最终单纯形表,当 时，最终单纯形表,当 时，原最终单纯形表,当 时，最终单纯形表,目标函数值 随 值变化的情况,举例分析约束条件右端的常数项含 有参数的线性规划问题,分析 值变化时，下述参数线性规划 问题最优解的变化。,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优基不变条件是 最优值为,当 时,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优基不变条件是 最优值为,当 时,当 时 最优值为,当 时,当 时 最优值 当 时， 所在元素均为正， 故原问题无可行解,第三节 参数线性规划,结束,