资源描述:
《线性规划的灵敏度分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第五章线性规划的灵敏度分析线性规划是静态模型参数发生变化,原问题的最优解还是不是最优哪些参数容易发生变化C,b,A每个参数发生多大的变化不会破坏最优解灵敏度越小,解的稳定性越好15.1边际值(影子价格)qi以(max,)为例边际值(影子价格)qi是指在最优解的基础上,当第i个约束行的右端项bi减少一个单位时,目标函数的变化量2例5.13关于影子价的一些说明影子价是资源最优配置下资源的理想价格,资源的影子价与资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位剩余变量增加一个单位等于资源增加一个单位资源有剩余,在最优解中就有对应松弛变量存在,且
2、其影子价为0影子价为0,资源并不一定有剩余45.2价值系数cj的灵敏度分析cj变动可能由于市场价格的波动,或生产成本的变动cj的灵敏度分析是在保证最优解的基变量不变的情况下,分析cj允许的变动范围cjcj的变化会引起检验数的变化,有两种情况:非基变量对应的价值系数变化,不影响其它检验数基变量对应的价值系数变化,影响所有非基变量检验数非基变量对应的价值系数的灵敏度分析5例5.2672基变量对应的价值系数的灵敏度分析由于基变量对应的价值系数cj在CB中出现,因此它会影响所有非基变量的检验数。只有一个基变量的发生变化,变化量为即在CB中的k分量,研究非
3、基变量xj机会成本的变化:8为什么akj=0不出现在任何一边的集合中与对偶单纯型法找入基变量的公式类似。有一边为空集如何处理设x4的价值系数增加c4,对应k=2,95.3右端项bi的灵敏度分析设XB=B1b是最优解,则有XB=B1b0b的变化不会影响检验数;b的变化量b可能导致原最优解变为非可行解。1011还是对前面的例分析,以b2为例,x6是对应的初始基变量,12135.4(技术系数aij的灵敏度分析)暂不讲授(转5.5)技术系数aij变化的影响比较复杂对应基变量的aij,且资源bi已全部用完对应基变量的aij,但资源bi未用完对应非基
4、变量的aij,且资源bi全用完或未用完1、对应基变量的aij,且资源bi已全部用完aij=02、对应基变量的aij,但资源bi未用完aijxn+i/xj上述两个公式不充分,为什么?引起B–1发生变化,从而引起非基变量的检验数zj–cj的变化3、对应非基变量的aij只影响对应非基变量xj的检验数zj–cj若aij>0,不会破坏最优解若aij<0,必须保证0zj–cj1415x1,x3为非基变量,q1=0,q2=0.25,q3=1,故有x2,x4为基变量,x5=100,b1有剩余,故有165.5新增决策变量的分析例5.1中,若新增产品
5、x8,单位产品的资源消耗量分别是:5,4,3,单位产品的利润是:9,问是否生产?已知c8=9,a18=5,a28=4,a38=3计算x8的检验数可知生产是否有利结论:生产x8有利。将B–1P8加入最优单纯型表中,以x8为入基变量进行迭代。(过程学生完成)175.6新增约束条件的分析1、将最优解代入新的约束条件,若满足,则最优解不变2、若不满足,则当前最优解要发生变化;将新增约束条件加入最优单纯型表,并变换为标准型3、利用对偶单纯型法继续迭代为什么可以利用对偶单纯型法例5.3续前例5.1,如果生产中为提高产品性能,增加一种原料,已知各产品单件生产的该
6、原料消耗量为:1,2,3,3,该原料总量为:650。应该如何调整生产计划?先把新增加的条件添加到表格中,再典范化:18(以上为典范化的过程。下面先计算判别数,可以发现是对偶可行的,因此利用对偶单纯形方法求解。)19注意:最优解的目标函数减少了25个单位205.7灵敏度分析举例(下例由学生作业完成)例5.4某工厂生产三种产品A,B,C,有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110个,求收益最大的生产方案。21解:设xj为已选定各种组合方案的组数(j=1,2,…,5),x6为A产品的剩余变量,x7,x8分别为工人工时和机器工时的
7、松弛变量。22例5.4最优解的B–1是什么产品A的影子价为多少第II组方案的生产费用提高2元,是否要调整生产组别若工人加班费为1元/小时,是否要采取加班措施若通过租借机器增加工时,租费的上限应为多少A产品的订购合同是否有利,A产品的变动范围多大若要选用第IV组方案,该组的生产费用应降低多少若工人加班费为0.3元/小时,最多允许加班时间多少若机器租费低于44元/小时,问租几部机器才合适(每天8小时计)若第III组方案使机器工时减少0.5小时,能否被选入235.8参数线性规划(暂不讲授)5.4节中aij,bi,cj只有一个发生变化,多个同时发生变化则很
8、难解析但在一些特殊情况下,用参数表示变化量,也可以用来进行多个系数的灵敏度分析5.8.1参数cj的变化分析i第i种资源的