3334线性规划的对偶和灵敏度分析ppt课件

1、3.3 影子价格影子价格对偶最优解的经济含义对偶最优解的经济含义 1、 对偶最优解的经济解释对偶最优解的经济解释“影子价格确切的定义是：一个线性规划对影子价格确切的定义是：一个线性规划对偶问题的最优解简称为偶问题的最优解简称为“对偶最优解对偶最优解”）。）。在经济上可以解释为约束条件所付出的代价。在经济上可以解释为约束条件所付出的代价。 看下面的线性规划看下面的线性规划 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2（8，0）k=6（0，4）k=012121212max23x +2x84x16. .4x12 x ,x0ZxxstQ24，2）Z=2*4+3*2=14当原问题

2、和对偶问题都取得最优解时，这当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，即一对线性规划对应的目标函数值相等，即有有 Zmax=CX*=2x*1+3x*2 =Wmin=y*b=8y*1+16y*2+12y*3=14 其中其中X*是原问题的最优解，是原问题的最优解，y*是对偶问题是对偶问题最优解。最优解。通过上面的例子可以看出：通过上面的例子可以看出：yi* 的值表示对第的值表示对第i种种资源的估价，它是针对具体问题而存在的一种资资源的估价，它是针对具体问题而存在的一种资源的特殊价格，称为源的特殊价格，称为“影子价格影子价格”。cj23000CBXBbx1x2x3x4x5

3、2x141001/40-0 x5400-21/21-3x22011/2 -1/80-cj-zj00-3/2 -1/80i即有即有 X*=(x1,x2)=(4,2)， Y*=(y1,y2,y3)=(3/2,1/8,0) 若原材料供应量能增加一个单位，即右端常若原材料供应量能增加一个单位，即右端常数向量数向量b=(b1,b2,b3)T=(8,16,12)Tb=(b1,b2,b3)T=(8,16,12)T中的中的b1b1从从8 8个个单位增加到单位增加到9 9个单位，则目标函数值的变化量为个单位，则目标函数值的变化量为（9y*1+16y*2+12y*3)-(8y*1+16y*2+12y*3)=y*1

4、=3/2 说明目标函数值的增加一个单位，是因为放说明目标函数值的增加一个单位，是因为放宽一个约束条件所产生的附加贡献。宽一个约束条件所产生的附加贡献。 就是说，影子价格确定了为得到一个附加就是说，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。单位的约束因素所应花费的成本上限。 所以，所以，yi*的经济意义是在其他条件不变的情的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数最优况下，单位资源变化所引起的目标函数最优值的变化。值的变化。 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2（8，0）C=6（0，4）C=012121212m ax23x

5、 +2x84x16. .4x12 x ,x0Zxxs tQ24，2）Q2（4, 2.5）Z=2*4+3*2=14Z=2*4+3*2.5=15.5Q2”（4.25, 1.875）Z=2*4.25+3*1.875=14.125Q2(1.5，3.25)Z=2*1.5+3*3.25=12.75u影子价格是对现有资源实现最大效益时的一种估价影子价格是对现有资源实现最大效益时的一种估价u 企业可以根据现有资源的影子价格，对资源的企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设租

6、，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。考虑买进该设备，否则不宜买进。u影子价格表明资源增加对总效益产生的影响影子价格表明资源增加对总效益产生的影响u 如果为了扩大生产能力，考虑增加设备，就应如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。努力，获得较大的整体效益。3

7、.4 对偶单纯形法对偶单纯形法 一、什么是对偶单纯形法？一、什么是对偶单纯形法？ 对偶单纯形法是应用对偶原理对偶单纯形法是应用对偶原理求解原始线性规划的一种方法求解原始线性规划的一种方法在原始问题的单纯形表格上进在原始问题的单纯形表格上进行对偶处理。行对偶处理。 留意：不是解对偶问题的单纯形留意：不是解对偶问题的单纯形法！法！ 二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想 1、对、对“单纯形法求解过程认识的提升单纯形法求解过程认识的提升 从更高的层次理解单纯形法从更高的层次理解单纯形法 初始可行基对应一个初始基可行解）初始可行基对应一个初始基可行解） 迭代迭代另一个可行基对应另一个基可

