线性规划的对偶理论

《线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性规划的对偶理论2011年3月黑龙江大学数学科学学院信息与计算数学系Allrightsreserved§1对偶问题的提出设备租赁问题假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备，常山方面应如何决定出租价格呢？设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。常山机器厂的考虑：不能比自己组织生产获利少(约束条件)；四海机器厂的考虑：租金尽可能少(目标函数)加工设备ABC单件利润产品I2402元产品II2053元设备时限12h16h15h——10/6/20212租赁问题形成的新规划模型写出原问题和新问题的约束矩阵，右端项和目标函

2、数系数问题：原问题的约束矩阵等和对偶问题的之间有什么关系？10/6/20213原问题和对偶问题之间的关系原问题和对偶问题A,b和c的对应关系：A~AT,bT~c,cT~b;原问题是极大化问题，对偶问题是极小化问题；原问题vs.对偶问题：约束条件个数=决策变量个数，反之依然；原问题的约束为“”号，对偶问题的约束为“”号。10/6/20214对称形式的对偶规划定义2.1原问题(LP)的对偶问题为（DP）其中y=(y1,y2,…,ym)T为对偶问题的决策变量，称(LP)为标准形式原问题。注：在对偶理论中，一般不再要求x和b非负。例2.1求下述问题的对偶问

3、题。标准原问题问题：请某位同学上黑板写下对偶问题(4')？10/6/20215对偶规划的对偶规划为原问题定理2.1对偶问题(DP)的对偶问题为（LP）证明思路：将对偶问题转化为标准形式原问题，即“max+约束”形式，再用定义求解。10/6/20216两个推论–非标准原问题的对偶问题难点记住：对偶问题约束的符号取决于原问题的变量符号；对偶问题的变量符号取决于原问题的约束符号。10/6/20217约束为“”的原问题的对偶问题10/6/20218混合形式原问题的对偶问题(书中P56例2)设对偶问题的决策变量为y=(y1,y2,y3)T，对偶问题目标函数，约束矩

4、阵，右端项容易写出；关键是约束符号和变量符号问题。第1约束：min+x10,如果x10,对偶问题约束该取“”，此处相反取“”；第2约束取“=”；第3约束为min+x30，约束取“”；对偶问题第1变量y1:由min+第1约束“”决定，y10;变量y2:由min+第2约束“”决定，y20;原问题第3个等式决定了变量y3取值无限制。10/6/20219作业书P78,2.1(b)（下周三交）10/6/202110