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

《管理运筹学课件第3章 对偶规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章对偶规划教学目标与要求【教学目标】通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。【知识结构】9/18/20212管理运筹学课件本章主要内容3.1线性规划的对偶模型3.1.1对偶问题3.1.2线性规划对偶模型3.1.3对偶问题的基本性质3.2对偶单纯形法简介3.3影子价格3.4灵敏度分析3.4.1价值系数的变化分析3.4.2右端常数的变化分析3.4.3增加一个新变量的分析3.4.4增加新的约束条件的分析3.5如何看计算机求解报告本章小结9/18/20213管理运筹学课件导入案例——出租还是自己组织生产？第2

2、章导入案例中的数学模型任何一个线性规划问题都存在一个伴生的线性规划问题，我们称之为“对偶”。本章将讨论对偶问题模型的建立、影子价格及敏感性分析。现在换个角度讨论这个问题。假若由于某种原因，该企业打算放弃生产产品的项目，而将所有设备出租，收取租金。那么，在考虑到设备出租市场竞争条件下，如何确定三种设备单位台时的租金，才能使企业不至于蚀本。问题：1.如何建立该问题的数学模型？3.用什么方法对该问题模型求解？9/18/20214管理运筹学课件3.1.1对偶问题原始规划设：两种设备单位台时租金分别为y1,y2由于承租方是理智的，会把租金压至最低。故出租方在满足上述二约束情况下，至少出租总收入（目标函数

3、）为约束一：生产甲产品的利润不大于放弃生产而出租的租金收入约束二：生产乙产品的利润不大于放弃生产而出租的租金收入对偶规划称（2）为（1）的对偶，也称（1）为（2）的对偶。9/18/20215管理运筹学课件3.1.2对偶问题的数学模型（1）对称形式对偶问题原问题对偶问题9/18/20216管理运筹学课件3.1.2对偶问题的数学模型（2）非对称形式对偶问题【例3.1】写出下列线性规划的对偶规划。对偶模型：9/18/20217管理运筹学课件3.1.3对偶问题的基本性质9/18/20218管理运筹学课件3.2对偶单纯形法简介9/18/20219管理运筹学课件3.2对偶单纯形法简介标准化（若≥乘-1）计

4、算检验数所有σ≤0?Yes所有b≥0?不符合对偶单纯形法条件，改用大M法No结束Yes找到最优解No找出最小bkxk为离去变量所有akj≥0?θs=min{akj/σj

5、σj<0}，xs入基，迭代得新单纯形表No无可行解Yes9/18/202110管理运筹学课件3.2对偶单纯形法简介【例3.2】用对偶单纯形法解解标准化初始单纯形表第1次迭代第2次迭代最优解最优值209/18/202111管理运筹学课件3.2对偶单纯形法简介【例3.3】用对偶单纯形法解B2<0A2j≥0无可行解9/18/202112管理运筹学课件3.3影子价格导入案例原问题的解如图.对偶问题的解9/18/202113管理运筹学

6、课件3.3影子价格原问题bi代表第i种资源拥有量yi代表第i种资源的估价，该估价并非市价格，而是在生产中的单位贡献所做的估价,称为影子价格。其含义：（1）资源的市场价格由供求关系决定，而它的影子价格则有赖于资源的利用情况。（2）影子价格是一种边际价格。（3）资源的影子价格实际上又是一种机会成本。（4）当影子价格为0时，表明该种资源未得到充分利用；当影子价格不为0时，表明该种资源已耗费完毕。（5）在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。对偶问题9/18/202114管理运筹学课件3.4灵敏度分析线性规划的各个参数A，C，b往往是

7、根据统计数据测算的，不可能完全准确，而且随着实际情况变化。灵敏度分析是指各参数变化对最优解的影响。9/18/202115管理运筹学课件3.4.1价值系数cj的变化分析由式3-7可知，cj变化仅影响检验数。敏感性分析是求检验数符号不变（最优基不变）时cj的允许变化范围。【例3.4】由下述模型的最终单纯形表求最优基不变的c2允许变化范围。令c2=4+Δc，有：若保持检验数非正，要求：即c2的允许变化范围：[2.5,5]9/18/202116管理运筹学课件3.4.2右端项bi的变化分析设由式3-8，若则最优基保持不变.【例3.5】由[例3.4]最终单纯形表求最优基不变的b3允许变化范围。初始基最优基

8、即b3的允许变化范围：[40,50]9/18/202117管理运筹学课件3.4.3增加一个新变量的分析9/18/202118管理运筹学课件3.4.3增加一个新变量的分析在操作上：由若大于0应安排生产。【例3.6】在例3.4中增加一个新产品是否可行。其消耗系数列向量p6=（3/2，1，1/2）及价值系数c6=3.9/18/202119管理运筹学课件3.4.4增加一个新的约束分析增加一个新的约束后，线