第二章对偶规划PPT讲稿.ppt

《第二章对偶规划PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章对偶规划PPT讲稿.ppt（159页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章对偶规划第1页，共159页，编辑于2022年，星期三将将分分块块形形式式代代入入矩矩阵阵形形式式标标准准型型，得得出出两两个基本表达式：个基本表达式：（1）由约束条件）由约束条件 可得可得用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：（2-1）略讲第2页，共159页，编辑于2022年，星期三（2）将将式式（2-1）代代入入目目标标函函数数的的表表达达式式，可得：可得：用非基变量表示目标函数的表达式：用非基变量表示目标函数的表达式：略讲第3页，共159页，编辑于2022年，星期三（3）借借助助一一个个恒恒等等式式推推出出用用非非基基变变量量表表示示目目标函数的另一个等价表达式

2、：标函数的另一个等价表达式：代入式（代入式（2-22-2），并令），并令 （2-4）单纯形乘子单纯形乘子 略讲第4页，共159页，编辑于2022年，星期三三、单纯形表格的矩阵形式：三、单纯形表格的矩阵形式：cjCBXB xjb CB CN 0 略讲第5页，共159页，编辑于2022年，星期三第第2节节 改进单纯形法（自学）改进单纯形法（自学）略讲第6页，共159页，编辑于2022年，星期三一、对偶思想一、对偶思想1.对对偶偶思思想想举举例例-矩矩形形的的面面积积与与周周长长关关系系的的两种表述：两种表述：周长一定的矩形中，以正方形面积最大；周长一定的矩形中，以正方形面积最大；面积面积一定的矩形

3、中，以正方形周长最小；一定的矩形中，以正方形周长最小；第第3节节 对偶问题的提出对偶问题的提出-1.6对偶是指对同一问题从不同的角度观察，对偶是指对同一问题从不同的角度观察，得到两种独立的表述的思想。得到两种独立的表述的思想。第7页，共159页，编辑于2022年，星期三例例1 要求制定一个生产计划方案，在设备要求制定一个生产计划方案，在设备和原材料可能供应的范围内，使得产品的总和原材料可能供应的范围内，使得产品的总利润最大利润最大：甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元二、对偶问题的提出二、对偶问题的提出

4、第8页，共159页，编辑于2022年，星期三它它的的对对对对偶偶偶偶问问问问题题题题就就是是一一个个价价价价格格格格系系系系统统统统，使使在在平平衡衡了了设设备备和和原原材材料料的直接成本后，所确定的的直接成本后，所确定的价格系统最具有竞争力。价格系统最具有竞争力。价格系统最具有竞争力。价格系统最具有竞争力。（用用于于生生产产第第i种种产产品品的的资资源源转转让让收收益益不不小小于于生生产产该该种产品时获得的利润）种产品时获得的利润）第9页，共159页，编辑于2022年，星期三若工厂自己不生产若工厂自己不生产甲甲和和乙乙产品，将现有的设备及产品，将现有的设备及原材料转为外租时，那么原材料转为外

5、租时，那么上述的价格系统能保证不亏上述的价格系统能保证不亏上述的价格系统能保证不亏上述的价格系统能保证不亏本又最富有竞争力本又最富有竞争力本又最富有竞争力本又最富有竞争力（包工及原材料的总价格最低）。（包工及原材料的总价格最低）。当原问题和对偶问题都取得最优解时，这一对线当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：性规划对应的目标函数值是相等的：Zmax=Wmin=14 对偶变量的经济意义可以解释为对设备及原材料的对偶变量的经济意义可以解释为对设备及原材料的对偶变量的经济意义可以解释为对设备及原材料的对偶变量的经济意义可以解释为对设备及原材料的单位定价单位定价单位

6、定价单位定价 。表示对偶关系表示对偶关系第10页，共159页，编辑于2022年，星期三3.再举一个对偶问题的例子：再举一个对偶问题的例子：饮食与营养问题饮食与营养问题饮食与营养问题饮食与营养问题 例例例例2 2 采购甲、乙、丙、丁采购甲、乙、丙、丁采购甲、乙、丙、丁采购甲、乙、丙、丁44种食品量分别为种食品量分别为种食品量分别为种食品量分别为x x1 1，x x2 2，x x3 3，x x4 4 单位，在保证人体所需维生素单位，在保证人体所需维生素单位，在保证人体所需维生素单位，在保证人体所需维生素A A、B B、C C前提下，使前提下，使前提下，使前提下，使总的花费最小。总的花费最小。总的花

