2.线性规划的对偶理论(第一部分).ppt

一、对偶问题的提出一、对偶问题的提出1、对偶思想举例：某工厂拥有一定生产对偶思想举例：某工厂拥有一定生产原材料时，该工厂考虑是自己进行产品生产原材料时，该工厂考虑是自己进行产品生产所赚的利润大还是将其原材料直接出售给其所赚的利润大还是将其原材料直接出售给其它工厂时所以赚取的利润大的问题。它工厂时所以赚取的利润大的问题。第二章第二章线性规划的对偶理论线性规划的对偶理论 2、换个角度审视生产计划问题换个角度审视生产计划问题例：（第一章例例：（第一章例2）要求制定一个生产计划）要求制定一个生产计划方案，在劳动力和原材料可能供应的范围方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大内，使得产品的总利润最大。它它的的对对对对偶偶偶偶问问问问题题题题就就是是一一个个价价价价格格格格系系系系统统统统，使使在在平平衡衡了了劳劳动动力力和和原原材材料料的的直直接接成成本本后后，所所确确定定的的价价价价格格格格系系系系统统统统最具有竞争力：最具有竞争力：最具有竞争力：最具有竞争力：（用用于于生生产产第第i种种产产品品的的资资源源转转让让收收益益不不小小于于生生产产该该种种产产品品时时获得的利润）获得的利润）对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以解释为对工时及原材料的单位定价料的单位定价料的单位定价料的单位定价 ；若工厂自己不生产产品若工厂自己不生产产品A、B和和C，将现将现有的工时及原材料转而接受外来加工时，有的工时及原材料转而接受外来加工时，那么那么上述的价格系统能保证不亏本又最富上述的价格系统能保证不亏本又最富有竞争力有竞争力（包工及原材料的总价格最低）（包工及原材料的总价格最低）当原问题和对偶问题都取得最优解时，这当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：一对线性规划对应的目标函数值是相等的：Zmax=Wmin二、原问题和对偶问题的关系二、原问题和对偶问题的关系1、对称形式的对偶关系、对称形式的对偶关系（1）定义：若原问题是）定义：若原问题是 则定义其对偶问题为则定义其对偶问题为这两个式子之间的变换关系称为这两个式子之间的变换关系称为“对称形式的对偶关系对称形式的对偶关系”。原问题与对偶问题的对比：原问题与对偶问题的对比：若原问题若原问题对偶问题对偶问题（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述（D）（L）（3）怎样从原始问题写出其对偶问题？）怎样从原始问题写出其对偶问题？按照定义；按照定义；记忆法则：记忆法则：“上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小”例例 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题：2、非对称形式的对偶关系：、非对称形式的对偶关系：（1）原问题原问题对偶问题对偶问题（特特点点：对对偶偶变变量量符符号号不限，系数阵转置）不限，系数阵转置）(特点：等式约束特点：等式约束)（2）怎样写出非对称形式的对偶问题？）怎样写出非对称形式的对偶问题？把把一一个个等等式式约约束束写写成成两两个个不不等等式式约约束束，再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；按照原始按照原始-对偶表直接写出对偶表直接写出；（3）原始）原始-对偶表对偶表原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数MaxZ目标函数目标函数MinW变量数：变量数：n个个变量变量0变量变量0变量变量无约束无约束约束条件数：约束条件数：n个个约束条件约束条件约束条件约束条件约束条件约束条件=约束条件：约束条件：m个个约束条件约束条件约束条件约束条件约束条件约束条件=变量数：变量数：m个个变量变量0变量变量0无约束无约束课堂练习：写出下面线性规划的对偶规划：课堂练习：写出下面线性规划的对偶规划：下面的答案哪一个是正确的？为什么下面的答案哪一个是正确的？为什么？（原原问问题题是是极极小小化化问问题题，因因此此应应从从原原始始对对偶偶表的表的右边右边往往左边左边查！查！）三、对偶定理三、对偶定理 对偶定理是揭示对偶定理是揭示原原始始问问题题的的解解与与对对偶偶问问题题的的解解之之间间重重要关系要关系的的 一系列性质。一系列性质。对称性对称性 对偶问题的对偶是原问题对偶问题的对偶是原问题。性性质质1 弱弱对对偶偶性性如如果果 是是原原问问题题的可行解，的可行解，其对偶问题的可行解，则恒有：其对偶问题的可行解，则恒有：（L）和和 （D）均有可行解，分别为均有可行解，分别为 和和 ，则，则C b。证证明明思思路路：由（由（L）左乘左乘 ，得，得 由（由（D）右乘右乘 ，得，得 关于关于“界界”的结果；的结果；极小化问题有下界极小化问题有下界推推论论1 极极大大化化问问题题的的任任意意一一个个可可行行解解所所对对应应的的目目标标函函数数值值是是其其对对偶偶问问题题最最优优目目标标函函数数值值的的一一个下界。个下界。极大化问题有上界极大化问题有上界推论推论2 极小化问题的任意一个可行解所对极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函应的目标函数值是其对偶问题最优目标函数值的一个上界。数值的一个上界。性质性质2 最优性最优性 若若、分别为对称形式对分别为对称形式对偶线性规划的可行解，且两者目标函数的偶线性规划的可行解，且两者目标函数的相应值相等，即相应值相等，即则则 ，分别为原始问题和对偶问题的最分别为原始问题和对偶问题的最优解。优解。性质性质3 无界性无界性 如果原问题（对偶问题）如果原问题（对偶问题）具有无界解，则对偶问题（原问题）无可具有无界解，则对偶问题（原问题）无可行解。行解。v注意：这个性质逆不成立。因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。性质性质4 强对偶性强对偶性(或称对偶定理或称对偶定理)如果原问如果原问题有最优解，则其对偶问题也一定具有最优题有最优解，则其对偶问题也一定具有最优解，且有解，且有性质性质5 互补松弛性互补松弛性 在线性规划问题的最优解在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定条件取严格不等式，则其对应的对偶变量一定为零。为零。即：即：性质性质6 线性规划的原问题及其对偶问题之间线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基解变量，则在另如果在一个问题的解中是基解变量，则在另一问题的解中是非基变量；将这对互补的基一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有：解分别代入原问题和对偶问题的目标函数有：例