对偶理论第一讲线性规划的对偶模型,对偶性质.ppt
《对偶理论第一讲线性规划的对偶模型,对偶性质.ppt》由会员分享,可在线阅读,更多相关《对偶理论第一讲线性规划的对偶模型,对偶性质.ppt(25页珍藏版)》请在三一办公上搜索。
1、3.1 对偶线性规划问题,对偶问题的提出,原问题,对偶问题,原问题,对偶问题,原问题与对偶问题关系,(1)原问题的约束个数(不含非负约束)等于对偶变量的个数,(2)原问题的目标函数系数对应于对偶问题的右端项,(3)原问题的右端项对应于对偶问题的目标函数系数,(4)原问题的约束矩阵转置就是对偶问题系数矩阵,(5)原问题求最小(最大),对偶问题是求最大(最小),(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”),原问题,对偶问题,原问题与对偶问题关系,(1)原问题的约束个数(不含非负约束)等于对偶变量的个数,(2)原问题的目标函数系数对应于对偶问题的右端项,(3)原问
2、题的右端项对应于对偶问题的目标函数系数,(4)原问题的约束矩阵转置就是对偶问题系数矩阵,【例】写出下列线性规划的对偶问题,【解】设Y=(y1,y2),(5)原问题求最小(最大),对偶问题是求最大(最小),(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”),【例3.3】写出下列线性规划的对偶问题,线性规划问题的规范形式(Canonical Form 或叫对称形式):,定义:目标函数求极大值时,所有约束条件为号,变量非负;目标函数求极小值时,所有约束条件为号,变量非负。,注:(1)线性规划规范形式与标准型是两种不同形式,但可以相互转换。,(2)规范形式的线性规划问题的
3、对偶仍然是规范形式,问题:讨论一般形式的线性规划问题的对偶问题?,方法:先将其转化为规范形式的线性规划问题,然后写出其对偶问题,适当将其进行化简。,3.2 对偶性质Dual property,对偶问题是(记为DP):,这里A是mn矩阵,X是n1列向量,Y是1m行向量。,【性质1】对称性:对偶问题的对偶是原问题。,设原问题是(记为LP):,3.2.1 对偶性质,【性质2】弱对偶性:设X*、Y*分别为LP(min)与 DP(max)的可行解,则,【性质2】弱对偶性:设X*、Y*分别为LP(mix)与 DP(max)的可行解,则,由这个性质可得到下面几个结论:,1)(DP)的任一可行解的目标值是(L
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 理论 第一 线性规划 模型 性质
链接地址:https://www.31ppt.com/p-6274231.html