对偶线性规划.ppt

文档介绍：第二章线性规划的对偶理论及其应用
窗含西岭千秋雪,门泊东吴万里船
对偶是一种普遍现象
1
线性规划的对偶理论 线性规划原问题与对偶问题的表达形式
任何线性规划问题都有其对偶问题
对偶问题有其明显的经济含义
假设有商人要向厂方购买资源A和B,问他们谈判原料
价格的模型是怎样的?
2

设A、B资源的出售价格分别为 y1 和 y2
显然商人希望总的收购价越小越好
工厂希望出售资源后所得不应比生产产品所得少
目标函数 min g(y)=25y1+15y2
3
线性规划原问题与对偶问题的表达形式
4
线性规划原问题与对偶问题的表达形式
5
(max,)标准型的对偶变换
目标函数由 max 型变为 min 型
对应原问题每个约束行有一个对偶变量 yi,i=1,2,…,m
对偶问题约束为型,有 n 行
原问题的价值系数 C 变换为对偶问题的右端项
原问题的右端项 b 变换为对偶问题的价值系数
原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵矩阵
原问题与对偶问题互为对偶
对偶问题可能比原问题容易求解
对偶问题还有很多理论和实际应用的意义
6
非标准型的对偶变换
7
对偶变换的规则
约束条件的类型与非负条件对偶
非标准的约束条件类型对应非正常的非负条件
对偶变换是一一对应的
8
弱对偶定理推论
max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限; min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限
如果原max(min)问题为无界解,则其对偶min (max)问题无可行解
如果原max(min)问题有可行解,其对偶min (max)问题无可行解,则原问题为无界解
9
最优解判别定理
定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等,则X0, Y0分别是相应问题的最优解
证:由弱对偶定理推论1,结论是显然的。
即CX0 = Y0b  CX, Y0b = CX0  Yb 。证毕。
主对偶定理
定理如果原问题和对偶问题都有可行解,则它们都有最优解,且它们的最优解的目标函数值相等。
证:由弱对偶定理推论1可知,原问题和对偶问题的目标函数有界,故一定存在最优解。
现证明定理的后一句话。
10