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

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

1、第3章对偶规划管理运筹学课件22021/7/18教学目标与要求【教学目标】通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。【知识结构】管理运筹学课件32021/7/18本章主要内容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如何看计算机求解报告本章小结管理运筹学

2、课件42021/7/18导入案例——出租还是自己组织生产？第2章导入案例中的数学模型任何一个线性规划问题都存在一个伴生的线性规划问题，我们称之为“对偶”。本章将讨论对偶问题模型的建立、影子价格及敏感性分析。现在换个角度讨论这个问题。假若由于某种原因，该企业打算放弃生产产品的项目，而将所有设备出租，收取租金。那么，在考虑到设备出租市场竞争条件下，如何确定三种设备单位台时的租金，才能使企业不至于蚀本。问题：1.如何建立该问题的数学模型？3.用什么方法对该问题模型求解？管理运筹学课件52021/7/183.1.1对偶问题原始规划设：两种设备单位台时租金分别为y1,y2由于

3、承租方是理智的，会把租金压至最低。故出租方在满足上述二约束情况下，至少出租总收入（目标函数）为约束一：生产甲产品的利润不大于放弃生产而出租的租金收入约束二：生产乙产品的利润不大于放弃生产而出租的租金收入对偶规划称（2）为（1）的对偶，也称（1）为（2）的对偶。管理运筹学课件62021/7/183.1.2对偶问题的数学模型（1）对称形式对偶问题原问题对偶问题管理运筹学课件72021/7/183.1.2对偶问题的数学模型（2）非对称形式对偶问题【例3.1】写出下列线性规划的对偶规划。对偶模型：管理运筹学课件82021/7/183.1.3对偶问题的基本性质管理运筹学课件9

4、2021/7/183.2对偶单纯形法简介管理运筹学课件102021/7/183.2对偶单纯形法简介标准化（若≥乘-1）计算检验数所有σ≤0?Yes所有b≥0?不符合对偶单纯形法条件，改用大M法No结束Yes找到最优解No找出最小bkxk为离去变量所有akj≥0?θs=min{akj/σj

5、σj<0}，xs入基，迭代得新单纯形表No无可行解Yes管理运筹学课件112021/7/183.2对偶单纯形法简介【例3.2】用对偶单纯形法解解标准化初始单纯形表第1次迭代第2次迭代最优解最优值20管理运筹学课件122021/7/183.2对偶单纯形法简介【例3.3】用对偶单纯形

6、法解B2<0A2j≥0无可行解管理运筹学课件132021/7/183.3影子价格导入案例原问题的解如图.对偶问题的解管理运筹学课件142021/7/183.3影子价格原问题bi代表第i种资源拥有量yi代表第i种资源的估价，该估价并非市价格，而是在生产中的单位贡献所做的估价,称为影子价格。其含义：（1）资源的市场价格由供求关系决定，而它的影子价格则有赖于资源的利用情况。（2）影子价格是一种边际价格。（3）资源的影子价格实际上又是一种机会成本。（4）当影子价格为0时，表明该种资源未得到充分利用；当影子价格不为0时，表明该种资源已耗费完毕。（5）在一个大公司内部，可借助资

7、源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。对偶问题管理运筹学课件152021/7/183.4灵敏度分析线性规划的各个参数A，C，b往往是根据统计数据测算的，不可能完全准确，而且随着实际情况变化。灵敏度分析是指各参数变化对最优解的影响。管理运筹学课件162021/7/183.4.1价值系数cj的变化分析由式3-7可知，cj变化仅影响检验数。敏感性分析是求检验数符号不变（最优基不变）时cj的允许变化范围。【例3.4】由下述模型的最终单纯形表求最优基不变的c2允许变化范围。令c2=4+Δc，有：若保持检验数非正，要求：即c2的允许变

8、化范围：[2.5,5]管理运筹学课件172021/7/183.4.2右端项bi的变化分析设由式3-8，若则最优基保持不变.【例3.5】由[例3.4]最终单纯形表求最优基不变的b3允许变化范围。初始基最优基即b3的允许变化范围：[40,50]管理运筹学课件182021/7/183.4.3增加一个新变量的分析管理运筹学课件192021/7/183.4.3增加一个新变量的分析在操作上：由若大于0应安排生产。【例3.6】在例3.4中增加一个新产品是否可行。其消耗系数列向量p6=（3/2，1，1/2）及价值系数c6=3.管理运筹学课件202021/7/183.5如何看计算