7、费最小。总的花费最小。成本成本第11页，共159页，编辑于2022年，星期三构建对偶构建对偶线性规划模型：线性规划模型：换一个角度，生产营养药制品公司力图制造各种营养药换一个角度，生产营养药制品公司力图制造各种营养药品代替食品。于是，营养药品的单位成本不能超过相应食品品代替食品。于是，营养药品的单位成本不能超过相应食品的市场价格。的市场价格。制药公司面对的问题是制药公司面对的问题是为营养药品确定单价为营养药品确定单价为营养药品确定单价为营养药品确定单价，以，以获获得最大的收益得最大的收益，同时，同时与真正的食品竞争与真正的食品竞争。第12页，共159页，编辑于2022年，星期三由此得到下面的对

8、偶问题：由此得到下面的对偶问题：第13页，共159页，编辑于2022年，星期三二、原问题和对偶问题的关系二、原问题和对偶问题的关系1.对称形式的对偶关系对称形式的对偶关系（1）定义：）定义：若若原问题是原问题是 第14页，共159页，编辑于2022年，星期三则定义其对偶问题为则定义其对偶问题为:这两个式子之间的变换关系称为这两个式子之间的变换关系称为“对对称形式的对偶关系称形式的对偶关系”。第15页，共159页，编辑于2022年，星期三（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述（L）（3）怎样从原始问题写出其对偶问题？）怎样从原始问题写出其对偶问题？对称性问题按照定义对称

9、性问题按照定义 “上、下上、下”交换，交换，“左、右左、右”换位，换位，不等式变号，不等式变号，“极大极大”变变“极小极小”第16页，共159页，编辑于2022年，星期三例例3 写出下面线性规划的对偶规划写出下面线性规划的对偶规划 第17页，共159页，编辑于2022年，星期三（1）原问题原问题（2）对偶问题对偶问题特特点点：对对偶偶变变量量符符号号不限，系数阵转置。不限，系数阵转置。(特点：等式约束特点：等式约束)2.非对称形式的对偶关系：非对称形式的对偶关系：为什么？证明略。看一个具体例子：为什么？证明略。看一个具体例子：第18页，共159页，编辑于2022年，星期三例例4写出下面线性规划

10、的对偶规划：写出下面线性规划的对偶规划：第19页，共159页，编辑于2022年，星期三第20页，共159页，编辑于2022年，星期三第21页，共159页，编辑于2022年，星期三第22页，共159页，编辑于2022年，星期三第23页，共159页，编辑于2022年，星期三第24页，共159页，编辑于2022年，星期三第25页，共159页，编辑于2022年，星期三 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数MaxZ目标函数目标函数MinW约束条件数：约束条件数：m个个第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型

11、为“”第第i个约束条件类型为个约束条件类型为“=”对偶变量数：对偶变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 决策变量数：决策变量数：n个个第第j个变量个变量0第第j个变量个变量0第第j个变量是自由变量个变量是自由变量 约束条件数：约束条件数：n第第j个约束条件类型为个约束条件类型为“”第第j个约束条件类型为个约束条件类型为“”第第j个约束条件类型为个约束条件类型为“=”（2）原始问题与对偶问题关系表）原始问题与对偶问题关系表第26页，共159页，编辑于2022年，星期三第27页，共159页，编辑于2022年，星期三对对偶偶定定理理是是揭揭示示

12、原原始始问问题题与与对对偶偶问问题题解解之之间重要关系的间重要关系的 定理定理1 对称性定理对称性定理(证明略证明略)对偶问题的对偶是原问题对偶问题的对偶是原问题。第第4节节 线性规划的线性规划的对偶理论对偶理论一系列定理。一系列定理。第28页，共159页，编辑于2022年，星期三定理定理2 弱对偶定理弱对偶定理对于任意的可行解成立对于任意的可行解成立第29页，共159页，编辑于2022年，星期三第30页，共159页，编辑于2022年，星期三该结论对非对称形式的对偶问题同样成立该结论对非对称形式的对偶问题同样成立。由该定理可以得到由该定理可以得到关于关于“界界”的结果的结果:极小化问题有下界极

13、小化问题有下界推推论论1 极极大大化化问问题题的的任任意意一一个个可可行行解解所所对对应应的的目目标标函函数数值值是是其其对对偶偶问问题题最最优优目目标标函函数数值值的的一一个个下下界。界。第31页，共159页，编辑于2022年，星期三极大化问题有上界极大化问题有上界推论推论2 极小化问题的任意一个可行解所对应极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的目标函数值是其对偶问题最优目标函数值的一个上界。的一个上界。第32页，共159页，编辑于2022年，星期三推论推论3 若原问题与对偶问题都有可行解，则它若原问题与对偶问题都有可行解，则它们都有最优解。们都有最优解。能

