1.8 灵敏度分析灵敏度分析CBB-1b C - CBB-1 AB-1 b B-1 A原始数据原始数据A A，b b，C CA=(A=(P1 P2 Pn ) )公式公式 Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj 1 A= A= B-1 A Pj = =B-1 Pj 标准型标准型 maxZ=CX AX = =b X 0(1)、参数、参数A，b，C在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？2例：例： A B C 备用资源备用资源 甲甲 1 1 1 12 乙乙 1 2 2 20 利润利润 5 8 6 产品产品原料原料问：如何安排产品产量，可获最大利润？问：如何安排产品产量，可获最大利润？3maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解解4 5 8 6 0 0 X1 X2 X3 X4 X5CB XB 0 5 8 6 0 0 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1 CB XB 84 0 0 -2 -2 -3 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 15(一一)、目标函数系数、目标函数系数Cj的灵敏度分析的灵敏度分析(1)、非基变量系数、非基变量系数Cj Cj 改变，改变， j仍仍 0 0 时对最优方案无影响。时对最优方案无影响。例中例中C3改变改变3 = C3 -CBB-1 P3 =C3 -(5 8) =C3 -8 0 0 2 -1-1 112即即C3 8 6 C3改为改为10，3 =20 CB XB 84 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -1 1 XB 100 0 -2 0 0 -5 5 X1 4 1 0 0 2 -110 X3 8 0 1 1 -1 1 7(2)、基变量系数、基变量系数Cj Cj 改变，改变， 全部全部j 0 0，最优方案不变。最优方案不变。例中例中C1改变改变A = C -CBB-1 A =(C1 ,8,6,0,0 ) -(C1 8) 1 0 0 2 -10 1 1 -1 1=(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 88 C1改变改变 C1=10，5 =20 ,换基换基 XB 104 0 0 -2 -12 2 10 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 120 0 -2 -4 -10 0 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 9(二二)、约束条件右端项、约束条件右端项 bj 的灵敏度分析的灵敏度分析(1)、bj 改变，改变， B-1 b仍仍 0时，最优方案不变。时，最优方案不变。例中例中b1改变改变2 -1-1 1b12010 b1 20 B-1 b= 02b1 -20 0-b1+20 010(2)、 b1改变改变, b1=30 ，CB XB 120 0 0 -2 -2 -3 5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 100 0 -2 -4 0 -5 5 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1 2 -1-1 13020B-1 b= 40-1011(三三)、添加新变量的灵敏度分析、添加新变量的灵敏度分析例例 对于新产品对于新产品D D，已知已知1 1个单位个单位D D要消耗要消耗 甲：甲：3 3 乙：乙：2 2 可以得利润可以得利润1010问：投产产品问：投产产品D D是否有利？是否有利？ 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得得 C6 12（2 2） C6 =15 时时 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 13 X1 X2 X3 X4 X5 X6 XB 84 0 0 -2 -2 -3 3 X1 4 1 0 0 2 -1 (4) X2 8 0 1 1 -1 1 -1 87 -3/4 0 -2 -7/2 -9/4 0 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 14(四四)、添加新约束的灵敏度分析、添加新约束的灵敏度分析例例 新增加电力约束：新增加电力约束：1313 A A、B B、C C每单位需电每单位需电 2 2、1 1、3 3问：原方案是否改变问：原方案是否改变？2X1 +X2 +3X3 1313 原方案原方案 A A：4 B4 B：8 C8 C：0 0 16 13 16 13 原方案要改变原方案要改变 2X1 +X2 +3X3 +X6 = = 1313 user:15 XB 84 0 0 -2 -2 -3 0 X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 XB 84 0 0 -2 -2 -3 0 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6 -3 0 0 2 (-3) 1 1 82 0 0 -10/3 0 -11/3 -2/35 X1 2 1 0 4/3 0 -1/3 2/38 X2 9 0 1 1/3 0 2/3 -1/30 X4 1 0 0 -2/3 1 -1/3 -1/3 16(五五)、aij改变改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变) )(1)、非基变量、非基变量Xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列， j .关键看关键看j 0? 还是还是0? . 用用(三三)类似方法解决。类似方法解决。(2)、基变量、基变量Xj工艺改变，复杂工艺改变，复杂17例：产品例：产品A工艺改变，对甲、乙需求变为工艺改变，对甲、乙需求变为2，2。 利润为利润为7，问最优方案如何？问最优方案如何？先计算先计算 p1= 2 -1 2 = 2 -1 1 2 0一一 1= -3 取代取代 p1 与与1 放入最优表放入最优表一一一一一一18 X1 X1 X2 X3 X4 X5 0 -3 0 -2 -2 -3 X1 4 1 2 0 0 2 -1 X2 8 0 0 1 1 -1 1 78 0 0 -2 1 -3/2 7 X1 2 1 0 0 1 -1/2 8 X2 8 0 1 1 -1 1 80 -1 0 -2 0 -1 0 X4 2 1 0 0 1 -1/2 8 X2 10 1 1 1 0 1/2 19也可能也可能 B-1 b出现负数出现负数检验数与基变量均不满足最优解检验数与基变量均不满足最优解要求要求20例例 p1 = 1 C1 = 7 3p1 = B-1 p1 = 2 -1 1 = -1 -1 1 3 21= -4一一一一21 - -M M X1 X2 X3 X4 X5 X6 -4 0 -2 -2 -3 X1 4 -1 0 0 2 -1 X2 8 2 1 1 -1 1 0 0 -2 -10 1 X1 -4 1 0 0 -2 1 X2 16 0 1 1 3 -1 22X1 - 2X4 +X5 = -4-X1 +2X4 -X5 +X6 = 4 -M+7 0 -2 2M-24 -M+8 0 X6 4 -1 0 0 (2) -1 1 X2 16 0 1 1 3 -1 0 -5 0 -2 0 -4 -M+12 X4 2 -1/2 0 0 1 -1/2 1/2 X2 10 3/2 1 1 0 1/2 -3/2 23线性规划小结线性规划小结(1)70年代初年代初 Klee LP 变量变量n 约束约束2n 单纯形计算步骤单纯形计算步骤 0(2n)“算法复杂性理论算法复杂性理论”有效算法有效算法: 问题规模与计算时间为多项式关系问题规模与计算时间为多项式关系无效算法无效算法:问题规模与计算时间为指数关系问题规模与计算时间为指数关系24(2)79年年 哈其扬哈其扬 椭球法椭球法 0(n6 L2) 82年年 十一次国际数学规划会议十一次国际数学规划会议Fulkerson奖奖(3)84年年 Karmarkar 0(n3.5 L2) 88年年 13次国际数学规划会议次国际数学规划会议25(4) 当前研究方向当前研究方向1、LP的内点算法的内点算法 许国志：通过非线性规划解决线性问题，许国志：通过非线性规划解决线性问题， 其成功是对数学思想的革新。其成功是对数学思想的革新。2、算法复杂性、算法复杂性 平均复杂度：评价算法好坏应从平均平均复杂度：评价算法好坏应从平均 工作量出发。工作量出发。263、大型问题的分解算法、近似算法、大型问题的分解算法、近似算法4、应用不断扩大、应用不断扩大企业成功确实通过提高生产和企业成功确实通过提高生产和 有效使用资源的竞争过程来达到有效使用资源的竞争过程来达到27