《运筹学课件-第三节-影子价格ppt.ppt》由会员分享，可在线阅读，更多相关《运筹学课件-第三节-影子价格ppt.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 第三节第三节 影子价格影子价格 对偶问题解的经济解释对偶问题解的经济解释影子价格影子价格 我们已经明白原始线性规划与对偶线性规我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们解之间的关系，划之间形式上的对偶以及他们解之间的关系，那么对偶问题的解除了前面引例中提到的租金那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？这种经济含义外其深刻的经济含义是什么呢？运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一
2、定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 对偶问题解的经济含义分析：对偶问题解的经济含义分析：从单纯形法的矩阵描述中，目标函数取值从单纯形法的矩阵描述中，目标函数取值 Z=CBB-1b，和检验数和检验数CN -CBB-1N 中都有乘子中都有乘子Y=CBB-1。由由强强对偶对偶定理知定理知 Z*=CX*=CBB-1b=Y*b=W*由此由此Z*=Y*b=b1y1+b1y2+bmym Z*bi Z*bi （Y*b）bi=CBB-1=Y*或或=yi*运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确
3、线性规划的对偶理论线性规划的对偶理论 对偶问题解的经济含义：对偶问题解的经济含义：由上面分析由上面分析对偶问题解中变量对偶问题解中变量 yi*的的经济含义是在其他条件不变的情况下，单位第经济含义是在其他条件不变的情况下，单位第 i 种种“资源资源”变化所引起的目标函数最优值的变化所引起的目标函数最优值的变化。变化。所以，所以，yi*描述了原始线性规划问题达描述了原始线性规划问题达到到最优时最优时（各种（各种“资源资源”都处于都处于最优最优的配置时）的配置时），第，第 i 种种“资源资源”的某种的某种“价值价值”，故称其为，故称其为第第 i 种种“资源资源”的的影子价格。影子价格。下面图解阐述影
4、子价格的直观含义：下面图解阐述影子价格的直观含义：运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 影子价格影子价格我们首先采用我们首先采用单纯形法求解得单纯形法求解得王老板的家具生王老板的家具生产模型产模型（P）的最优解、最优基矩阵如下的最优解、最优基矩阵如下（P）的最优解为的最优解为X*=（15，20，0，0）TB=（p2，p1）=34412（D）的最优解为的最优解为Y*=CBB-1=（5，15）CB=（C2，C1）=（30，50）B-1=1 -2-1/2 3/2（P）max Z=50
5、 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 影子价格影子价格王老板的家具生产模型的图解：王老板的家具生产模型的图解：x1x2P可行域可行域1350=50 x1+30 x2（15，20）（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)2x1+x2=504x1+3x2=120L0：
6、50 x1+30 x2运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 影子价格的直观含义影子价格的直观含义：x1x24x1+3x2=1202x1+x2=50 L0：50 x1+30 x2 P可行域可行域（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)2x1+x2=51 4x1+3x2=1211365=50 x1+30 x21355=50 x1+30 x2运筹学教程在整堂课的教学中，刘教师总是让学生
7、带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 影子价格的特点：影子价格的特点：影子价格是对偶解的一个十分形象的名称，它既表明对偶影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的解是对系统内部资源在当前的最优利用配置下最优利用配置下的一种客观估价，的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。格。特点特点1、影子价格是对系统资源的一种影子价格是对系统资源的一种内部最优估价内部最优估价，只，只有当系统有当系统 达到最优状态时
8、才可能赋予资源这种价值。达到最优状态时才可能赋予资源这种价值。系统资源的一种系统资源的一种动态价格体系动态价格体系，影子价格的大小与系统的影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。化都可能会引起影子价格的变化。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确线性规划的对偶理论线性规划的对偶理论 影子价格的特点：影子价格的特点：特点特点2、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因影子价格是一
9、种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理有中十分重要的应用价值。企业管理者可以根据资源在企业而，在经济管理有中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。影子价格内部的影子价格的大小决定企业的经营策略。影子价格yi相当于在资源得到相当于在资源得到最优利用的生产条件下，资源最优利用的生产条件下，资源bi每增加一个单位，目标函数每增加一个单位，目标函数z 的增量。的增量。n特点特点3、影子价格的大小客观地反映影子价格的大小客观地反映资源在系统内的资源在系统内的稀缺程度稀缺程度。如果某种资。如果某种资源在系统内供大于求，尽管它有实实在
10、在的市场价格，但它在系统内的源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子影子价格却为零，而影子价格越高，价格却为零，而影子价格越高，资源在系统内资源在系统内越越稀缺。稀缺。n n当影子价格高于市场价格，应该买进资源；当影子价格高于市场价格，应该买进资源；当影子价格高于市场价格，应该买进资源；当影子价格高于市场价格，应该买进资源；n n当影子价格低于市场价格，应该卖出资源；当影子价格低于市场价格，应该卖出资源；当影子价格低于市场价格，应该卖出资源；当影子价格低于市场价格，应该卖出资源；设备A:y1=0设备B:y2=0.25调试C:y3=0.5运筹学教程在整堂课的教学中，刘教
11、师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确特点特点4、表明生产过程中该种资源的影子价格不等于表明生产过程中该种资源的影子价格不等于0 0，表明，表明生产过程中资源得到充分利用。生产过程中资源得到充分利用。如果某种资源未得到充分利用，该种资源的影子价格如果某种资源未得到充分利用，该种资源的影子价格=0=0；运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确特点特点5、从影子价格考察单纯形表的计算。从影子价格考察单纯形表的计算。CjCj代表第代表第j j种产品的产值，种产品的产值，是生产
12、该种产品所消耗各项资源的影子价格的总和，即产品的是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。隐含成本。当产品产值大于隐含成本时，表明生产该产品有利。当产品产值大于隐含成本时，表明生产该产品有利。当产品产值小于隐含成本时，表明用资源生产别的产品有利。当产品产值小于隐含成本时，表明用资源生产别的产品有利。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第四节第四节对偶单纯形法对偶单纯形法一、对偶单纯形法的基本思路一、对偶单纯形法的基本思路对对偶偶单单纯纯形形法法是是应应用用对对偶偶原原理理求求解解线线性性规规
13、划划的的一一种种方方法法在在原原问问题题的的单单纯纯形形表表上进行上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 1、单纯形法求解单纯形法求解初初始始可可行行基基（对对应应一一个个初初始始基基可可行行解解）迭迭代代另另一一个个可可行行基基（对对应应另另一一个个基基可可行行解），直至解），直至所有检验数所有检验数0为止为止。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明
14、确 所有检验数所有检验数0意味着意味着，说说明明原原问问题题的的最最优优基基也也是是对对偶偶问问题题的的可可行行基基。换换言言之之，当当原原问问题题的的基基B既既是是原原可可行行基基又又是是对偶可行基时，对偶可行基时，B成为最优基。成为最优基。补补充充定定理理B是是线线性性规规划划的的最最优优基基的的充充要要条条件件是，是，B是可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的求解过程就是：单纯形法的求解过程就是：在在保保持持原原问问题题可可行行的的前前提提下
15、下（b列列保保持持0），通过逐步迭代通过逐步迭代实现对偶可行实现对偶可行（检验数行（检验数行0）。2、对偶单纯形法思想：对偶单纯形法思想：换换个个角角度度考考虑虑LP求求解解过过程程：保保持持对对偶偶可可行行的的前前提提下下（检检验验数数行行保保持持0），通通过过逐逐步步迭迭代代实实现现原原问问题题可可行行（b列列0，从从非非可可行行解解变变成成可行解）。可行解）。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3、对偶单纯形法的实施、对偶单纯形法的实施（1）使用条件：）使用条件：检验数全部检验数全部0；解答列解答列bi至少
16、一个元素至少一个元素0；（2）实施对偶单纯形法的基本原则：）实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换每一次每一次迭代过程中取出迭代过程中取出基变量中的一个负分量基变量中的一个负分量作为作为换出换出变量变量去去替换替换某个某个非基变量非基变量（作为（作为换入变量换入变量），使），使原问题的非可行解向可行解靠近。原问题的非可行解向可行解靠近。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确二、对偶单纯形法的计算步骤二、对偶单纯形法的计算步骤：建立初始单纯形表，计算检验数行。建立
17、初始单纯形表，计算检验数行。bibi00已得最优解；已得最优解；已得最优解；已得最优解；bibi至少一个元素至少一个元素至少一个元素至少一个元素0,0,转下步转下步转下步转下步;bibi00原始单纯形法；原始单纯形法；原始单纯形法；原始单纯形法；bibi至少一个元素至少一个元素至少一个元素至少一个元素0,0,另外处理；另外处理；另外处理；另外处理；(原原原原问问问问题题题题、对对对对偶偶偶偶问问问问题题题题均均均均无无无无可可可可行行行行解解解解，引进人工变量引进人工变量引进人工变量引进人工变量)检验数全部检验数全部检验数全部检验数全部0 0（非基变量检验数（非基变量检验数（非基变量检验数（非
18、基变量检验数000运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 基变换：基变换：先先确确定定换换出出变变量量bi中中的的负负元元素素（一一般般选最小的负元素）选最小的负元素）对应的基变量对应的基变量出基出基；即即相应的行相应的行为主元行为主元行。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确然然后后确确定定换换入入变变量量原原则则是是：在在保保持持对对偶偶可行的前提可行的前提下，下，减少原问题的不可行性减少原问题的不可行性。如果如果（最小比值原则）（
19、最小比值原则），则选，则选为换入变量，相为换入变量，相应的列为应的列为主元列主元列，主元行和主元列交叉处的，主元行和主元列交叉处的元素元素为主元素为主元素。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 按按主主元元素素进进行行换换基基迭迭代代，将将主主元元素素变变成成1，主元列变成单位向量，主元列变成单位向量，得到新的单纯形表。，得到新的单纯形表。继续以上步骤，直至求出最优解。继续以上步骤，直至求出最优解
20、。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确举例举例用对偶单纯形法求解用对偶单纯形法求解LP：化为化为化为化为标准型标准型标准型标准型将将2个等式约束个等式约束两边分别乘以两边分别乘以-1，然后列表求解，然后列表求解如下：如下：Cj-15 -24 -5 0 0CB 基 by1 y2 y3 y4 y50 y4 -20 y5 -10 -6 -1 1 0-5 -2 -1 0 1Cj-Zj-15 -24 -5 0 0-24 y2 1/30 y5-1/30 1 1/6 -1/6 0-5 0 -2/3 -1/3 1Cj-Zj-15
21、 0 -1 -4 0-24 y2 1/4-5 y3 1/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2Cj-Zj-15/2 0 0 -7/2 -3/2运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确对偶单纯形法求解线性规划问题时，当使用对偶单纯形法求解线性规划问题时，当使用约束条件为约束条件为“大于等于大于等于”，不必引进人工变，不必引进人工变量，计算简化。量，计算简化。注意：在初始单纯形表其对偶问题应该是基注意：在初始单纯形表其对偶问题应该是基可行解，对多数线性规划问题难实现。可行解，对多数线性规划
22、问题难实现。主要应用：灵敏度分析。主要应用：灵敏度分析。运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确练习:使用对偶单纯形法求解运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Cj-4-1-300CB基bx1x2x3x4x50 x4-5-1-1-1100 x5-3-11401Cj-zj-4-1-300-1x25111-100 x5-8-20311Cj-zj-30-2-10运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Cj-4-1-300CB基bx1x2x3x4x5-4x21015/2-1/21/2-1x1410-3/2-1/2-1/2Cj-zj00-13/2-5/2-3/2X=(4,1,0)T,最优值z=17运筹学教程在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确n小结小结n1.影子价格影子价格n2.对偶单纯形法对偶单纯形法n作业作业:n2.9(1)