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