第四章 线性规划的对偶原理.ppt

第四章线性规划的对偶原理
线性规划的对偶性
对于线性规划的最大值问题,都相应存在着一个特
,一个问题
可以从两个不同的方面提出:一个方面是在一定的资源
条件下,如何最合理地规划使用这种资源,使得完成的
任务量最大;另一个方面是根据已确定的任务如何规划
使用资源,
作是从两个不同的角度对同一个问题所进行的分析与研
究,
之间的关系是相对的,通常称一个问题是另一个问题的
,后者就叫做对偶
,如果把后者称为原始问题,前者就叫做对
偶问题,.
本章主要内容
第一节线性规划的对偶问题
第二节对偶单纯形法
第三节对偶问题的经济意义
第四节灵敏度分析
第一节线性规划的对偶问题
对偶问题举例
对称型对偶关系的一般形式

非对称型对偶关系
一、对偶问题举例
例1 我们以第三章第一节的例1为例,已经得到了
问题的数学模型:
设计划期内甲、乙两种产品产量分别为吨、
吨,则有
现在从另一个角度讨论个问题:假设该工厂的决策
者打算不再自己生产甲、乙产品,而是将各设备的有限
台时租让给其它工厂使用,
策者就要确定租价.

的原则应该是:将生产1吨产品甲所需的各设备的台时租
。

模型为:
为什么求目标函数最小值呢?显然,如果求
最大值,,得到
的租费收入越多,但租价定得过高,就不会有人
来租,,我们所
求的是和自己生产甲、乙产品的最优情况效果相
同的租价,即满足约束的最低租价.
上述两个线性规划问题是一对对偶问题。
二、对称型对偶关系的一般形式
例1的一般形式为:

这种模型的特点是:
1、所有决策变量都是
非负的;
2、所有约束条件都是
“≤”类型;
3、目标函数是最大化
类型.
如果把它做为原始问题,根据上述原始和对偶问题
的对应关系可得出它的对偶问题为:
原始问题和对偶问题之间的对应关系
称为对称型对偶关系。