运筹学课件对偶问题的经济解释—影子价格

1、5 5 对偶问题的经济解释对偶问题的经济解释 影子价格影子价格 (P)的最终单纯形表中松弛变量的检验数对应的最终单纯形表中松弛变量的检验数对应(D)的最优解。的最优解。 当某约束条件的右端常数增加一个单位时当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。最优值增加的数量。Z*=CX*=Y*b =(y1*,y2*, ,ym*)b1b2bm=y1*b1+y2*b2+ym*bm当某个右端常数当某个右端常数bi bi+1时时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第第I种资源的影子价种

2、资源的影子价格是第格是第i个约束条件个约束条件的右端常数增加一的右端常数增加一个单位时，目标函个单位时，目标函数增加的数量数增加的数量 甲甲 乙乙可用量可用量机械设备机械设备 1 28原材料原材料A 4 016原材料原材料B 0 412 X X(3)(3)=(4=(4，2 2，0 0，0, 4)0, 4)T T， z z3 3 =14=14cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-2-3/2-1/81/8010-1400-3/2 -1/800125051321 *,.,.yyy经济意义：经济意义：在其它条件在其它条件不变的情况不变的情况下，下，单位资源

3、变单位资源变化所引起的化所引起的目标函数的目标函数的最优值的变最优值的变化。化。影子价格影子价格 产品产品资源资源 现有资源数现有资源数钢材钢材1 2100（吨）（吨）煤煤2 2180（吨）（吨）机时机时1 6240（小时）（小时）利润（万元）利润（万元）1 302406180210032121212121 xxxxxxxxxxZ,maxx1x2x3x4x5 -zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T, Z*=135y1*=3/4y2*=0,y3*=1/4影子价格影子价格经济意义