8、行解），直至另一个可行基对应另一个基可行解），直至所有检验数所有检验数0为止。为止。 所有检验数所有检验数0意味着什么？意味着什么？ -1BCC B A0()()BN-1BC BCB0CNNB-1-1BBCCC B BB0CN00NYAC以上分析过程说明原问题的最优基也是对偶问以上分析过程说明原问题的最优基也是对偶问题的可行基。换言之，当原问题的基题的可行基。换言之，当原问题的基B既是原既是原问题的可行基又是对偶问题的可行基时，问题的可行基又是对偶问题的可行基时，B成成为原问题的最优基。为原问题的最优基。定理定理2-5 基基B是线性规划的最优基的充要条件是线性规划的最优基的充要条件是，是，B是

9、可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。单纯形法的求解过程就是：在保持原始可行单纯形法的求解过程就是：在保持原始可行的前提下的前提下(b列保持列保持0)，通过逐步迭代实现对，通过逐步迭代实现对偶可行偶可行(检验数行检验数行0)。 2、 对偶单纯形法思想：对偶单纯形法思想： 换个角度考虑换个角度考虑LP求解过程：保持对偶可行求解过程：保持对偶可行的前提下检验数行保持的前提下检验数行保持0） ，通过逐步，通过逐步迭代实现原始可行迭代实现原始可行b列列0）。）。 原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 0所有所有 0最优性检验最优性检验所有所有 0

10、？所有所有 0？换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解原始基本解的进化的进化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）ibj对 偶 单 纯 形 法对 偶 单 纯 形 法ibj3、计算思路对于、计算思路对于MAX问题）：问题）： 建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。b列列0已得最优解已得最优解至少一个元素至

11、少一个元素0,转下步转下步检验数全部检验数全部0（非基变量检验（非基变量检验数数0） 基变换：基变换： 先确定换出变量先确定换出变量解答列中的负元素对应的基变量出基，解答列中的负元素对应的基变量出基，即即出基，则选lliiixbBbBbB,)(0)()(min111相应的行为主元行。相应的行为主元行。然后确定换入变量然后确定换入变量原则是：在保持对偶原则是：在保持对偶可行的前提下，减少原始问题的不可行性。可行的前提下，减少原始问题的不可行性。假设假设 0minlkkkljljjjjazcaazc(最小比值原则最小比值原则),则选则选 为换入变量为换入变量 , 相相应的列为主元列应的列为主元列

12、, 主元行和主元列交叉处主元行和主元列交叉处的元素的元素 为主元素。为主元素。kxlka假设假设 ,要计算最要计算最小比值吗？为什么？小比值吗？为什么？0lja 按主元素进行换基迭代旋转运算、枢运算），将按主元素进行换基迭代旋转运算、枢运算），将主元素变成主元素变成1，主元列变成单位向量，得到新的单纯形表。，主元列变成单位向量，得到新的单纯形表。 循环以上步骤，直至求出最优解。循环以上步骤，直至求出最优解。例例3.9 用对偶单纯形法求解用对偶单纯形法求解LP： 化为标准型化为标准型 将两个等式约束两边分别乘以将两个等式约束两边分别乘以-1，得，得0,332232. .653min4321432

13、143214321xxxxxxxxxxxxtsxxxxw0,332232. .653max65432164321543214321xxxxxxxxxxxxxxxxtsxxxxw以此形式进行列表求解，满足对偶单纯形以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：法的基本条件，具体如下：0,332232. .6532max62164321543214321xxxxxxxxxxxxxtsxxxxwCj -2 -3 -5 -6 0 0 CB XBb x1x2x3 x4 x5 x60 x5 -2 -1 -2 -3 -1 1 0 0 x6 (-3) -2 1 -1 3 0 1 -2 -3 -5

14、 -6 0 0 （1） 5jCj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 (-1/2) 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 0 -4 -4 -9 0 -1 (8/5) 8/5 18/5 2jCj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 0 0 0 -5 -8/5 -1/5 j因此，最优解为因此，最优解为X*=(8/5

15、,1/5,0,0,0,0)T，最优值最优值*=21/5。练习练习用对偶单纯形法求解用对偶单纯形法求解LP： 0, 037342. .932121212121yyyyyyyyt syyMinW 化为化为标准型标准型 0,37342. .935152142132121yyyyyyyyyyyt syyMaxZ将三个等式约束两边分别乘以将三个等式约束两边分别乘以-1，然后，然后列表求解如下：列表求解如下： -3/-1 -9/-1 - - - 比比 值值 -3 -9 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y4 y5 0 0

16、0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB - -6/-3 -3/-1 - - 比比 值值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB（1初始解可以是非可行解，当检验数都初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要为负数时，就可以进行基的变换，这时