第二章对偶规划精选PPT.ppt

第二章对偶规划第1页，本讲稿共159页将将分分块块形形式式代代入入矩矩阵阵形形式式标标准准型型，得得出出两两个基本表达式：个基本表达式：（1）由约束条件）由约束条件 可得可得用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：（2-1）略讲第2页，本讲稿共159页（2）将将式式（2-12-1）代代入入目目标标函函数数的的表表达达式式，可得：可得：用非基变量表示目标函数的表达式：用非基变量表示目标函数的表达式：略讲第3页，本讲稿共159页（3）借借助助一一个个恒恒等等式式推推出出用用非非基基变变量量表表示示目标函数的另一个等价表达式：目标函数的另一个等价表达式：代入式（代入式（2-22-2），并令），并令 （2-4）单纯形乘子单纯形乘子 略讲第4页，本讲稿共159页三、单纯形表格的矩阵形式：三、单纯形表格的矩阵形式：cjCBXB xjb CB CN 0 略讲第5页，本讲稿共159页第第2节节 改进单纯形法（自学）改进单纯形法（自学）略讲第6页，本讲稿共159页一、对偶思想一、对偶思想1.对对对对偶偶偶偶思思思思想想想想举举举举例例例例-矩矩矩矩形形形形的的的的面面面面积积积积与与与与周周周周长长长长关关关关系系系系的的的的两两两两种种种种表表表表述：述：述：述：周长一定的矩形中，以正方形面积最大；周长一定的矩形中，以正方形面积最大；周长一定的矩形中，以正方形面积最大；周长一定的矩形中，以正方形面积最大；面积面积面积面积一定的矩形中，以正方形周长最小；一定的矩形中，以正方形周长最小；一定的矩形中，以正方形周长最小；一定的矩形中，以正方形周长最小；第第3节节 对偶问题的提出对偶问题的提出-1.6对偶是指对同一问题从不同的角度观察，对偶是指对同一问题从不同的角度观察，得到两种独立的表述的思想。得到两种独立的表述的思想。第7页，本讲稿共159页例例1 要求制定一个生产计划方案，在设备要求制定一个生产计划方案，在设备和和原材料可能供应的范围内，使得产品的总利润原材料可能供应的范围内，使得产品的总利润最大最大：甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元二、对偶问题的提出二、对偶问题的提出二、对偶问题的提出二、对偶问题的提出第8页，本讲稿共159页它它的的对对对对偶偶偶偶问问问问题题题题就就是是一一个个价价价价格格格格系系系系统统统统，使使在在平平衡衡了了设设备备和和原原材材料的直接成本后，所确定的料的直接成本后，所确定的价格系统最具有竞争力。价格系统最具有竞争力。价格系统最具有竞争力。价格系统最具有竞争力。（用用于于生生产产第第i种种产产品品的的资资源源转转让让收收益益不不小小于于生生产产该种产品时获得的利润）该种产品时获得的利润）第9页，本讲稿共159页若工厂自己不生产若工厂自己不生产甲甲和和乙乙产品，将现有的设备及产品，将现有的设备及原材料转为外租时，那么原材料转为外租时，那么上述的价格系统能保证不亏上述的价格系统能保证不亏上述的价格系统能保证不亏上述的价格系统能保证不亏本又最富有竞争力本又最富有竞争力本又最富有竞争力本又最富有竞争力（包工及原材料的总价格最低）。（包工及原材料的总价格最低）。当原问题和对偶问题都取得最优解时，这一对当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：线性规划对应的目标函数值是相等的：Zmax=Wmin=14 对偶变量的经济意义可以解释为对设备及原材料的单对偶变量的经济意义可以解释为对设备及原材料的单对偶变量的经济意义可以解释为对设备及原材料的单对偶变量的经济意义可以解释为对设备及原材料的单位定价位定价位定价位定价 。表示对偶关系表示对偶关系第10页，本讲稿共159页3.再举一个对偶问题的例子：再举一个对偶问题的例子：饮食与营养问题饮食与营养问题饮食与营养问题饮食与营养问题 例例例例2 2 采购甲、乙、丙、丁采购甲、乙、丙、丁采购甲、乙、丙、丁采购甲、乙、丙、丁44种食品量分别为种食品量分别为种食品量分别为种食品量分别为x x1 1，x x2 2，x x3 3，x x4 4 单位，在保证人体所需维生素单位，在保证人体所需维生素单位，在保证人体所需维生素单位，在保证人体所需维生素A A、B B、C C前提下，使前提下，使前提下，使前提下，使总的花费最小。总的花费最小。总的花费最小。总的花费最小。成本成本第11页，本讲稿共159页构建对偶构建对偶构建对偶构建对偶线性规划模型：线性规划模型：换一个角度，生产营养药制品公司力图制造各种换一个角度，生产营养药制品公司力图制造各种营养药品代替食品。于是，营养药品的单位成本不能营养药品代替食品。于是，营养药品的单位成本不能超过相应食品的市场价格。超过相应食品的市场价格。制药公司面对的问题是制药公司面对的问题是为营养药品确定单价为营养药品确定单价为营养药品确定单价为营养药品确定单价，以，以获得获得最大的收益最大的收益，同时，同时与真正的食品竞争与真正的食品竞争。第12页，本讲稿共159页由此得到下面的对偶问题：由此得到下面的对偶问题：由此得到下面的对偶问题：由此得到下面的对偶问题：第13页，本讲稿共159页二、原问题和对偶问题的关系二、原问题和对偶问题的关系1 1.对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系对称形式的对偶关系（1）定义：）定义：若若原问题是原问题是 第14页，本讲稿共159页则定义其对偶问题为则定义其对偶问题为:这两个式子之间的变换关系称为这两个式子之间的变换关系称为“对称对称形式的对偶关系形式的对偶关系”。第15页，本讲稿共159页（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述（L）（3）怎样从原始问题写出其对偶问题？）怎样从原始问题写出其对偶问题？对称性问题按照定义对称性问题按照定义 “上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小”第16页，本讲稿共159页例例3 写出下面线性规划的对偶规划写出下面线性规划的对偶规划 第17页，本讲稿共159页（1）原问题原问题（2）对偶问题对偶问题特特点点：对对偶偶变变量量符符号号不限，系数阵转置。不限，系数阵转置。(特点：等式约束特点：等式约束)2.非对称形式的对偶关系：非对称形式的对偶关系：为什么？证明略。看一个具体例子：为什么？证明略。看一个具体例子：第18页，本讲稿共159页例例4写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：第19页，本讲稿共159页第20页，本讲稿共159页第21页，本讲稿共159页第22页，本讲稿共159页第23页，本讲稿共159页第24页，本讲稿共159页第25页，本讲稿共159页 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数MaxZ目标函数目标函数MinW约束条件数：约束条件数：m个个第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“=”对偶变量数：对偶变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 决策变量数：决策变量数：n个个第第j个变量个变量0第第j个变量个变量0第第j个变量是自由变量个变量是自由变量 约束条件数：约束条件数：n第第 j个个 约约 束束 条条 件件 类类 型型 为为“”第第 j个个 约约 束束 条条 件件 类类 型型 为为“”第第j个约束条件类型为个约束条件类型为“=”（2）原始问题与对偶问题关系表）原始问题与对偶问题关系表第26页，本讲稿共159页第27页，本讲稿共159页对对偶偶定定理理是是是是揭揭揭揭示示示示原原原原始始始始问问问问题题题题与与与与对对对对偶偶偶偶问问问问题题题题解解解解之之之之间间间间重要关系的重要关系的重要关系的重要关系的 定理定理定理定理1 1 对称性定理对称性定理(证明略证明略)对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题对偶问题的对偶是原问题。第第4节节 线性规划的线性规划的对偶理论对偶理论一系列定理。一系列定理。第28页，本讲稿共159页定理定理2 弱对偶定理弱对偶定理对于任意的可行解成立对于任意的可行解成立第29页，本讲稿共159页第30页，本讲稿共159页该结论对非对称形式的对偶问题同样成立该结论对非对称形式的对偶问题同样成立。由该定理可以得到由该定理可以得到关于关于“界界”的结果的结果:极小化问题有下界极小化问题有下界推推论论1 极极大大化化问问题题的的任任意意一一个个可可行行解解所所对对应应的的目目标标函数值是其对偶问题最优目标函数值的一个下界。函数值是其对偶问题最优目标函数值的一个下界。第31页，本讲稿共159页极大化问题有上界极大化问题有上界推论推论2 极小化问题的任意一个可行解所对应的极小化问题的任意一个可行解所对应的极小化问题的任意一个可行解所对应的极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个目标函数值是其对偶问题最优目标函数值的一个目标函数值是其对偶问题最优目标函数值的一个目标函数值是其对偶问题最优目标函数值的一个上界。上界。上界。上界。第32页，本讲稿共159页推论推论3 3 若原问题与对偶问题都有可行解，则若原问题与对偶问题都有可行解，则它们都有最优解。它们都有最优解。能达到最优能达到最优（由连续函数的性质得到）（由连续函数的性质得到）证毕证毕第33页，本讲稿共159页推论推论4 若原问题若原问题(对偶问题对偶问题)为无界解，则其为无界解，则其对偶问题对偶问题(原问题原问题)无可行解。其逆不真。无可行解。其逆不真。证明证明由弱对偶定理得由弱对偶定理得由弱对偶定理得由弱对偶定理得:第34页，本讲稿共159页第35页，本讲稿共159页第36页，本讲稿共159页C =bC =bCXYb弱对偶弱对偶定定理理已已知知结结论论最优解定义最优解定义最优解定义最优解定义X=CX X bY=特别取特别取CYb证明思路证明思路 第37页，本讲稿共159页第38页，本讲稿共159页 若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最优值相等，反之亦然。优值相等，反之亦然。优值相等，反之亦然。优值相等，反之亦然。定理定理4 强对偶定理强对偶定理第39页，本讲稿共159页第40页，本讲稿共159页推论推论 对偶问题的最优解为原问题最优表对偶问题的最优解为原问题最优表中，相应的松弛变量的检验数的相反数。中，相应的松弛变量的检验数的相反数。第41页，本讲稿共159页单纯形方法计算过程单纯形方法计算过程:第42页，本讲稿共159页第43页，本讲稿共159页第44页，本讲稿共159页第45页，本讲稿共159页第46页，本讲稿共159页略讲略讲 第47页，本讲稿共159页甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元第48页，本讲稿共159页定理定理5 互补松弛定理互补松弛定理略讲略讲 第49页，本讲稿共159页第50页，本讲稿共159页第51页，本讲稿共159页第52页，本讲稿共159页第53页，本讲稿共159页为了保证检验数的非正性取为了保证检验数的非正性取 第54页，本讲稿共159页第第6节节 对偶单纯形法对偶单纯形法最小比值原则第55页，本讲稿共159页第56页，本讲稿共159页第57页，本讲稿共159页为了保证检验数的非正性取为了保证检验数的非正性取 第58页，本讲稿共159页第59页，本讲稿共159页第60页，本讲稿共159页应知道此方法：第61页，本讲稿共159页第62页，本讲稿共159页第63页，本讲稿共159页回到（回到（55张）前几张张）前几张PPT总结对偶单纯性方法。总结对偶单纯性方法。第64页，本讲稿共159页第65页，本讲稿共159页第66页，本讲稿共159页作业作业 P-73-1.12第67页，本讲稿共159页第68页，本讲稿共159页第69页，本讲稿共159页第70页，本讲稿共159页P-73-1.12第71页，本讲稿共159页第72页，本讲稿共159页5/7202 2第73页，本讲稿共159页第74页，本讲稿共159页第75页，本讲稿共159页第76页，本讲稿共159页第77页，本讲稿共159页实际上，此题实际上，此题为无界解。为无界解。举例：举例：第78页，本讲稿共159页举例：举例：第79页，本讲稿共159页第80页，本讲稿共159页第81页，本讲稿共159页第82页，本讲稿共159页第83页，本讲稿共159页第84页，本讲稿共159页第85页，本讲稿共159页第86页，本讲稿共159页第87页，本讲稿共159页第88页，本讲稿共159页第89页，本讲稿共159页第90页，本讲稿共159页第91页，本讲稿共159页第92页，本讲稿共159页第93页，本讲稿共159页第94页，本讲稿共159页第95页，本讲稿共159页第96页，本讲稿共159页第97页，本讲稿共159页第98页，本讲稿共159页 第第7节节 灵敏度分析灵敏度分析第99页，本讲稿共159页将模型写在黑板上第100页，本讲稿共159页第101页，本讲稿共159页第102页，本讲稿共159页第103页，本讲稿共159页第104页，本讲稿共159页第105页，本讲稿共159页第106页，本讲稿共159页第107页，本讲稿共159页第108页，本讲稿共159页第109页，本讲稿共159页第110页，本讲稿共159页第111页，本讲稿共159页第112页，本讲稿共159页第113页，本讲稿共159页第114页，本讲稿共159页第115页，本讲稿共159页第116页，本讲稿共159页第117页，本讲稿共159页第118页，本讲稿共159页第119页，本讲稿共159页第120页，本讲稿共159页第121页，本讲稿共159页第122页，本讲稿共159页第123页，本讲稿共159页第124页，本讲稿共159页第125页，本讲稿共159页第126页，本讲稿共159页第127页，本讲稿共159页第128页，本讲稿共159页第129页，本讲稿共159页第130页，本讲稿共159页第131页，本讲稿共159页第132页，本讲稿共159页第133页，本讲稿共159页第134页，本讲稿共159页第135页，本讲稿共159页第136页，本讲稿共159页第137页，本讲稿共159页第138页，本讲稿共159页第139页，本讲稿共159页第140页，本讲稿共159页第141页，本讲稿共159页二、思考练习二、思考练习考察线性规划问题考察线性规划问题考察线性规划问题考察线性规划问题(1)(1)：一、讨论总结对偶定理的应用。一、讨论总结对偶定理的应用。第142页，本讲稿共159页1.写出其对偶问题写出其对偶问题;2.讨论：如果知道是原问题的可行解（用什麽办法讨论：如果知道是原问题的可行解（用什麽办法可以较方便地寻找一个可行解？），能否对对偶可以较方便地寻找一个可行解？），能否对对偶问题的目标函数值做出估计？问题的目标函数值做出估计？以此为启发，能否对原问题目标函数值作出以此为启发，能否对原问题目标函数值作出估计？估计？第143页，本讲稿共159页可可以以观观察察到到是是原原始始问问题题的的可可行行解解。不不要要使使用用单单纯纯形形法法求求解解，能能否否说说明明原原始始问问题题最最优解无界？优解无界？(2)下面的问题是某线性规划的对偶问题，下面的问题是某线性规划的对偶问题，请写出其原始问题。请写出其原始问题。第144页，本讲稿共159页回顾回顾第145页，本讲稿共159页第146页，本讲稿共159页第第5节节 对偶问题的经济含意对偶问题的经济含意-影子价格影子价格影子价格影子价格第147页，本讲稿共159页第148页，本讲稿共159页第149页，本讲稿共159页第150页，本讲稿共159页增加该种资源的投入，不能带来利润的提高。增加该种资源的投入，不能带来利润的提高。第151页，本讲稿共159页第152页，本讲稿共159页第153页，本讲稿共159页第154页，本讲稿共159页第155页，本讲稿共159页第156页，本讲稿共159页第157页，本讲稿共159页第158页，本讲稿共159页第159页，本讲稿共159页