管理运筹学课件第3章对偶规划.ppt

《管理运筹学课件第3章对偶规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学课件第3章对偶规划.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 对偶规划对偶规划10/27/20221教学目标与要求教学目标与要求n【教学目标】【教学目标】n通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。n【知识结构】【知识结构】10/27/20222本章主要内容本章主要内容 n3.1 线性规划的对偶模型线性规划的对偶模型n3.1.1 对偶问题对偶问题n3.1.2 线性规划对偶模型线性规划对偶模型n3.1.3 对偶问题的基本性质对偶问

2、题的基本性质n3.2 对偶单纯形法简介对偶单纯形法简介n3.3 影子价格影子价格n3.4 灵敏度分析灵敏度分析n3.4.1 价值系数的变化分析价值系数的变化分析n3.4.2 右端常数的变化分析右端常数的变化分析n3.4.3 增加一个新变量的分析增加一个新变量的分析n3.4.4 增加新的约束条件的分析增加新的约束条件的分析n3.5 如何看计算机求解报告如何看计算机求解报告n本章小结本章小结10/27/20223导入案例导入案例出租还是自己组织生产？出租还是自己组织生产？第第2章导入案例中的数学模型章导入案例中的数学模型任何一个线性规划问题都存在一任何一个线性规划问题都存在一个伴生的线性规划问题，

3、我们称个伴生的线性规划问题，我们称之为之为“对偶对偶”。本章将讨论对偶。本章将讨论对偶问题模型的建立、影子价格及敏问题模型的建立、影子价格及敏感性分析。感性分析。现在换个角度讨论这个问题。现在换个角度讨论这个问题。假若由于某种原因，该企业打算放弃生产产品的项目，而将所有设备出租，假若由于某种原因，该企业打算放弃生产产品的项目，而将所有设备出租，收取租金。那么，在考虑到设备出租市场竞争条件下，如何确定三种设备收取租金。那么，在考虑到设备出租市场竞争条件下，如何确定三种设备单位台时的租金，才能使企业不至于蚀本。单位台时的租金，才能使企业不至于蚀本。问题：问题：1.如何建立该问题的数学模型？如何建立

4、该问题的数学模型？3.用什么方法对该问题模型求解？用什么方法对该问题模型求解？10/27/202243.1.1 对偶问题对偶问题原始规划原始规划设：两种设备单位台时租金分别为设：两种设备单位台时租金分别为 y1,y2由于承租方是理智的，会把租金压至最由于承租方是理智的，会把租金压至最低。故出租方在满足上述二约束情况下，低。故出租方在满足上述二约束情况下，至少出租总收入（目标函数）为至少出租总收入（目标函数）为约束一：生产甲产品的利润不大于放弃生约束一：生产甲产品的利润不大于放弃生产而出租的租金收入产而出租的租金收入约束二：生产乙产品的利润不大于放弃生约束二：生产乙产品的利润不大于放弃生产而出租

5、的租金收入产而出租的租金收入对偶规划对偶规划称（称（2）为（）为（1）的对偶，也称（）的对偶，也称（1）为（）为（2）的对偶。）的对偶。10/27/202253.1.2 对偶问题的数学模型对偶问题的数学模型（1）对称形式对偶问题）对称形式对偶问题 原问题原问题 对偶问题对偶问题10/27/202263.1.2 对偶问题的数学模型对偶问题的数学模型（2）非对称形式对偶问题）非对称形式对偶问题【例【例3.1】写出下列线性规划的对偶规划。写出下列线性规划的对偶规划。对偶模型：对偶模型：10/27/202273.1.3 对偶问题的基本性质对偶问题的基本性质 10/27/202283.2 对偶单纯形法简

6、介对偶单纯形法简介10/27/202293.2 对偶单纯形法简介对偶单纯形法简介标准化标准化（若（若乘乘-1）计算检验数计算检验数所有所有0?Yes所有所有b0?不符合对偶单纯形法不符合对偶单纯形法条件，改用大条件，改用大M法法No结束结束Yes找到最找到最优解优解No找出最小找出最小bkxk为离去变量为离去变量所有所有akj0?s=minakj/j|j0，xs入入基，迭代得新单纯形表基，迭代得新单纯形表No无可无可行解行解Yes10/27/2022103.2 对偶单纯形法简介对偶单纯形法简介【例【例3.2】用对偶单纯形法解】用对偶单纯形法解解解 标准化标准化初始单纯形表初始单纯形表第第1次迭

