运筹学：教案7_灵敏度（改）

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 30,24061802210023max2121212121xxxxxxxxxxZx1x2x3x4x5 -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、义：经济意义：在其它条件不变的情况下，在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。单位资源变化所引起的目标函数的最优值的变化。影子价格的意义 (1)影子价格客观地反映资源在系统内的稀缺程度。 如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。 (2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。 (3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它

5、是一种动态价格。 (4)如果考虑扩大生产能力，应该从影子价格高的设备入手。6 对偶单纯形法对偶单纯形法保持对偶可行性，保持对偶可行性，逐步改进主可行性逐步改进主可行性，求解主问题。，求解主问题。 当当b有负分量，有负分量，A中有一明显初始对偶可行中有一明显初始对偶可行基基(检验数均非正检验数均非正)，因而易得一初始解时，可用，因而易得一初始解时，可用对偶单纯形法求解。对偶单纯形法求解。 0 XbAXCXZmax设设B为一个基为一个基 010bBX)(基本解基本解X（0）为基本可行为基本可行解的条件？解的条件？B-1b0X（0）为最优解的为最优解的条件？条件？01 ABCCB原原原始可行性条件原

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

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

8、- 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 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2

9、 -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,43232432min321321321321xxxxxxxxxxxxw（P）单单纯纯形形表表：1 - 4/3 - -1 0

10、 -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 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 - -3

11、 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 对偶单纯形法的一个应用：对偶单纯形法的一个应用： 增加一个约束条件的分析增加一个约束条件的分析 。 1 检查原最优解是否满足新的约束条件 满足，则原最优解仍为最优解，否则，2。2 将约束方程带到最优单纯形表中。max z =x +45x +24x 4040123s.t. 0,120233

12、10032 321321321xxxxxxxxx例新增加一个条件 151x7 灵敏度分析灵敏度分析 系数系数bi、cj 、aij 变化，最优解的最变化，最优解的最优性、可行性是否变化？优性、可行性是否变化？ 系数在什么范围内变化，最优解系数在什么范围内变化，最优解或最优性不变？或最优性不变？ 如何求新的最优解？如何求新的最优解？本本节节重重点点7.1 灵敏度分析的原理灵敏度分析的原理SNBXXXX是最优解，则是最优解，则000111BCNBCCbBBBN可行性条件可行性条件最优性条件最优性条件正则性 bi非基变量非基变量cj基变量基变量cB增加新变量增加新变量一个非基变量一个非基变量 系数系数

13、aij的变化，要视的变化，要视aij对应的变量是基变量对应的变量是基变量或非基变量而定。或非基变量而定。XB=B-1(b+b)，其中b=(0, br ,0,0)T只要XB0，最终表中检验数不变（b变化，不影响检验数），则最优性不变，但最优解的值发生变化, XB成为新的最优解.B-1(b+b)= B-1b+ B-1b0新的最优解允许范围是:当某一个资源系数br 发生变化，亦即br= br +br ，其他系数不变，这样最终的单纯形表中原问题的解相应地变化为1、资源系数资源系数br的灵敏度变化分析的灵敏度变化分析mrirrrrmrrirrrraaabbabababB11100B-1的第r列进一步得，

14、最终表中 b 列元素bbairir B-1b, 0babririi=1，2，mi=1，2，miririrabba;/0iririrabba/0 x1, x5, x2是基变量，从而可得基B1210010160100480012154321bxxxxx例：求第一章例题中当第二个约束条件b2变化范围b2。得到公式: 0min0maxiriririririaabbaabcj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-0-21/21/41/2-1/8010-1400-3/2 -1/80可得b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16

15、由公式知b2变化范围-8,16, 显然b2变化范围8,32000125. 05 . 025. 0244002211bbBbB 例题: 将上面例题进行实际应用。每台设备台时的影子价格为1.5元。若该厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方案。B=（x1 x5 x2)410004201B2800040125.05 .015 .02025.001bB将这个结果放到最终表中得解：先计算B-1b 2 3 0 0 0 cj203x1x2x54+04-82+2CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 -2 0.5 10 1 0.5 -0.125 0c

16、j-zj 0 0 -1.5 -0.125 0 表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。 最优解见下表 最优生产方案应改为第一种产品4件，第二种产品3件，获利z=17元。 2 3 0 0 0 cj203x1x2x3423CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 1 -0.25 -050 1 0 0 0.25cj-zj 0 0 0 -0.5 -0.75（1）当cj是非基底变量xj的系数，检验数为mijijjjjBjjyacPBCc11或当cj变化cj后，检验数应要小于或等于零，即jjjjjjjjjBjjjccYPcYPccPBCcc012、目标函

17、数中价值系数、目标函数中价值系数C的变化的变化（2）当cr是基底变量xr的系数，即crCB，cr变化cr后，有aaaCAC B BABCABCrnrrrrB),()0 , 0(21111最优解不变0j为非基变量jacaacarjjrrjrjjrrj, 0;, 0njacA)jcrjrjj, 2 , 1,(CBB1cr的变化范围0min0maxrjrjjjrrjrjjjaacaa 例8： 仍以第一章例1的最终表为例。设基变量x2的系数c2变化c2，在原最优解不变的条件下，确定c2的变化范围。 解：这时最终计算表为cj2 3 000CBXBbx1x2x3x4x5203x1x5x2442100001

18、0-20.50.250.5-0.125010cj-zj00-1.5-0.1250 可见c2-1.5/0.5; c2-0.125/(-0.125) 故c2的变化范围: -3c21即x2的价值系数c2可在0,4之间变化，不影响原最优解。02,1502121202314xxxxxx230150 xxzMaxcj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj00-5-15已知线性规划问题最优单纯形表练习1025. 13) 6 (2 0) 0.125 5 . 1 (5PBCcT31B33 3 aij的变化分析的变化分析(1). aij 为非基变

19、量的系数为非基变量的系数只影响只影响xj的检验数，从而影响最优性。的检验数，从而影响最优性。 例例: 第一章例第一章例1，增加一种新产品，增加一种新产品，它的技术系，它的技术系数是数是(2，6，3)T，利润系数是，利润系数是5。问该厂是否应生产问该厂是否应生产该产品和生产多少？该产品和生产多少？ 解：设新产品解：设新产品的产量为的产量为x3 (对于原最优解来说是对于原最优解来说是非基变量非基变量)。因。因 故应生产产品故应生产产品。 x3进基进基25.02 5.1 3620 0.125 0.51 0.5 20 0.25 0 31PB cj 2 3 0 0 0 5 CB XB b x1 x2 x

20、3 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 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-

21、 -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，若生产产品，若生产产品的工艺结构有的工艺结构有改进，其技术系数变为改进，其技术系数变为（2， 5 ，2)T，利润系数，利润系数

