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

第3章对偶规划
8/15/2018
1
课件
教学目标与要求
【教学目标】
通过对本章的学****理解对偶定义和性质及影子价格的含义;了解对偶单纯形法;会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。
【知识结构】
8/15/2018
2
课件
本章主要内容
线性规划的对偶模型
对偶问题
线性规划对偶模型
对偶问题的基本性质
对偶单纯形法简介
影子价格
灵敏度分析
价值系数的变化分析
右端常数的变化分析
增加一个新变量的分析
增加新的约束条件的分析
如何看计算机求解报告
本章小结
8/15/2018
3
课件
导入案例——出租还是自己组织生产?
第2章导入案例中的数学模型
任何一个线性规划问题都存在一个伴生的线性规划问题,我们称之为“对偶”。本章将讨论对偶问题模型的建立、影子价格及敏感性分析。
现在换个角度讨论这个问题。
假若由于某种原因,该企业打算放弃生产产品的项目,而将所有设备出租,收取租金。那么,在考虑到设备出租市场竞争条件下,如何确定三种设备单位台时的租金,才能使企业不至于蚀本。
问题:
1. 如何建立该问题的数学模型?
3. 用什么方法对该问题模型求解?
8/15/2018
4
课件
对偶问题
原始规划
设:两种设备单位台时租金分别为 y1,y2
由于承租方是理智的,会把租金压至最低。故出租方在满足上述二约束情况下,至少出租总收入(目标函数)为
约束一:生产甲产品的利润不大于放弃生产而出租的租金收入
约束二:生产乙产品的利润不大于放弃生产而出租的租金收入
对偶规划
称(2)为(1)的对偶,也称(1)为(2)的对偶。
8/15/2018
5
课件
对偶问题的数学模型
(1)对称形式对偶问题
原问题对偶问题
8/15/2018
6
课件
对偶问题的数学模型
(2)非对称形式对偶问题
【】写出下列线性规划的对偶规划。
对偶模型:
8/15/2018
7
课件
对偶问题的基本性质
8/15/2018
8
课件
对偶单纯形法简介
8/15/2018
9
课件
对偶单纯形法简介
标准化
(若≥乘-1)
计算检验数
所有σ≤0?
Yes
所有b≥0?
不符合对偶单纯形法条件,改用大M法
No
结束
Yes
找到最优解
No
找出最小bkxk为离去变量
所有akj≥0?
θs=min{akj/σj|σj<0},xs入基,迭代得新单纯形表
No
无可行解
Yes
8/15/2018
10
课件