7、代次迭代第第2次迭代次迭代最优解最优解最优值最优值2010/27/2022113.2 对偶单纯形法简介对偶单纯形法简介【例【例3.3】用对偶单纯形法解】用对偶单纯形法解B20A2j0无可行解无可行解10/27/2022123.3 影子价格影子价格导入案例原问题的解如图导入案例原问题的解如图.对偶问题的解对偶问题的解10/27/2022133.3 影子价格影子价格原问题原问题 bi代表第代表第i种资源拥有量种资源拥有量 yi 代表第代表第i种资源种资源的估价，该估价并非市价格，而是在生产中的估价，该估价并非市价格，而是在生产中的单位贡献所做的估价的单位贡献所做的估价,称为影子价格。其称为影子价格

8、。其含义：含义：（1）资源的市场价格由供求关系决定，而）资源的市场价格由供求关系决定，而它的影子价格则有赖于资源的利用情况。它的影子价格则有赖于资源的利用情况。（2）影子价格是一种边际价格。）影子价格是一种边际价格。（3）资源的影子价格实际上又是一种机会）资源的影子价格实际上又是一种机会成本。成本。（4）当影子价格为）当影子价格为0时，表明该种资源未得时，表明该种资源未得到充分利用；当影子价格不为到充分利用；当影子价格不为0时，表明该时，表明该种资源已耗费完毕。种资源已耗费完毕。（5）在一个大公司内部，可借助资源的影）在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有子价格

9、确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。限资源的使用和考核下属企业经营的好坏。对偶问题对偶问题10/27/2022143.4 灵敏度分析灵敏度分析n线性规划的各个参数A，C，b往往是根据统计数据测算的，不可能完全准确，而且随着实际情况变化。灵敏度分析是指各参数变化对最优解的影响。10/27/2022153.4.1 价值系数价值系数cj的变化分析的变化分析由式由式3-7 可知，可知，cj变化仅影响检验数。敏感性分析是求变化仅影响检验数。敏感性分析是求检验数符号不变（最优基不变）时检验数符号不变（最优基不变）时cj的允许变化范围。的允许变化范围。【例【例3.4】由下述

10、模型的最终单纯形表求最优基不变的由下述模型的最终单纯形表求最优基不变的c2允许变化范围。允许变化范围。令令c2=4+c，有：有：若保持检验数非正，要求若保持检验数非正，要求：即即c2的允许变化范围：的允许变化范围：2.5,510/27/2022163.4.2 右端项右端项bi的变化分析的变化分析设设 由式由式3-8，若，若 则最优基保持不变则最优基保持不变.【例【例3.5】由由例例3.4最终单纯形表求最优基不变的最终单纯形表求最优基不变的b3允许变化范围。允许变化范围。初初始始基基最最优优基基即即b3的允许变化范围：的允许变化范围：40,5010/27/2022173.4.3 增加一个新变量的

11、分析增加一个新变量的分析10/27/2022183.4.3 增加一个新变量的分析增加一个新变量的分析在操作上：由在操作上：由 若大于若大于0应安排生产。应安排生产。【例【例3.6】在例在例3.4 中增加一个新产品是否可行。其消耗系数列向量中增加一个新产品是否可行。其消耗系数列向量p6=（3/2，1，1/2）及价值系数）及价值系数c6=3.10/27/2022193.4.4 增加一个新的约束分析增加一个新的约束分析增加一个新的约束后，线性规划的可行域只会变小，不会变大，最优值增加一个新的约束后，线性规划的可行域只会变小，不会变大，最优值只能变差，不会变的更好。因此如果原最优解只能变差，不会变的更

12、好。因此如果原最优解X*满足新的约束条件，则满足新的约束条件，则X*仍然是最优解；否则继续进行迭代。仍然是最优解；否则继续进行迭代。【例【例3.7】在例中增加一个新的约束在例中增加一个新的约束引入松弛变量引入松弛变量 添加到最终单纯形表中。添加到最终单纯形表中。将基向量变成单位向量。将基向量变成单位向量。10/27/2022203.5 如何看计算机求解报告如何看计算机求解报告【例【例3.8】Global optimal solution found.Total solver iterations:2Variable ValueReduced CostRowSlack or Surplus Du

