《Chapter线性规划的对偶理论实用.pptx》由会员分享，可在线阅读，更多相关《Chapter线性规划的对偶理论实用.pptx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12023/3/23租赁问题形成的新规划模型写出原问题和新问题的约束矩阵，右端项和目标函数系数问题：原问题的约束矩阵等和对偶问题的之间有什么关系？第1页/共9页22023/3/23原问题和对偶问题之间的关系原问题和对偶问题A,b 和 c 的对应关系：A AT,bT c,cT b;原问题是极大化问题，对偶问题是极小化问题；原问题 vs.对偶问题：约束条件个数=决策变量个数，反之依然；原问题的约束为“”号，对偶问题的约束为“”号。第2页/共9页32023/3/23对称形式的对偶规划定义2.1 原问题(LP)的对偶问题为（DP）其中 y=(y1,y2,ym)T 为对偶问题的决策变量，称(LP)为标准
2、形式原问题。注：在对偶理论中，一般不再要求x和 b 非负。例2.1 求下述问题的对偶问题。标准原问题问题：请某位同学上黑板写下对偶问题(4)？第3页/共9页42023/3/23对偶规划的对偶规划为原问题定理2.1 对偶问题(DP)的对偶问题为（LP）证明思路：将对偶问题转化为标准形式原问题，即“max+约束”形式，再用定义求解。第4页/共9页52023/3/23两个推论 非标准原问题的对偶问题难点记住：对偶问题约束的符号取决于原问题的变量符号；对偶问题的变量符号取决于原问题的约束符号。第5页/共9页62023/3/23约束为“”的原问题的对偶问题第6页/共9页72023/3/23混合形式原问题的对偶问题(书中书中P56P56例例2 2)设对偶问题的决策变量为 y=(y1,y2,y3)T，对偶问题目标函数，约束矩阵，右端项容易写出；关键是约束符号和变量符号问题。第1约束：min+x1 0,如果x10,对偶问题约束该取“”，此处相反取“”；第2约束取“=”；第3约束为 min+x3 0，约束取“”；对偶问题第1变量y1:由 min+第1约束“”决定，y1 0;变量y2:由 min+第2约束“”决定，y2 0;原问题第3个等式决定了变量y3取值无限制。第7页/共9页82023/3/23作业书P78,2.1(b)（下周三交）第8页/共9页92023/3/23感谢您的欣赏！第9页/共9页