- 1、本文档共30页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
1
第三章 线性规划的对偶问题
对偶线性规划
对偶定理
对偶单纯形法
第一节 对偶问题
对偶问题概念:
任何一个线性规划问题都有一个与之相对应
的线性规划问题,如果前者称为原始问题,后者
就称为“对偶”问题。
对偶问题是对原问题从另一角度进行的描述
其最优解与原问题的最优解有着密切的联系,在
求得一个线性规划最优解的同时也就得到对偶线
性规划的最优解,反之亦然。
对偶理论就是研究线性规划及其对偶问题的
理论,是线性规划理论的重要内容之一。
3
对偶问题的提出
例1、某工厂生产甲,乙两种产品,这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时,它们销售后所能获得的利润,以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划,即甲,乙两种产品各生产多少吨,可使该厂所获得利润达到最大。
对偶线性规划
设备
每吨产品的加工台时
可供台时数
甲
乙
A
B
C
3
5
9
4
4
8
36
40
76
利润(元/吨)
32
30
4
设备
每吨产品的加工台时
可供台时数
甲
乙
A
B
C
3
5
9
4
4
8
36
40
76
利润(元/吨)
32
30
5
现在从另一个角度来考虑该工厂的生产问题:
假设该厂的决策者打算不再自己生产甲,乙产品,而是把各种设备的有限台时数租让给其他工厂使用,这时工厂的决策者应该如何确定各种设备的租价。
6
设备
每吨产品的加工台时
可供台时数
甲
乙
A
B
C
3
5
9
4
4
8
36
40
76
利润(元/吨)
32
30
7
8
可以得到另一个线性规划:
称之为原线性规划问题的对偶问题,
对偶线性规划
考虑如下具有不等式约束的线性规划问题
9
10
11
12
若令 线性规划标准型
的对偶规划为:
线性规划问题标准型的对偶问题
考虑一个标准形式的线性规划问题
由于任何一个等式约束都可以用两个不等式约束等价地表示,所以标准形线性规划问题可等价表示为:
它的对偶规划为:
对偶问题的特点
(1)目标函数在一个问题中是求最大值在另一问题中则为求最小值
(2)一个问题中目标函数的系数是另一个问题中约束条件的右端项
(3)一个问题中的约束条件个数等于另一个问题中的变量数
(4)原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵
其他形式问题的对偶
15
对偶线性规划的求法
从任何一个线性规划出发,都可以求出相应的对偶规划,在实际求解过程中,通常不通过求标准型,而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表:
目标函数变量系数
约束条件右端项
约束条件右端项
目标函数变量系数
约束条件个数:n个
变量个数:n个
变量个数:m个
约束条件个数:m个
目标函数minW
目标函数maxZ
对偶问题(或原问题)
原问题(或对偶问题)
16
解:对偶规划:
例2 写出下列线性规划的对偶问题
17
例3 写出下列线性规划的对偶问题
解:上述问题的对偶规划:
18
本节讨论几条重要的对偶定理,这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。
定理1:(对称性)对偶问题的对偶是原问题。
证明:设原问题为 对偶问题为
改写对偶问题为 对偶问题的对偶为
第二节 对偶定理
19
定理2:弱对偶定理
若 是原(极小化)问题的可行解, 是对偶(极大化)问题的可行解,那么
注:原(极小化)问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。
对偶(极大化)问题的最优目标函数值以原问题任一可行解的目标函数值为上界。
推论1:如果原问题没有下界(即minZ→-∞),则对偶问题不可行。
如果对偶问题没有上界(即maxW→+∞),则原问题不可行。
若原问题与对偶问题之一无界,则另一个无可行解。
20
证明:由弱对偶定理,对于原始问题的所有可行解 ,都有 因此 是原问题的最优解。
同理,对于对偶问题的所有可行解 ,都有
所以 是对偶问题的最优解。
21
证明:设 是原问题(min)的最优解,则对应的基B必有
。
文档评论(0)