14、达到最优能达到最优（由连续函数的性质得到）（由连续函数的性质得到）证毕证毕第33页，共159页，编辑于2022年，星期三推论推论4 若原问题若原问题(对偶问题对偶问题)为无界解，则其对为无界解，则其对偶问题偶问题(原问题原问题)无可行解。其逆不真。无可行解。其逆不真。证明证明由弱对偶定理得由弱对偶定理得由弱对偶定理得由弱对偶定理得:第34页，共159页，编辑于2022年，星期三第35页，共159页，编辑于2022年，星期三第36页，共159页，编辑于2022年，星期三C =bC =bCXYb弱对偶弱对偶定定理理已已知知结结论论最优解定义最优解定义最优解定义最优解定义X=CX X bY=特别取特

15、别取CYb证明思路证明思路 第37页，共159页，编辑于2022年，星期三第38页，共159页，编辑于2022年，星期三 若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最若原问题有最优，则对偶问题也有最优，且最优值相等，反之亦然。优值相等，反之亦然。优值相等，反之亦然。优值相等，反之亦然。定理定理4 强对偶定理强对偶定理第39页，共159页，编辑于2022年，星期三第40页，共159页，编辑于2022年，星期三推论推论 对偶问题的最优解为原问题最优表中，对偶问题的最优解为原问题最优表中，相应的松弛变量的检验数的相反数。相应

16、的松弛变量的检验数的相反数。第41页，共159页，编辑于2022年，星期三单纯形方法计算过程单纯形方法计算过程:第42页，共159页，编辑于2022年，星期三第43页，共159页，编辑于2022年，星期三第44页，共159页，编辑于2022年，星期三第45页，共159页，编辑于2022年，星期三第46页，共159页，编辑于2022年，星期三略讲略讲 第47页，共159页，编辑于2022年，星期三甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元第48页，共159页，编辑于2022年，星期三定理定理5 互补松弛定理互补

17、松弛定理略讲略讲 第49页，共159页，编辑于2022年，星期三第50页，共159页，编辑于2022年，星期三第51页，共159页，编辑于2022年，星期三第52页，共159页，编辑于2022年，星期三第53页，共159页，编辑于2022年，星期三为了保证检验数的非正性取为了保证检验数的非正性取 第54页，共159页，编辑于2022年，星期三第第6节节 对偶单纯形法对偶单纯形法最小比值原则第55页，共159页，编辑于2022年，星期三第56页，共159页，编辑于2022年，星期三第57页，共159页，编辑于2022年，星期三为了保证检验数的非正性取为了保证检验数的非正性取 第58页，共159页

18、，编辑于2022年，星期三第59页，共159页，编辑于2022年，星期三第60页，共159页，编辑于2022年，星期三应知道此方法：第61页，共159页，编辑于2022年，星期三第62页，共159页，编辑于2022年，星期三第63页，共159页，编辑于2022年，星期三回到（回到（55张）前几张张）前几张PPT总结对偶单纯性方法。总结对偶单纯性方法。第64页，共159页，编辑于2022年，星期三第65页，共159页，编辑于2022年，星期三第66页，共159页，编辑于2022年，星期三作业作业 P-73-1.12第67页，共159页，编辑于2022年，星期三第68页，共159页，编辑于2022

19、年，星期三第69页，共159页，编辑于2022年，星期三第70页，共159页，编辑于2022年，星期三P-73-1.12第71页，共159页，编辑于2022年，星期三第72页，共159页，编辑于2022年，星期三5/7202 2第73页，共159页，编辑于2022年，星期三第74页，共159页，编辑于2022年，星期三第75页，共159页，编辑于2022年，星期三第76页，共159页，编辑于2022年，星期三第77页，共159页，编辑于2022年，星期三实际上，此题实际上，此题为无界解。为无界解。举例：举例：第78页，共159页，编辑于2022年，星期三举例：举例：第79页，共159页，编辑于

20、2022年，星期三第80页，共159页，编辑于2022年，星期三第81页，共159页，编辑于2022年，星期三第82页，共159页，编辑于2022年，星期三第83页，共159页，编辑于2022年，星期三第84页，共159页，编辑于2022年，星期三第85页，共159页，编辑于2022年，星期三第86页，共159页，编辑于2022年，星期三第87页，共159页，编辑于2022年，星期三第88页，共159页，编辑于2022年，星期三第89页，共159页，编辑于2022年，星期三第90页，共159页，编辑于2022年，星期三第91页，共159页，编辑于2022年，星期三第92页，共159页，编辑于2

