运筹学课件第三节影子价格

第三节影子价格

对偶问题解的经济解释——影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？1可编辑ppt线性规划的对偶理论

对偶问题解的经济含义分析：从单纯形法的矩阵描述中，目标函数取值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*2可编辑ppt线性规划的对偶理论

对偶问题解的经济含义：由上面分析——对偶问题解中变量yi*的经济含义是在其他条件不变的情况下，单位第i种“资源”变化所引起的目标函数最优值的变化。所以，yi*

描述了原始线性规划问题达到最优时（各种“资源”都处于最优的配置时），第i种“资源”的某种“价值”，故称其为第i种“资源”的影子价格。

下面图解阐述影子价格的直观含义：3可编辑ppt线性规划的对偶理论影子价格

我们首先采用单纯形法求解得王老板的家具生产模型（P）的最优解、最优基矩阵如下（P）的最优解为X*=（15，20，0，0）TB=（p2，p1）=412（D）的最优解为Y*=CBB-1

=（5，15）CB=（C2，C1）

=（30，50）

B-1=1-2-1/23/2（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)4可编辑ppt线性规划的对偶理论影子价格王老板的家具生产模型的图解：

x1x2P可行域1350=50x1+30x2（15，20）

（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)2x1+x2=504x1+3x2=120L0：50x1+30x25可编辑ppt线性规划的对偶理论影子价格的直观含义：x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2

P可行域（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0Z*=1350Y*=(5,15)2x1+x2=514x1+3x2=1211365=50x1+30x21355=50x1+30x26可编辑ppt线性规划的对偶理论

影子价格的特点：影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。特点1、影子价格是对系统资源的一种内部最优估价，只有当系统达到最优状态时才可能赋予资源这种价值。

系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。7可编辑ppt线性规划的对偶理论

影子价格的特点：特点2、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理有中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。影子价格yi相当于在资源得到最优利用的生产条件下，资源bi每增加一个单位，目标函数z的增量。特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。当影子价格高于市场价格，应该买进资源；当影子价格低于市场价格，应该卖出资源；

设备A:y1=0设备B:y2=0.25调试C:y3=0.58可编辑ppt特点4、表明生产过程中该种资源的影子价格不等于0，表明生产过程中资源得到充分利用。如果某种资源未得到充分利用，该种资源的影子价格=0；9可编辑ppt特点5、从影子价格考察单纯形表的计算。Cj代表第j种产品的产值，是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当产品产值大于隐含成本时，表明生产该产品有利。当产品产值小于隐含成本时，表明用资源生产别的产品有利。10可编辑ppt

第四节

对偶单纯形法

一、对偶单纯形法的基本思路

对偶单纯形法是应用对偶原理求解线性规划的一种方法——在原问题的单纯形表上进行对偶处理。

注意：不是解对偶问题的单纯形法！11可编辑ppt

1、单纯形法求解

初始可行基（对应一个初始基可行解）→迭代→另一个可行基（对应另一个基可行解），直至所有检验数≤0为止。12可编辑ppt

所有检验数≤0意味着，说明原问题的最优基也是对偶问题的可行基。换言之，当原问题的基B既是原可行基又是对偶可行基时，B成为最优基。补充定理B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。13可编辑ppt单纯形法的求解过程就是：

在保持原问题可行的前提下（b列保持≥0），通过逐步迭代实现对偶可行（检验数行≤0）。

2、

对偶单纯形法思想：

换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0），通过逐步迭代实现原问题可行（b列≥0，从非可行解变成可行解）。14可编辑ppt3、对偶单纯形法的实施（1）使用条件：

①检验数全部≤0；②解答列bi至少一个元素<0；（2）实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原问题的非可行解向可行解靠近。15可编辑ppt二、对偶单纯形法的计算步骤：

①建立初始单纯形表，计算检验数行。bi≥0——已得最优解；bi至少一个元素<0,转下步;bi≥0——原始单纯形法；bi至少一个元素<0,另外处理；(原问题、对偶问题均无可行解，引进人工变量)

检验数全部≤0（非基变量检验数<0）至少一个检验数>016可编辑ppt

基变换：

先确定换出变量——bi中的负元素（一般选最小的负元素）对应的基变量出基；即相应的行为主元行。17可编辑ppt然后确定换入变量——原则是：在保持对偶可行的前提下，减少原问题的不可行性。如果（最小比值原则），则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。18可编辑ppt19可编辑ppt

按主元素进行换基迭代，将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解。20可编辑ppt举例——用对偶单纯形法求解LP：

化为标准型→

将2个等式约束两边分别乘以-1，然后列表求解如下：21可编辑pptCj-15-24-500CB

基by1y2y3y4y50y4-20y5-10[-6]-110-5-2-101Cj-Zj-15-24-500-24y21/30y5-1/3011/6-1/60-50[-2/3]-1/31Cj-Zj-150-1-40-24y21/4-5y31/2-5/410-1/41/415/2011/2-3/2Cj-Zj-15/200-7/2-3/222可编辑ppt对偶单纯形法求解线性规划问题时，当使用约束条件为“大于等于”，不必引进人工变量，计算简化。注意：在初始单纯形表其对偶问题应该是基可行解，对多数线性规划问题难实现。主要应用：灵敏度分析。23可编辑ppt练习:使用对偶单纯形法求解24可编辑pptCj-4-1-300CB基bx1x2x3x4x50x4-5-1-1-1100x5-3-11401Cj-zj-4-1-300