线性规划的对偶理论第一部分.pptx

《线性规划的对偶理论第一部分.pptx》由会员分享，可在线阅读，更多相关《线性规划的对偶理论第一部分.pptx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划的对偶理论第一部分线性规划的对偶理论第一部分 它它的的对对对对偶偶偶偶问问问问题题题题就就是是一一个个价价价价格格格格系系系系统统统统，使使在在平平衡衡了了劳劳动动力力和和原原材材料料的的直直接接成成本本后后，所所确确定定的的价价价价格格格格系系系系统统统统最具有竞争力：最具有竞争力：最具有竞争力：最具有竞争力：（用用于于生生产产第第i种种产产品品的的资资源源转转让让收收益益不不小小于于生生产产该该种种产产品时获得的利润）品时获得的利润）对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以解释为对工时及原材对偶变量的经济意义可以

2、解释为对工时及原材料的单位定价料的单位定价料的单位定价料的单位定价 ；第1页/共22页 若工厂自己不生产产品若工厂自己不生产产品A、B和和C，将现将现有的工时及原材料转而接受外来加工时，有的工时及原材料转而接受外来加工时，那么那么上述的价格系统能保证不亏本又最富上述的价格系统能保证不亏本又最富上述的价格系统能保证不亏本又最富上述的价格系统能保证不亏本又最富有竞争力有竞争力有竞争力有竞争力（包工及原材料的总价格最低）（包工及原材料的总价格最低）当原问题和对偶问题都取得最优解时，这当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：一对线性规划对应的目标函数值是相等的：Zma

3、x=Wmin第2页/共22页二、原问题和对偶问题的关系二、原问题和对偶问题的关系二、原问题和对偶问题的关系二、原问题和对偶问题的关系1 1、对称形式的对偶关系、对称形式的对偶关系、对称形式的对偶关系、对称形式的对偶关系（1）定义：若原问题是）定义：若原问题是 第3页/共22页则定义其对偶问题为则定义其对偶问题为则定义其对偶问题为则定义其对偶问题为 这两个式子之间的变换关系称为这两个式子之间的变换关系称为“对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系”。第4页/共22页原问题与对偶问题的对比：原问题与对偶问题的对比：若原问题若原问题对偶问题对偶问题对偶问题对偶问题第5

4、页/共22页（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述（D）（L）（3）怎样从原始问题写出其对偶问题？）怎样从原始问题写出其对偶问题？按照定义；按照定义；记忆法则：记忆法则：“上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小”第6页/共22页例例 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题：2 2、非对称形式的对偶关系：、非对称形式的对偶关系：、非对称形式的对偶关系：、非对称形式的对偶关系：第7页/共22页（1 1）原问题原问题原问题原问题 对偶问题对偶问题对偶问题对偶问题（特特点点：对对偶偶变变量量符符

5、号号 不限，系数阵转置）不限，系数阵转置）(特点：等式约束特点：等式约束)第8页/共22页（2）怎样写出非对称形式的对偶问题？）怎样写出非对称形式的对偶问题？把把把把一一一一个个个个等等等等式式式式约约约约束束束束写写写写成成成成两两两两个个个个不不不不等等等等式式式式约约约约束束束束，再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；按照原始按照原始按照原始按照原始-对偶表直接写出对偶表直接写出对偶表直接写出对偶表直接写出 ；（3）原始）原始-对偶表对偶表第9页/共22页 原问题（或对偶问题）原问题（或对偶

6、问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 MaxZ目标函数目标函数 MinW 变量数：变量数：n个个 变量变量 0 变量变量 0 变量变量 无约束无约束 约束条件数：约束条件数：n个个 约束条件约束条件 约束条件约束条件 约束条件约束条件 =约束条件：约束条件：m个个 约束条件约束条件 约束条件约束条件 约束条件约束条件 =变量数：变量数：m个个变量变量 0变量变量 0无约束无约束 第10页/共22页课堂练习：写出下面线性规划的对偶规划：课堂练习：写出下面线性规划的对偶规划：第11页/共22页下面的答案哪一个是正确的？为什么下面的答案哪一个是正确的？为什么下面的答案哪一个

7、是正确的？为什么下面的答案哪一个是正确的？为什么？（原原问问题题是是极极小小化化问问题题，因因此此应应从从原原始始对对偶偶表的表的右边右边往往左边左边查！查！）第12页/共22页三、对偶定理三、对偶定理三、对偶定理三、对偶定理 对偶定理是揭示对偶定理是揭示对偶定理是揭示对偶定理是揭示原原原原始始始始问问问问题题题题的的的的解解解解与与与与对对对对偶偶偶偶问问问问题题题题的的的的解解解解之之之之间间间间重重重重要关系要关系要关系要关系的的的的 一系列性质。一系列性质。一系列性质。一系列性质。对称性对称性对称性对称性 对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶

