Chapter 3.3-3.4 线性规划的对偶和灵敏度分析.ppt

1、3.3 影子价格 对偶最优解的经济含义,1、 对偶最优解的经济解释,“影子价格”确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。在经济上可以解释为约束条件所付出的代价。,看下面的线性规划,（8，0）,k=6,（0，4）,k=0,Q2（4，2）,Z=2*4+3*2=14,当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，即有 Zmax=CX*=2x*1+3x*2,=Wmin=y*b=8y*1+16y*2+12y*3=14,其中X*是原问题的最优解，y*是对偶问题最优解。,通过上面的例子可以看出：yi* 的值表示对第i种资源的估价，它是针对具体问题而存在的一

2、种资源的特殊价格，称为“影子价格”。,即有,X*=(x1,x2)=(4,2)，,Y*=(y1,y2,y3)=(3/2,1/8,0),若原材料供应量能增加一个单位，即右端常数向量b=(b1,b2,b3)T=(8,16,12)T中的b1从8个单位增加到9个单位，则目标函数值的变化量为,（9y*1+16y*2+12y*3)-(8y*1+16y*2+12y*3)=y*1=3/2,说明目标函数值的增加一个单位，是因为放宽一个约束条件所产生的附加贡献。 就是说，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。,所以，yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数最优值

3、的变化。,（8，0）,C=6,（0，4）,C=0,Q2（4，2）,Q2（4, 2.5）,Z=2*4+3*2=14,Z=2*4+3*2.5=15.5,Q2”（4.25, 1.875）,Z=2*4.25+3*1.875=14.125,Q2(1.5，3.25),Z=2*1.5+3*3.25=12.75,影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。

4、 影子价格表明资源增加对总效益产生的影响 如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,3.4 对偶单纯形法 一、什么是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！,二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提升 从更高的层次理解单纯形法 初始可行基（对应一个初始基可行解） 迭代另一个可行基（对应另一个基可行解），直至所有检验数0为止。,所有检验数0意味着什么？,以上分析过程说明原问题的最优基也是对偶问题的可行基。

5、换言之，当原问题的基B既是原问题的可行基又是对偶问题的可行基时，B成为原问题的最优基。 定理2-5 基B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。,单纯形法的求解过程就是：在保持原始可行的前提下(b列保持0)，通过逐步迭代实现对偶可行(检验数行0)。,2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持0） ，通过逐步迭代实现原始可行（b列0）。,对偶单纯形法,3、计算思路（对于MAX问题）： 建立初始单纯形表，计算检验数行。,检验数全部0 （非基变量检验数0）, 基变换： 先确定换出变量解答列中的负元素对应的基变量出基，即,相应的行为主

6、元行。,然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。 如果,(最小比值原则),则选 为换入变量 , 相应的列为主元列 , 主元行和主元列交叉处的元素 为主元素。,若 ,要计算最小比值吗？为什么？,按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。 循环以上步骤，直至求出最优解。,例3.9 用对偶单纯形法求解LP：,化为标准型 ,将两个等式约束两边分别乘以-1，得,以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：,因此，最优解为X*=(8/5,1/5,0,0,0,0)T， 最优值*=21/5。,练习用对偶单纯形法求解LP：,化为 标准型 ,将三个等式约束两边分别乘以-1，然后 列表求解如下：,最优解是Y*=（5/3，1/3，0，0，1）T， 目标函数最优值为Wmin=-Zmax=8,（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 （2）当变量多于约束条件时，用对偶单纯形法计算可以减少计算工