教案7灵敏度改

1、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种资源的影子价格是第i1 甲 乙可用量机械设备 1 28原材料A 4 016原材料B 0 412 X(3)=(4，2，0，0, 4)T， z3 =14cj23000CBXBbx1x2 x3x4x5203x1x

2、5x2442100001-2-3/2-1/81/8010-1400-3/2-1/80经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格2 产品资源 现有资源数钢材1 2100（吨）煤2 2180（吨）机时1 6240（小时）利润（万元）1 3x1x2x3x4x5 -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影子价格经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。

3、3影子价格的意义(1)影子价格客观地反映资源在系统内的稀缺程度。如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。(2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。(4)如果考虑扩大生产能力，应该从影子价格高的设备入手。46 对偶单纯形法保持对偶可行性，逐步改进主可行性，求解主问题。 当b有负分量，A中

4、有一明显初始对偶可行基(检验数均非正)，因而易得一初始解时，可用对偶单纯形法求解。 设B为一个基基本解X（0）为基本可行解的条件？B-1b0X（0）为最优解的条件？原原始可行性条件原始最优性条件令Y=CBB-1，代入原始最优性条件，YAC对偶可行性条件56例 用对偶单纯形法求解单纯形法大M 法剩余变量、人工变量 用（-1）乘不等式两边，再引入松弛变量。7cj -1 -4 0 -3 0 0CBXBb x1 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先选出基变量后选进基变量原问题，符合原始最优性条件

5、，但不可行cj -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 08cj -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 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*=-79例6

6、 用对偶单纯形法求解（P）101 - 4/3 - -1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1- 8/5 - - 22/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5 11对偶单纯形法的一个应用： 增加一个约束条件的分析 。 检查原最优解是否满足新的约束条件 满足，则原最优解仍为最优解，否则，2。2 将约束方程带到最优单纯形表中。max z =x+45x+24x 40123s.t. 例新增加一个条件 127 灵敏度分析 系数bi、cj 、aij 变化，最优解

7、的最优性、可行性是否变化？ 系数在什么范围内变化，最优解或最优性不变？ 如何求新的最优解？本节重点137.1 灵敏度分析的原理是最优解，则可行性条件最优性条件正则性 bi非基变量cj基变量cB增加新变量一个非基变量 系数aij的变化，要视aij对应的变量是基变量或非基变量而定。14XB=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 ，其他系数不变，这样最终

8、的单纯形表中原问题的解相应地变化为1、资源系数br的灵敏度变化分析15B-1的第r列进一步得，最终表中b列元素bbairir-D B-1b,0babririD+i=1，2，mi=1，2，miririrabba;/0-Diririrabba/0-D16x1, x5, x2是基变量，从而可得基B例：求第一章例题中当第二个约束条件b2变化范围b2。得到公式: 17cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-0-21/21/41/2-1/8010-1400-3/2-1/8018可得b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16由

9、公式知b2变化范围-8,16, 显然b2变化范围8,32 例题: 将上面例题进行实际应用。每台设备台时的影子价格为1.5元。若该厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方案。B=（x1 x5 x2)19将这个结果放到最终表中得解：先计算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 0cj-zj 0 0 -1.5 -0.125 020 表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。 最优解见下表 最优生产方案应改为

10、第一种产品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.7521（1）当cj是非基底变量xj的系数，检验数为或当cj变化cj后，检验数应要小于或等于零，即2、目标函数中价值系数C的变化22（2）当cr是基底变量xr的系数，即crCB，cr变化cr后，有aaaCAC B BABCABCrnrrrrBLLL),()0,0(21111D+=D+-最优解不变njacA)jcrjrjjL,2,1,=D-=s

11、(CBB1-23cr的变化范围 例8： 仍以第一章例1的最终表为例。设基变量x2的系数c2变化c2，在原最优解不变的条件下，确定c2的变化范围。 解：这时最终计算表为24cj2 3 000CBXBbx1x2x3x4x5203x1x5x24421000010-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之间变化，不影响原最优解。25cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj

12、00-5-15已知线性规划问题最优单纯形表练习1263 aij的变化分析(1). aij 为非基变量的系数只影响xj的检验数，从而影响最优性。 例: 第一章例1，增加一种新产品，它的技术系数是(2，6，3)T，利润系数是5。问该厂是否应生产该产品和生产多少？ 解：设新产品的产量为x3 (对于原最优解来说是非基变量)。因 故应生产产品。 x3进基27在最终表中的系数是： 原最终表成为： 28用单纯形法求解得： 29(2). aij为基变量系数基变化，影响最优性、可行性。 例: 第一章例1，若生产产品的工艺结构有改进，其技术系数变为（2， 5 ，2)T，利润系数为4，试分析对生产计划有什么影响？

13、解： 设产品产量为x1(产品产量在原最优解中是基变量)。计算 30将和所求系数填入原最终表的x1列位置，得 将x1的系数列向量变换为单位向量 31 上表中假如对偶可行，主不可行，则用对偶单纯形法求新解；假如主对偶均不可行，要加入人工变量，用单纯形法继续解。注意：例11 假设例10的产品的技术系数向量为 p1=（4，5，2），而每件获利仍为4元。试该厂应如何安排最优生产方案？323334练习2 在练习1中，如果新增加产品，其目标系数为100，消耗系数为（9，3.5） 是否应该生产该产品cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj0

14、0-5-15最优单纯形表35(1)求线性规划问题的最优解；(2)求对偶问题的最优解； (3)当b3= -150时最优基是否发生变化？为什么？ (4)求C2的灵敏度范围; (5)如果x3的系数由1，3，5变为1，3，2最优基是否改变？若改变求新的最优解 ;(6)假定新增决策变量x8，且p8=(2，5，3)，C8=4，原最优解是否改变？为什么？ 36线性规划综合例题 某工厂使用5种生产方式，生产A、B、C三种产品，有关每种方法的批产量数据如表1、资源消耗如表2。有一合同要求至少生产A110单位。 表1 每种方法的批产量 方法产品12345单价ABC3622164254110481054 方法产品12345单价工时机时成本/元01484119623011442178050-表2 资源消耗 1.若第2种生产方法的成本提高到21元，问是否改变最有解？ 2.现每工时的工资为3元，若加班，另附加费用1.5元