4、：经济意义：在其它条件不变的情况下，在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。单位资源变化所引起的目标函数的最优值的变化。6 对偶单纯形法对偶单纯形法保持对偶可行性，保持对偶可行性，逐步改进主可行性逐步改进主可行性，求解主问题。，求解主问题。 当当b有负分量，有负分量，A中有一明显初始对偶可行中有一明显初始对偶可行基基(检验数均非正检验数均非正)，因而易得一初始解时，可用，因而易得一初始解时，可用对偶单纯形法求解。对偶单纯形法求解。 0 XbAXCXZmax设设B为一个基为一个基 010bBX)(基本解基本解X（0）为基本可行为基本可行解的条件？解的条件？B-1b0X

5、（0）为最优解的为最优解的条件？条件？01 ABCCB原原原始可行性条件原始可行性条件原始最优性条件原始最优性条件令令Y=CBB-1，代入原始最优性条件，代入原始最优性条件，YAC无符号限制无符号限制YCYAYbW min对偶可行性条件对偶可行性条件计算步骤：计算步骤： 10 求初始基解，其检验数均非正。求初始基解，其检验数均非正。 20 计算计算liibbmin ，若，若 bl 0，则已得到最优解，结束；，则已得到最优解，结束；否则第否则第 l 行的基变量为换出变量。行的基变量为换出变量。 30 若若 alj 0 （ j） ，则无可行解，结束；否则计算，则无可行解，结束；否则计算 lkklj

6、ljjjaaamin 0 ，xk 为换入变量为换入变量 40 以以 alk 为主元素作旋转运算，为主元素作旋转运算，xk 取代原第取代原第 l 行基变行基变量，返回量，返回 20。 例例 用对偶单纯形法求解用对偶单纯形法求解 43210242323443214321421,max jxxxxxxxxxxxxZj单纯形法单纯形法大大M 法法 621024232346432154321421,max jxxxxxxxxxxxxxxZj剩余变量、剩余变量、人工变量人工变量 用（用（-1）乘不等式两边，再引入松弛变量。）乘不等式两边，再引入松弛变量。cj -1 -4 0 -3 0 0CBXBb x1

7、x2 x3 x4 x5 x600 x5x6-3-2 -1 -2 1 - 1 1 0 2 1 -4 -1 0 10 -1 -4 0 -3 0 0先选出基变量先选出基变量后选进基变量后选进基变量原问题，原问题，符合原始符合原始最优性条最优性条件，但不件，但不可行可行1132411 ,mincj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1

8、 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0-10 x1x374 1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 0 -1/2 0 -1/2 -2 -1/2最优解最优解X*=（7，0，4，0）TZ*=-7解解： 先先将将这这问问题题化化成成下下列列形形式式， 以以便便得得到到对对偶偶问问题题的的初初始始可可行行基基 （P）5210 4 3 2 3 2 43253214321321,j ,xxxxxxxxxxxxzmaxj 例例6 用对偶单纯形法求解用对偶单纯形法求解0 x,x,x4x3xx23xx2xx4x3x2wmin32

9、1321321321（P）单单纯纯形形表表：1 - 4/3 - -1 0 -5/2 1/2 1 -1/2-1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1 0 -4 -1 0 -1- 8/5 - - 22/5 0 1 -1/5 -2/5 1/5 2/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/511/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5 0 0 -3/5 -8/5 -1/5cj - -2 - -3 3 - -4 0 0 C

10、B XB b x1 x2 x3 x4 x5 0 0 x4 x5 - -3 3 - -4 4 - -1 - -2 2 - -2 2 1 - -1 1 - -3 3 1 0 0 0 1 cj- -zj - -2 2 - -3 3 - -4 4 0 0 0 0 - -2 2 x4 x1 cj- -zj - -3 - -2 2 x2 x1 cj- -zj T),/,/(X00052511 7 灵敏度分灵敏度分析析 系数系数bi、cj 、aij 变化，最优解的最变化，最优解的最优性、可行性是否变化？优性、可行性是否变化？ 系数在什么范围内变化，最优解系数在什么范围内变化，最优解或最优性不变？或最优性不变

11、？ 如何求新的最优解？如何求新的最优解？本本节节重重点点7.1 灵敏度分析的原理灵敏度分析的原理SNBXXXX是最优解，则是最优解，则0BC0NBCC0bB1B1BN1可行性条件可行性条件最优性条件最优性条件正则性 bi非基变量非基变量cj基变量基变量cB增加新变量增加新变量一个非基变量一个非基变量 系数系数aij的变化，要视的变化，要视aij对应的变量是基变量对应的变量是基变量或非基变量而定。或非基变量而定。7.2 br变化的分析rrrrbbbb影响解的可行性，影响解的可行性，只要只要B-1(b+b) 0，解的可行性不变，最优性也不变。，解的可行性不变，最优性也不变。0b0BbBbbBr11

12、1rr11b)B(bB (B-1)r 是是B-1的第的第r列列，解上述不等式，求得保持，解上述不等式，求得保持可行性不变的可行性不变的br的范围。的范围。0 000125050 250 2440 0 2211b.bBbB 例例: 求第一章例求第一章例1中的第二个约束条件中的第二个约束条件b2（=16）的变）的变化范围化范围 b2时，计算时，计算可得可得 b2 -4/0.25=-16 b2 -4/0.5=-8 b2 2/0.125=16所以，所以， b2的变化范围是的变化范围是-8，16；b2的变化范围是的变化范围是8，32。 c cj j 2 3 0 0 0 0 CB XB b x1 x2 x

13、3 x4 x x5 5 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 0 - -2 2 1/2 1/4 1/2 - -1 1/ /8 8 0 0 1 0 cj- -zj 0 0 - -1 1. .5 5 - -1 1/ /8 8 0 4442 80 2440040 0.125 0.51 0.5 20 250 024411.bBbBb 例例: 第一章例第一章例1中，若设备增加中，若设备增加4台时，求新的最台时，求新的最优生产计划。优生产计划。计算计算:cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 - -4 4 4

14、 1 0 0 0 0 1 0 - -2 2 0.5 0.25 0.5 - -0.125 0 0 1 0 cj- -zj 0 0 - -1.5 - -0.125 0 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x3 x2 4 2 3 1 0 0 0 0 1 0 1 0 0.25 - -0.25 0 0 0 - -0.5 0.25 cj- -zj 0 0 0 0 - -0.5 - -0.75 得表：得表：用用对偶单纯形法对偶单纯形法得：得： X*=(4，3，2，0，0)，z*=17 rBrrPBCc1 01 rrrBrrrcPBCcc ， 即rrc

15、 时，最优性不变。 7.3 cr 变化的灵敏度变化的灵敏度 分析分析cr cr + cr不影响解的可行性，影响最优性。不影响解的可行性，影响最优性。(1) cr 为为非非基变量的系数基变量的系数 000 111 jrjBjjBBjjPB),c,(PBCcPB)CC(c 即 0 rjrjac (j =1，n) 时最优性不变。 cj23 3+ + c2000CB XBbx1x2x3x4x5203+ c2x1x5x24421000010-4-40.50.250.5-0-0.1250 010cj- -zj00-1-1.5 5- - c2/2 c2/8-1/8-1/80(2) cr 为基变量的系数为基变

16、量的系数 例：第一章例例：第一章例1中中c2变化变化 c2，问，问 c2在什么范围内变化时最在什么范围内变化时最优解不变。优解不变。 解：解： 对所有的非基变量对所有的非基变量由 0818 025122/c/c. cj23 3+ + c2000CB XBbx1x2x3x4x5203+ c2x1x5x24421000010-4-40.50.250.5-0-0.1250 010cj- -zj00-1-1.5 5- - c2/2 c2/8-1/8-1/80 当给定当给定 c2，要求新的最优解时，先求新的检验数，要求新的最优解时，先求新的检验数，再用单纯形法迭代。再用单纯形法迭代。 解得：解得： -3

17、 c2 1 025. 13) 6 (2 0) 0.125 5 . 1 (5PBCcT31B33 7.4 aij变化的灵敏度分析变化的灵敏度分析(1). aij 为非基变量的系数为非基变量的系数只影响只影响xj的检验数，从而影响最优性。的检验数，从而影响最优性。 例例: 第一章例第一章例1，增加一种新产品，增加一种新产品，它的技术系，它的技术系数是数是(2，6，3)T，利润系数是，利润系数是5。问该厂是否应生产问该厂是否应生产该产品和生产多少？该产品和生产多少？ 解：设新产品解：设新产品的产量为的产量为x3 (对于原最优解来说是对于原最优解来说是非基变量非基变量)。因。因 故应生产产品故应生产产

18、品。 x3进基进基 2502 51 6220 0.125 0.51 0.5 20 0.25 0 31.PB cj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x3 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 0 - -2 0.5 1/4 1/2 -1/8 0 1 0 1.5 2 0.25 cj- -zj 0 0 - -1.5 - -1/8 0 1.25 在最终表中的系数是：在最终表中的系数是： 原最终表成为：原最终表成为： 3xcj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x3 2 0 3 x1 3x x2 1 2

19、1.5 1 0 0 0 0 1 1.5 - -1 0.75 - -0.125 0.25 - -0.1875 - -0.75 0.5 - -0.125 0 1 0 cj- -zj 0 0 - -0.25 - -0.4375 - -0.625 0 用单纯形法求解得：用单纯形法求解得： 3x5 .16*z, 2*3x, 5 . 1*2x, 1*1x 0.3752) 5 0)(2 0.125 514T111 .(PBCcB 375050 251 2520 0.125 0.51 0.5 20 0.25 011. -PB (2). aij为基变量系数为基变量系数基变化基变化，影响最优性、可行性。，影响最优性、可行性。 例例: 第一章例第一章例1，若生产产品，若生产产品的工艺结构有的工艺结构有改进，其技术系数变为