18灵敏度分析

1§1.8灵敏度分析CBB-1bC-CBB-1AB-1bB-1A原始数据A，b，CA=(P1P2…Pn)公式①Z0=CBB-1bXB=B-1b②λA=C-CBB-1AλN=CN-CBB-1Nλj=Cj-CBB-1Pj2③A=B-1APj=B-1Pj~~标准型maxZ=CXAX=bX0(1)、参数A，b，C在什么范围内变动，对当前方案无影响？(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？3例：ABC备用资源甲11112乙12220利润586产品原料问：如何安排产品产量，可获最大利润？4maxZ=5X1+8X2+6X3X1+X2+X3+X4=12X1+2X2+2X3+X5=20X1…X50解558600X1X2X3X4X5CBXB0586000X412111100X52012201CBXB8400-2-2-35X141002-18X28011-11…6(一)、目标函数系数Cj的灵敏度分析(1)、非基变量系数Cj①Cj改变，λj仍0时对最优方案无影响。例中C3改变λ3=C3-CBB-1P3=C3-(58)=C3-802-1-1112即C387②C3改为10，λ3=20CBXB8400(2)-2-35X141002-18X2801(1)-11XB1000-200-55X141002-110X38011-118(2)、基变量系数Cj①Cj改变，全部λj0，最优方案不变。例中C1改变λA=C-CBB-1A=(C1,8,6,0,0)-(C18)1002-1011-11=(0,0,-2,-2C1+8,C1-8)0-2C1+80C1-804C189②C1改变C1=10，λ5=20,换基XB10400-2-12210X141002-18X28011-1(1)1200-2-4-10010X112111100X58011-1110(二)、约束条件右端项bj的灵敏度分析(1)、bj改变，B-1b仍0时，最优方案不变。例中b1改变2-1-11b12010b120B-1b=02b1-200-b1+20011(2)、b1改变,b1=30，CBXB12000-2-2-35X1401002-18X2-10011(-1)11000-2-40-55X120122010X4100-1-11-12-1-113020B-1b==40-1012(三)、添加新变量的灵敏度分析例对于新产品D，已知1个单位D要消耗甲：3乙：2可以得利润10问：投产产品D是否有利？6=C6-CBB-1P6=10-(58)2-13-112=10-12=-20结论：无利13（1）利润为多少时，投产产品D有利？Λ6=C6-CBB-1P6=C6-120得C612（2）C6=15时6=3P6=B-1P6=2-13=4-112-1~14X1X2X3X4X5X6XB8400-2-2-33X141002-1(4)X28011-11-187-3/40-2-7/2-9/40X611/400-1/2-1/41X291/411-1/23/4015(四)、添加新约束的灵敏度分析例新增加电力约束：13A、B、C每单位需电2、1、3问：原方案是否改变？2X1+X2+3X313原方案A：4B：8C：01613原方案要改变2X1+X2+3X3+X6=13user:16XB8400-2-2-30X141002-10X28011-110X613213001XB8400-2-2-305X141002-108X28011-1100X6-3002(-3)118200-10/30-11/3-2/35X12104/30-1/32/38X29011/302/3-1/30X4100-2/31-1/3-1/3…………17(五)、aij改变(计划生产的产品工艺结构改变)(1)、非基变量Xj工艺改变只影响单纯形表Pj列，λj.关键看λj0?还是0?.用(三)类似方法解决。(2)、基变量Xj工艺改变，复杂18例：产品A工艺改变，对甲、乙需求变为2，2。利润为7，问最优方案如何？先计算p1’=2-12=2-1120一1’=-3取代p1与λ1放入最优表一一一19X1X1’X2X3X4X50-30-2-2-3X1412002-1X280011-117800-21-3/27X1’21001-1/28X28011-1180-10-20-10X421001-1/28X21011101/220•也可能B-1b出现负数•检验数与基变量均不满足最优解要求21例p1’=1C1’=73p1’=B-1p1’=2-11=-1-1132λ1’=-4一一22-MX1’X2X3X4X5X6-40-2-2-3X14-1002-1X28211-1100-2-101X1’-4100-21X2160113-123X1’-2X4+X5=-4-X1’+2X4-X5+X6=4-M+70-22M-24-M+80X64-100(2)-11X2160113-10-50-20-4-M+12X42-1/2001-1/21/2X2103/21101/2-3/224线性规划小结(1)70年代初KleeLP变量n约束2n单纯形计算步骤0(2n)“算法复杂性理论”有效算法:问题规模与计算时间为多项式关系无效算法:问题规模与计算时间为指数关系25(2)79年哈其扬椭球法0(n6L2)82年十一次国际数学规划会议Fulkerson奖(3)84年Karmarkar0(n3.5L2)88年13次国际数学规划会议26(4)当前研究方向1、LP的内点算法许国志：通过非线性规划解决线性问题，其成功是对数学思想的革新。2、算法复杂性平均复杂度：评价算法好坏应从平均工作量出发。273、大型问题的分解算法、近似算法4、应用不断扩大企业成功确实通过提高生产和有效使用资源的竞争过程来达到