22、为为4，试分析对生产计划有什么影响？，试分析对生产计划有什么影响？ 解：解： 设产品设产品产量为产量为x1(产品产品产量在原最优解产量在原最优解中是基变量中是基变量)。计算。计算 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 4 4 2 1.25 0.5 0.375 0 0 1 0 - -2 0.5 0.25 0.5 0.125 0 1 0 cj- -zj 0.375 0 - -1.5 - -0.125 0 CB XB b x1 x2 x3 x4 x5 4 0 3 1x x5 x2 3.2 2.4 0.8 1 0 0 0 0 1 0 - -2 0.5 0.2 0.

23、4 - -0.2 0 1 0 cj- -zj 0 0 - -1.5 - -0.2 0 得到231.x* ，802.x* ， 215.z* 将和所求系数填入原最终表的将和所求系数填入原最终表的x1列位置，得列位置，得 1x1x将将x1的系数列向量变换为单位向量的系数列向量变换为单位向量 上表中假如对偶可行，主不可行，则用对上表中假如对偶可行，主不可行，则用对偶单纯形法求新解；假如主对偶均不可行，要加偶单纯形法求新解；假如主对偶均不可行，要加入人工变量，用单纯形法继续解。入人工变量，用单纯形法继续解。注意：注意：例例11 假设例假设例10的产品的产品的技术系数向量为的技术系数向量为 p1=（4，5

24、，2），而每件获利仍为），而每件获利仍为4元。试该厂应如何安元。试该厂应如何安排最优生产方案？排最优生产方案？练习2 在练习1中，如果新增加产品，其目标系数为100，消耗系数为（9，3.5） 是否应该生产该产品cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj00-5-15最优单纯形表4433251 xxxxzMax04,3,2,11000433524131200443324158004232312xxxxxxxxxxxxxxxx(1)求线性规划问题的最优解；(2)求对偶问题的最优解； (3)当b3= -150时最优基是否发生变化？为什么？ (4)求C2的灵敏度范围; (5)如果x3的系数由1，3，5变为1，3，2最优基是否改变？若改变求新的最优解 ;(6)假定新增决策变量x8，且