线性规划的对偶理论

#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/2/2,1,2024/11/16,1,对偶问题的提出,设备租赁问题,假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备，,常山方面应如何决定出租价格呢,？,设常山机器厂对三种设备的出租定价分别为,y,1,y,2,y,3,元,/,小时。,常山机器厂的考虑：,不能比自己组织生产获利少,(,约束条件,),；,四海机器厂的考虑：,租金尽可能少,(,目标函数,),加工设备,A,B,C,单件利润,产品,I,2,4,0,2,元,产品,II,2,0,5,3,元,设备时限,12,h,16,h,15,h,2,2024/11/16,租赁问题形成的新规划模型,写出,原问题,和,新问题,的约束矩阵，右端项和目标函数系数,问题,：原问题的约束矩阵等和对偶问题的之间有什么关系？,3,2024/11/16,原问题和对偶问题之间的关系,原问题和对偶问题,A,b,和,c,的对应关系：,A,A,T,b,T,c,c,T,b,;,原问题是极大化问题，对偶问题是极小化问题；,原问题,vs.,对偶问题：约束条件个数,=,决策变量个数，反之依然；,原问题的约束为,“,”,号，对偶问题的约束为,“,”,号。,4,2024/11/16,对称形式的对偶规划,定义,2.1,原问题,(LP),的,对偶问题,为（,DP,）其中,y,=(,y,1,y,2,y,m,),T,为对偶问题的决策变量，称,(LP),为,标准形式,原问题。,注,：在对偶理论中，一般不再要求,x,和,b,非负。,例,2.1,求下述问题的对偶问题,。,标准原问题,问题,：请某位同学上黑板写下对偶问题,(4,),？,5,2024/11/16,对偶规划的对偶规划为原问题,定理,2.1,对偶问题,(DP),的对偶问题为（,LP,）,证明思路,：,将对偶问题转化为标准形式原问题，即,“,max+,约束,”形式，再用定义求解。,6,2024/11/16,两个推论,非标准原问题的对偶问题,难点记住,：对偶问题约束的符号取决于原问题的变量符号；,对偶问题的变量符号取决于原问题的约束符号。,7,2024/11/16,约束为“,”的原问题的对偶问题,8,2024/11/16,混合形式原问题的对偶问题,(,书中,P56,例,2,),设对偶问题的决策变量为,y,=(,y,1,y,2,y,3,),T,，,对偶问题目标函数，约束矩阵，右端项容易写出；,关键是约束符号和变量符号问题,。,第,1,约束：,min+,x,1,0,如果,x,1,0,对偶问题约束该取“”，此处相反取“”；,第,2,约束取“,=”,；第,3,约束为,min+,x,3,0,，约束取“”；,对偶问题第,1,变量,y,1,:,由,min+,第,1,约束“”决定，,y,1,0;,变量,y,2,:,由,min+,第,2,约束“”决定，,y,2,0;,原问题第,3,个等式决定了变量,y,3,取值无限制。,9,2024/11/16,作业,书,P78,2.1(b),（下周三交）,