文档介绍：运筹学—线性规划与目标规划
第二章对偶问题与灵敏度分析
Duality Theory and Sensitivity Analysis
对偶问题的经济解释—影子价格
影子价格(Shadow Price)是一个向量,它的分量表示最优目标值随相应资源数量变化的变化率。
若x*,y* 分别为(LP)和(DP)的最优解,那么, cx* = y*b 。
根据Z * = y*b = b1y1*+b2y2*++bmym*
可知Z / bi = yi* 。
其中yi* 表示 bi 变化1个单位对目标Z 产生的影响,称 yi* 为 bi的影子价格。
注意:若 B 是最优基,
y* = cB B-1 为影子价格向量。
影子价格的经济含义
(1)影子价格是对现有资源实现最大效益时的一种估价。
企业可以根据现有资源的影子价格,对资源的使用有两种考虑:
第一,是否将设备用于外加工或出租,若租费高于某设备的影子价格,可考虑出租该设备,否则不宜出租。
第二,是否将投资用于购买设备,以扩大生产能力,若市价低于某设备的影子价格,可考虑买进该设备,否则不宜买进。
(2) 影子价格表明资源增加对总效益产生的影响。
根据结论“设x0和y0分别为原规划(P)和对偶规划(D)的可行解,当cx0=y0b时,x0、y0分别是两个问题的最优解”,可知,在最优解的情况下,有关系:
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力,考虑增加设备,就应该从影子价格高的设备入手。这样可以用较少的局部努力,获得较大的整体效益。
需要指出,影子价格不是固定不变的,当约束条件、产品利润等发生变化时,有可能使影子价格发生变化。
另外,影子价格的经济含义,是指资源在一定范围内增加时的情况,当某种资源的增加超过了这个“一定的范围”时,总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题在灵敏度分析一节中讨论。
对偶单纯形法的基本思想
对偶单纯形法的基本思想是:从原规划的一个基本解出发,此基本解不一定可行,但它对应着一个对偶可行解(检验数非正),所以也可以说是从一个对偶可行解出发;
然后检验原规划的基本解是否可行,即是否有负的分量,如果有小于零的分量,则进行迭代,求另一个基本解,此基本解对应着另一个对偶可行解(检验数非正)。
§ 对偶单纯形法
如果得到的基本解的分量皆非负则该基本解为最优解。也就是说,对偶单纯形法在迭代过程中始终保持对偶解的可行性(即检验数非正),使原规划的基本解由不可行逐步变为可行,当同时得到对偶规划与原规划的可行解时,便得到原规划的最优解。
对偶单纯形法在什么情况下使用:
应用前提:有一个解,其对应的基满足:
①单纯形表的检验数行全部非正
(对偶可行解);
②变量取值可有负数(非可行解)。
注:对偶单纯形法是通过矩阵行变换运算,使所有相应变量取值均为非负数, 即得到最优单纯形表。