13、al Price3Ranges in which the basis is unchanged:Objective Coefficient RangesCurrent Allowable AllowableVariable CoefficientIncreaseDecreaseX(2)1.0000002.000000INFINITY Righthand Side RangesRow CurrentAllowableAllowableRHSIncrease Decrease23 最优值最优值迭代次数迭代次数最优解最优解缩减成本（缩减成本（Reduced Cost）指在资源总量不变指在资源总量不变

14、的情况下，某一个变量在最的情况下，某一个变量在最优解的基础上增加优解的基础上增加1个单位个单位时，目标成本增加量。由求时，目标成本增加量。由求解结果可见，解结果可见，X(2)=0，其缩，其缩减成本为减成本为2，表示如果，表示如果X(2)入基后，每增加入基后，每增加1个单位，个单位，成本将增加成本将增加2个单位。个单位。松弛或剩余变量（松弛或剩余变量（Slack or Surplus）反映了资源的利用情反映了资源的利用情况。若松弛变量为况。若松弛变量为0，表示该资源，表示该资源已耗费完毕，若大于已耗费完毕，若大于0，表示尚有，表示尚有剩余。本例剩余。本例2个约束的松弛变量个约束的松弛变量（第（第

15、2、3行）均为行）均为0，表示两种资，表示两种资源均已耗费完毕。而第源均已耗费完毕。而第1行是生产行是生产一个单位产品所消耗的各项资源一个单位产品所消耗的各项资源的影子价格的总和，称为产品的的影子价格的总和，称为产品的隐含成本。隐含成本。影子价格（影子价格（Dual Price）的含义）的含义见节见节3.3。当松弛变量为。当松弛变量为0时，影时，影子价格大于子价格大于0。目标系数当前值目标系数当前值保持最优基不变时允许增量保持最优基不变时允许增量保持最优基不变时允许减量保持最优基不变时允许减量10/27/202221本章小结本章小结n 本本章章主主要要内内容容包包括括线线性性规规划划对对偶偶问

16、问题题；线线性性规规划划原原模模型型与与对对偶偶模模型型之之间间的的结结构构关关系系；基基于于线线性性规规划划对对偶偶问问题题的的资资源源影影子子价价格格的的含含义义；各参数变化的敏感性分析；对偶单纯形法。各参数变化的敏感性分析；对偶单纯形法。n原原始始规规划划的的解解与与对对偶偶规规划划的的解解之之间间有有一一些些重重要要的的关关系系，这这些些基基本本性性质质统统称称为为对对偶偶定定理理，包包括括对对称称性性定定理理，弱弱对对偶偶定定理理，最最优优性性准准则则定定理，主对偶定理。理，主对偶定理。n对对偶偶变变量量表表示示一一个个单单位位第第i种种资资源源的的估估价价，这这种种估估价价不不是是

17、资资源源的的市市场场价价格格，而而是是根根据据资资源源在在生生产产中中作作出出的的贡贡献献而而作作的的估估价价，为为区区别别起起见见，称为影子价格（称为影子价格（Shadow price），），n线线性性规规划划的的灵灵敏敏度度分分析析就就是是研研究究参参数数变变化化时时对对最最优优解解的的影影响响。具具体体来来说说，主主要要讨讨论论下下列列两两类类问问题题：一一是是在在最最优优解解（或或最最优优基基）不不变变的的前前提提下下，确确定定参参数数的的变变化化范范围围；二二是是当当参参数数或或系系数数矩矩阵阵的的结结构构发发生生变化时，如何确定最优解的变化（即参数线性规划）。变化时，如何确定最优解的变化（即参数线性规划）。n从从理理论论解解度度，线线性性规规划划灵灵敏敏度度分分析析的的方方法法是是利利用用最最优优单单纯纯形形表表；从从应用角度，要会生成并解读计算机额灵敏度分析的输出信息。应用角度，要会生成并解读计算机额灵敏度分析的输出信息。10/27/202222