北京交通大学运筹学教案7灵敏度改.ppt

1、5 对偶问题的经济解释 影子价格,(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。,当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。,+yi*(bi+1),=Y*b+yi* =Z*+yi*,第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量,X(3)=(4，2，0，0, 4)T， z3 =14,经济意义：在其它条件不变的情况下， 单位资源变化所引起的目标函数的最优值的变化。,影子价格,X*=(30,35,0,50,0)T, Z*=135,y1*=3/4 y2*=0, y3*=1/4,经济意义：在其它条件不

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

3、法,保持对偶可行性，逐步改进主可行性，求解主问题。,当b有负分量，A中有一明显初始对偶可行基(检验数均非正)，因而易得一初始解时，可用对偶单纯形法求解。,设B为一个基,基本解,X（0）为基本可行解的条件？,B-1b0,X（0）为最优解的条件？,原,原始可行性条件,原始最优性条件,令Y=CBB-1，代入原始最优性条件，YAC,对偶可行性条件,例 用对偶单纯形法求解,单纯形法,大M 法,剩余变量、人工变量,用（-1）乘不等式两边，再引入松弛变量。,先选出基变量 后选进基变量,原问题，符合原始最优性条件，但不可行,最优解 X*=（7，0，4，0）T Z*=-7,例6 用对偶单纯形法求解,（P）,1

4、- 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 - - 2,2/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, , ,对偶单纯形法的一个应用： 增加一个约束条件的分析 。,检查原最优解是否满足新的约束条件 满足，则原最优解仍为最优解，否则，2。 2 将约束方程带到最优单纯形表中。,7 灵敏度分析,系数bi、cj 、aij 变化，最优解的最优性、可行性是否变化？,系数在什么范围内变化，最优解或最优性不变？,如何求新的最优解？,7

5、.1 灵敏度分析的原理,是最优解，则,可行性条件,基变量cB,增加新变量,系数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的灵敏度变化分析,B-1的第r列,x1, x5, x2是基变量，从而可得基B,例：求

6、第一章例题中当第二个约束条件b2变化范围b2。,可得 b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16 由公式知b2变化范围-8,16, 显然b2变化范围8,32,例题: 将上面例题进行实际应用。每台设备台时的影子价格为1.5元。若该厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方案。,B=（x1 x5 x2),将这个结果放到最终表中得,解：先计算B-1b,表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。 最优解见下表,最优生产方案应改为第一种产品4件，第二种产品3件，获利z=17元。,（1）当cj是非基底变量xj的系数，检验数

7、为,或,当cj变化cj后，检验数应要小于或等于零，即,2、目标函数中价值系数C的变化,（2）当cr是基底变量xr的系数，即crCB，cr变化cr后，有,最优解不变,cr的变化范围,例8： 仍以第一章例1的最终表为例。设基变量x2的系数c2变化c2，在原最优解不变的条件下，确定c2的变化范围。,解：这时最终计算表为,可见 c2-1.5/0.5; c2-0.125/(-0.125) 故c2的变化范围: -3c21 即x2的价值系数c2可在0,4之间变化，不影响原最优解。,已知线性规划问题,最优单纯形表,练习1,3 aij的变化分析,(1). aij 为非基变量的系数,只影响xj的检验数，从而影响最

8、优性。,例: 第一章例1，增加一种新产品，它的技术系数是(2，6，3)T，利润系数是5。问该厂是否应生产该产品和生产多少？,解：设新产品的产量为x3 (对于原最优解来说是非基变量)。因,故应生产产品。,x3进基,在最终表中的系数是：,原最终表成为：,用单纯形法求解得：,(2). aij为基变量系数,基变化，影响最优性、可行性。,例: 第一章例1，若生产产品的工艺结构有改进，其技术系数变为（2， 5 ，2)T，利润系数为4，试分析对生产计划有什么影响？,解： 设产品产量为x1(产品产量在原最优解中是基变量)。计算,将和所求系数填入原最终表的x1列位置，得,将x1的系数列向量变换为单位向量,上表中

9、假如对偶可行，主不可行，则用对偶单纯形法求新解；假如主对偶均不可行，要加入人工变量，用单纯形法继续解。,注意：,例11 假设例10的产品的技术系数向量为 p1=（4，5，2），而每件获利仍为4元。试该厂应如何安排最优生产方案？,练习2 在练习1中，如果新增加产品，其目标系数为100，消耗系数为（9，3.5） 是否应该生产该产品,例2-14 已知线性规划问题,其最优单纯形表为,现增加新约束 求新问题的最优解,解：增加约束后的新问题为,原问题的最优解为,带入新增加的约束,故X*不满足新增加的约束条件，因此引入松弛变量x7后，新增加的约束条件变为,将第1行的3倍，第3行的（-6）倍分别加到第4行上，

10、使基变量x1、 x5、 x3 、x7的系数列向量构成单位矩阵，即,得到下表,在表中 故当前解不是可行解，用对偶单纯形法求解，x7是换出变量，A4为主行又,p6是主列， 是主元素,新问题的最优解,要注意的是追加约束条件后，新问题的目标函数值总不会比原问题的目标函数值好（为什么）,线性规划综合例题,某工厂使用5种生产方式，生产A、B、C三种产品，有关每种方法的批产量数据如表1、资源消耗如表2。有一合同要求至少生产A110单位。,表1 每种方法的批产量,表2 资源消耗,列出利润最大化的线性规划模型,(1)求线性规划问题的最优解； (2)求对偶问题的最优解； (3)当b3= -150时最优基是否发生变

11、化？为什么？ (4)求C2的灵敏度范围; (5)如果x3的系数由1，3，5变为1，3，2最优基是否改变？若改变求新的最优解 ; (6)假定新增决策变量x8，且p8=(2，5，3)，C8=4，原最优解是否改变？为什么？,线性规划综合例题,某工厂使用5种生产方式，生产A、B、C三种产品，有关每种方法的批产量数据如表1、资源消耗如表2。有一合同要求至少生产A110单位。,表1 每种方法的批产量,表2 资源消耗,1.若第2种生产方法的成本提高到21元，问是否改变最有解？,2.现每工时的工资为3元，若加班，另附加费用1.5元/h，加班是否使利润增加？,3.若只要另付加班费0.3元/h，加班是否有利？如果有利，可加班多少小时？,4.若购置1台新机器，购价为30万元，每天可以增加8h，机器可以用5年，每年250工作日，问是否有利？,5.问增加3台新机器是否有利？,6.公司按合同每天至少供应110单位A，若变更合同减少供应量，是否有利？,7.第4种生产方法的成本要降低到什么程度才能增加利润？,8.若第2 种方法的批量不能超过20次，最优解有无变化？若不能超过15次呢？,求：（1）线性规划问题的最优解； （2）求对偶