21、022年，星期三第93页，共159页，编辑于2022年，星期三第94页，共159页，编辑于2022年，星期三第95页，共159页，编辑于2022年，星期三第96页，共159页，编辑于2022年，星期三第97页，共159页，编辑于2022年，星期三第98页，共159页，编辑于2022年，星期三 第第7节节 灵敏度分析灵敏度分析第99页，共159页，编辑于2022年，星期三将模型写在黑板上第100页，共159页，编辑于2022年，星期三第101页，共159页，编辑于2022年，星期三第102页，共159页，编辑于2022年，星期三第103页，共159页，编辑于2022年，星期三第104页，共159

22、页，编辑于2022年，星期三第105页，共159页，编辑于2022年，星期三第106页，共159页，编辑于2022年，星期三第107页，共159页，编辑于2022年，星期三第108页，共159页，编辑于2022年，星期三第109页，共159页，编辑于2022年，星期三第110页，共159页，编辑于2022年，星期三第111页，共159页，编辑于2022年，星期三第112页，共159页，编辑于2022年，星期三第113页，共159页，编辑于2022年，星期三第114页，共159页，编辑于2022年，星期三第115页，共159页，编辑于2022年，星期三第116页，共159页，编辑于2022年，星

23、期三第117页，共159页，编辑于2022年，星期三第118页，共159页，编辑于2022年，星期三第119页，共159页，编辑于2022年，星期三第120页，共159页，编辑于2022年，星期三第121页，共159页，编辑于2022年，星期三第122页，共159页，编辑于2022年，星期三第123页，共159页，编辑于2022年，星期三第124页，共159页，编辑于2022年，星期三第125页，共159页，编辑于2022年，星期三第126页，共159页，编辑于2022年，星期三第127页，共159页，编辑于2022年，星期三第128页，共159页，编辑于2022年，星期三第129页，共159

24、页，编辑于2022年，星期三第130页，共159页，编辑于2022年，星期三第131页，共159页，编辑于2022年，星期三第132页，共159页，编辑于2022年，星期三第133页，共159页，编辑于2022年，星期三第134页，共159页，编辑于2022年，星期三第135页，共159页，编辑于2022年，星期三第136页，共159页，编辑于2022年，星期三第137页，共159页，编辑于2022年，星期三第138页，共159页，编辑于2022年，星期三第139页，共159页，编辑于2022年，星期三第140页，共159页，编辑于2022年，星期三第141页，共159页，编辑于2022年，星

25、期三二、思考练习二、思考练习考察线性规划问题考察线性规划问题(1)：一、讨论总结对偶定理的应用。一、讨论总结对偶定理的应用。第142页，共159页，编辑于2022年，星期三1.写出其对偶问题写出其对偶问题;2.讨论：如果知道是原问题的可行解（用什麽讨论：如果知道是原问题的可行解（用什麽办法可以较方便地寻找一个可行解？），能办法可以较方便地寻找一个可行解？），能否对对偶问题的目标函数值做出估计？否对对偶问题的目标函数值做出估计？以此为启发，能否对原问题目标函数值作出以此为启发，能否对原问题目标函数值作出估计？估计？第143页，共159页，编辑于2022年，星期三可可以以观观察察到到是是原原始始问

26、问题题的的可可行行解解。不不要要使使用用单单纯纯形形法法求求解解，能能否否说说明明原原始始问问题题最最优解无界？优解无界？(2)下面的问题是某线性规划的对偶问题，下面的问题是某线性规划的对偶问题，请写出其原始问题。请写出其原始问题。第144页，共159页，编辑于2022年，星期三回顾回顾第145页，共159页，编辑于2022年，星期三第146页，共159页，编辑于2022年，星期三第第5节节 对偶问题的经济含意对偶问题的经济含意-影子价格影子价格影子价格影子价格第147页，共159页，编辑于2022年，星期三第148页，共159页，编辑于2022年，星期三第149页，共159页，编辑于2022年，星期三第150页，共159页，编辑于2022年，星期三增加该种资源的投入，不能带来利润的提高。增加该种资源的投入，不能带来利润的提高。第151页，共159页，编辑于2022年，星期三第152页，共159页，编辑于2022年，星期三第153页，共159页，编辑于2022年，星期三第154页，共159页，编辑于2022年，星期三第155页，共159页，编辑于2022年，星期三第156页，共159页，编辑于2022年，星期三第157页，共159页，编辑于2022年，星期三第158页，共159页，编辑于2022年，星期三第159页，共159页，编辑于2022年，星期三