8、是原问题。第13页/共22页性性性性质质质质1 1 弱弱弱弱对对对对偶偶偶偶性性性性如如如如果果果果 是是是是原原原原问问问问题题题题的可行解，的可行解，的可行解，的可行解，其对偶问题的可行解，则恒有：其对偶问题的可行解，则恒有：其对偶问题的可行解，则恒有：其对偶问题的可行解，则恒有：（L）和和 （D）均有可行解，分别为均有可行解，分别为 和和 ，则，则C b。证证明明思思路路：由由（L）左乘左乘 ，得，得 由（由（D）右乘右乘 ，得得 第14页/共22页 关于关于关于关于“界界界界”的结果；的结果；的结果；的结果；极小化问题有下界极小化问题有下界推推推推论论论论1 1 极极极极大大大大化化化

9、化问问问问题题题题的的的的任任任任意意意意一一一一个个个个可可可可行行行行解解解解所所所所对对对对应应应应的的的的目目目目标标标标函函函函数数数数值值值值是是是是其其其其对对对对偶偶偶偶问问问问题题题题最最最最优优优优目目目目标标标标函函函函数数数数值值值值的的的的一一一一个下界。个下界。个下界。个下界。极大化问题有上界极大化问题有上界推论推论推论推论2 2 极小化问题的任意一个可行解所对极小化问题的任意一个可行解所对极小化问题的任意一个可行解所对极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函应的目标函数值是其对偶问题最优目标函应的目标函数值是其对偶问题最优目标函应的目标函

10、数值是其对偶问题最优目标函数值的一个上界。数值的一个上界。数值的一个上界。数值的一个上界。第15页/共22页性质性质性质性质2 2 最优性最优性最优性最优性 若若若若 、分别为对称形式对分别为对称形式对分别为对称形式对分别为对称形式对偶线性规划的可行解，且两者目标函数的偶线性规划的可行解，且两者目标函数的偶线性规划的可行解，且两者目标函数的偶线性规划的可行解，且两者目标函数的相应值相等，即相应值相等，即相应值相等，即相应值相等，即则则则则 ，分别为原始问题和对偶问题的最分别为原始问题和对偶问题的最分别为原始问题和对偶问题的最分别为原始问题和对偶问题的最优解。优解。优解。优解。第16页/共22页

11、性质性质性质性质3 3 无界性无界性无界性无界性 如果原问题（对偶问题）如果原问题（对偶问题）如果原问题（对偶问题）如果原问题（对偶问题）具有无界解，则对偶问题（原问题）无可具有无界解，则对偶问题（原问题）无可具有无界解，则对偶问题（原问题）无可具有无界解，则对偶问题（原问题）无可行解。行解。行解。行解。v注意：这个性质逆不成立。因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。第17页/共22页性质性质性质性质4 4 强对偶性强对偶性强对偶性强对偶性(或称对偶定理或称对偶定理或称对偶定理或称对偶定理)如果原问如果原问如果原问如果原问题有最优解，则其对偶问题也一定

12、具有最优题有最优解，则其对偶问题也一定具有最优题有最优解，则其对偶问题也一定具有最优题有最优解，则其对偶问题也一定具有最优解，且有解，且有解，且有解，且有第18页/共22页性质性质性质性质5 5 互补松弛性互补松弛性互补松弛性互补松弛性 在线性规划问题的最优在线性规划问题的最优在线性规划问题的最优在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为解中，如果对应某一约束条件的对偶变量值为解中，如果对应某一约束条件的对偶变量值为解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约非零，则该约束条件取严格等式；反之如果约非零，则该约束条件取严格等式；反之如果约非

13、零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一束条件取严格不等式，则其对应的对偶变量一束条件取严格不等式，则其对应的对偶变量一束条件取严格不等式，则其对应的对偶变量一定为零。定为零。定为零。定为零。即：即：即：即：第19页/共22页性质性质性质性质6 6 线性规划的原问题及其对偶问题之间线性规划的原问题及其对偶问题之间线性规划的原问题及其对偶问题之间线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变存在一对互补的基解，其中原问题的松驰变存在一对互补的基解，其中原问题的松驰变存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的

14、剩余变量对应对偶问题的变量，对偶问题的剩余变量对应对偶问题的变量，对偶问题的剩余变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量量对应原问题的变量；这些互相对应的变量量对应原问题的变量；这些互相对应的变量量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基解变量，则在另如果在一个问题的解中是基解变量，则在另如果在一个问题的解中是基解变量，则在另如果在一个问题的解中是基解变量，则在另一问题的解中是非基变量；将这对互补的基一问题的解中是非基变量；将这对互补的基一问题的解中是非基变量；将这对互补的基一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有：解分别代入原问题和对偶问题的目标函数有：解分别代入原问题和对偶问题的目标函数有：解分别代入原问题和对偶问题的目标函数有：第20页/共22页例例第21页/共22页