文档介绍：第二章线性规划的对偶理论及其应用
窗含西岭千秋雪,门泊东吴万里船
对偶是一种普遍现象
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
线性规划的对偶定理
弱对偶定理
定理对偶问题(min)的任何可行解Y0,其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值
为了便于讨论,下面不妨总是假设
9
弱对偶定理推论
max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限; min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限
如果原max(min)问题为无界解,则其对偶 min (max)问题无可行解
如果原max(min)问题有可行解,其对偶 min (max)问题无可行解,则原问题为无界解
注:有可能存在原问题和对偶问题同时无可行解的情况
10