《最优化LP对偶原理.ppt》由会员分享，可在线阅读，更多相关《最优化LP对偶原理.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、对偶问题的提出一、对偶问题的提出1、对偶思想举例对偶思想举例周周长长一一定定的的矩矩形形中中，以以正正方方形形面面积积最最大大；面面积积一一定定的的矩矩形形中中，以以正正方方形形周长最小；周长最小；Chapter 3 LP的的对偶问题对偶问题 2、换个角度审视生产计划问题换个角度审视生产计划问题例例2-12-1要求制定一个生产计划方案，在劳动力和原要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大材料可能供应的范围内，使得产品的总利润最大 。资源资源产品产品人力人力原材料原材料单位利润单位利润甲甲112乙乙143丙丙173现有资源现有资源39若工厂自己不生产产
2、品若工厂自己不生产产品甲甲、乙乙和和丙丙，将将现有的工时及原材料转而接受外来加工时，现有的工时及原材料转而接受外来加工时，工厂要求包工及原材料的总价格最低。工厂要求包工及原材料的总价格最低。对偶变量的经济意义可以解释为对偶变量的经济意义可以解释为对偶变量的经济意义可以解释为对偶变量的经济意义可以解释为对工时及原材料的单位定价对工时及原材料的单位定价对工时及原材料的单位定价对工时及原材料的单位定价 ；（用用于于生生产产第第i种种产产品品的的资资源源转转让让收收益益不不小小于于生生产产该该种产品时获得的利润）种产品时获得的利润）当原问题和对偶问题都取得最优解当原问题和对偶问题都取得最优解时，这一对
3、线性规划对应的目标函时，这一对线性规划对应的目标函数值是相等的：数值是相等的：ZmaxZmax=WminWmin=8=8 考察原问题和对偶问题的解，给作决考察原问题和对偶问题的解，给作决策的管理者另一个自由度；策的管理者另一个自由度；怎样通过增加更多的资源来增加利润？怎样通过增加更多的资源来增加利润？怎样使用不同类型的资源来增加利润？怎样使用不同类型的资源来增加利润？价格价格VaVbVc甲甲0.810000.617.5乙乙0.515000.277.5丙丙0.917500.680丁丁1.532500.330例例2-2 采购甲、乙、丙、丁采购甲、乙、丙、丁4种食品量分别为种食品量分别为x1，x2，
4、x3，x4，在保证人体所需维生素在保证人体所需维生素A(4000)、B(1)、C(30)前提下，使总的花前提下，使总的花费最小。费最小。3、饮食与营养问题、饮食与营养问题换一个角度，生产营养药丸的制药公司力图换一个角度，生产营养药丸的制药公司力图使营养师相信，各种营养药丸勿须通过多种食使营养师相信，各种营养药丸勿须通过多种食品的转换就能供营养师调剂。品的转换就能供营养师调剂。制药公司面对的问题是制药公司面对的问题是为营养药丸确定为营养药丸确定单价单价，以，以获得最大的收益获得最大的收益，同时，同时与真正与真正的食品竞争的食品竞争。于是，营养药丸的单位成本于是，营养药丸的单位成本不能超过不能超过
5、相相应食品的市价。应食品的市价。1.对称形式的对偶关系的矩阵描述对称形式的对偶关系的矩阵描述（D）（L）怎样从原始问题写出其对偶问题？怎样从原始问题写出其对偶问题？按照定义；按照定义；记忆法则：记忆法则：“上、下上、下”交换，矩阵转置，交换，矩阵转置，不等式变号，不等式变号，“极小极小”变变“极大极大”二、对偶问题的一般形式二、对偶问题的一般形式例例2-3 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题：2、非对称形式的对偶关系：、非对称形式的对偶关系：（1）原问题原问题对偶问题对偶问题（特特点点：对对偶偶变变量量符符号号不不限限，系系数数阵阵转置）转置）(特点：等式约束特点：等式约束
6、)（2）怎怎样样写写出出非非对对称称形形式式的的对对偶偶问问题题？把把一一个个等等式式约约束束写写成成两两个个不不等等式式约约束束，再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；按照原始按照原始-对偶表直接写出对偶表直接写出；（3）原始）原始-对偶表对偶表 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数Min 目标函数目标函数Max约束条件数：约束条件数：m个个对偶变量数：对偶变量数：m个个决策变量数：决策变量数：n个个约束条件数：约束条件数：n个个课堂练习：写出下面线性规划的对偶规划：课堂练习：写出下面线性规划的对偶规划
7、：三、对偶定理三、对偶定理 对偶定理是揭示对偶定理是揭示原原始始问问题题的的解解与与对对偶偶问问题题的的解解之之间间重重要关系要关系的的 一系列定理。一系列定理。定理定理3-1 对称性定理对称性定理 对偶问题的对偶是原问题对偶问题的对偶是原问题。定定理理3-2 弱弱对对偶偶定定理理若若一一对对对对称称形形式的对偶线性规划式的对偶线性规划（L）和和 （D）均有可行解，分别为均有可行解，分别为 和和 ，则，则该结论对非对称形式的对偶问题同样成立该结论对非对称形式的对偶问题同样成立。定理定理3-3 最优性准则定理最优性准则定理 若若、分分别为一对对偶线性规划的可行解，且别为一对对偶线性规划的可行解，
8、且两者目标函数的相应值相等，即两者目标函数的相应值相等，即 ，则则 ，分别为原始问题分别为原始问题和对偶问题的最优解。和对偶问题的最优解。定理定理3-4 强对偶定理强对偶定理 若原始问题和对若原始问题和对偶问题两者均可行，则两者均有最优偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。解，且此时目标函数值相同。原始问题原始问题对偶问题对偶问题有最优解有最优解有最优解有最优解无界无界不可行不可行不可行不可行无界无界不可行不可行不可行不可行LPLP原始问题与对偶问题的关系：原始问题与对偶问题的关系：（P）和和 （D）定理定理3-5 3-5 设设分别是原问题（分别是原问题（P P）和对偶问题（和对偶问题（D D）的可行解，则）的可行解，则为（为（P P）和（）和（D D）最优解的充要条件是）最优解的充要条件是