对偶理论2.ppt

运筹学Operational Research
运筹帷幄,决胜千里
史记《张良传》
1
目录
绪论
第一章线性规划问题及单纯型解法
第二章线性规划的对偶理论及其应用
第三章图与网路分析
第四章运输问题数学模型及其解法
第五章决策理论
第六章对策理论
2
3
第二章 LP 的对偶理论与灵敏度分析
第三节对偶问题的基本性质


若
是原LP的可行解。
是DLP的可行解。则
证:
4
推论:
(1)原LP任一可行解的目标函数值是DLP目标函数值的下界;
反之DLP可行解的目标函数值是LP的目标函数上界。
(2)若原LP有无界解,则其DLP无可行解;DLP有无界解,
则 LP无可行解。当对偶问题无可行解,其原问题或
具有无界解或无可行解。
5
例:已知LP问题如下,试用对偶理论证明该LP问题无最优解。
证:先分析这里LP问题无最优解是指无界解还是无可行解。
可行,只要证无界解。
6
第一个约束式与第四个约束式矛盾,DLP无可行解。
根据对偶理论推论2,LP或者可行无界解或者无可行解。
因为零解是LP的可行解,所以,LP无界解。
7

分别是LP、DLP的可行解
且
,则分别是LP、DLP的最优解。
证:设x为任一可行解,
(弱对偶性)
又
所以,
为LP最优解。
同理证
为DLP最优解。
,
8
(强对偶性)
若LP和DLP均有可行解,
则两者均有最优解,且最优解目标函数相等。
证:
为LP可行解
有下界DLP
求
原LP有界可行,一定存在最优解
最优基可行解,
设
为LP最优基可行解,
则
令
则
为DLP可行解且
由最优性,可知结论。
,
9
(松紧定理)
设
为LP、DLP的最优解,
若对应某一约束条件式的对偶变量为非零,则该约束条件
取严格等式;反之,若约束条件取严格不等式则对应的
对偶变量一定为零。
例如:若
则
若
则
,
证:用对称形式的对偶问题证明最简单。(略)
10