MATLAB非线性规划建模灵敏度分析 ppt课件

第二章 对偶线性规划
对偶的定义 对偶问题的性质 原始对偶关系 dual linear programming
目标函数值之间的关系 最优解之间的互补松弛关系
对偶单纯形法 对偶的经济解释 灵敏度分析
2015/10/27
DUAL
1
§2.1 线性规划的对偶问题
一、对偶问题的提出
现有甲乙两种原材料生产 A1，A2两种产品，所需的 原料，甲乙两种原料的可 供量，以及生产A1,A2两种 产品可得的单位利润见表。 问如何安排生产资源使得 总利润最大？
2015/10/27
3
解：设生产A1为x1件，生产A2为x2件，则线性规划问题为： maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 A1 A2 原料 4x1+5x2≤40 3 2 24 甲 x1,x2≥0 4 5 40 另一方面，假设另一公司想把资源买 乙 过来，它至少应付出多大代价才能使原来 利润 4.5 5 公司放弃生产，出让资源？ 解：设甲资源的出让价格为y1,乙资源的出让价格为y2 minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5y2≥5 y1,y2≥0
A1 3 甲 4 乙 利润 4.5 A2 原料 2 24 5 40 5
2015/10/27
2
解:设生产A1为x1单位，生产A2为x2单位,则线性规划问题为： maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 A1 A2 原料 4x1+5x2≤40 3 2 24 甲 x1,x2≥0 4 5 40 另一方面，假设另一公司想把资源买 乙 过来，它至少应付出多大代价才能使原来 利润 4.5 5 公司放弃生产，出让资源？ 解：设甲资源的出让单价为y1,乙资源的出让单价为y2 minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5y2≥5 y1,y2≥0

具体对本例来说： milk）原料最多增加10（桶牛奶），time） 劳动时间最多增加53（小时）。
现在可以回答附加问题1）的第2问：虽然应该批准用35元买1 桶牛奶的投资，但每天最多购买10桶牛奶。顺便地说，可以用 低于每小时2元的工资聘用临时工人以增加劳动时间，但最多增 加小时。
需要注意的是：灵敏性分析给出的只是最优基保持不变 的充分条件，而不一定是必要条件。比如对于上面的问 题，“原料最多增加10（桶牛奶）”的含义只能是“原 料增加10（桶牛奶）”时最优基保持不变，所以影子价 格有意义，即利润的增加大于牛奶的投资。反过来，原 料增加超过10（桶牛奶），最优基是否一定改变？影子 价格是否一定没有意义？一般来说，这是不能从灵敏性 分析报告中直接得到的。此时，应该重新用新数据求解 规划模型，才能做出判断。所以严格来说，我们上面回 答“原料最多增加10（桶牛奶）”并不是完全科学的。
显然，如果在最优解处约束正好取等号（也就是“紧约束”， 即起作用约束），对偶价格值才可能不是0。本例中：第3、4 行是紧约束，对应的对偶价格值为10，表示当紧约束
3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20 变为 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 21 时，目标函数值 = 280 +10 = 290。对第4行也可类似解释。
2单位
1.5单位 0.5单位 8单位
60单位 30单位 20单位
若要求桌子的生产量不超过5件，如何安排三种产品 的生产可使利润最大？
解： 用DESKS、TABLES和CHAIRS分别表示三种
产品的生产量（决策变量），容易建立LP模型。
在LINDO模型窗口中输入模型：

输出中除了告诉我们问题的最优解和最优值以外，还有许 多对分析结果有用的信息，下面结合题目中提出的3个附加 问题给予说明。
3个约束条件的右端不妨看作3种“资源”：原料、劳动时间、 车间甲的加工能力。输出中SLACK OR SURPLUS （松弛或 剩余）给出这3种资源在最优解下是否有剩余：原料、劳动时 间的剩余均为零（即约束为紧约束），车间甲尚余40公斤加 工能力（不是紧约束）。
2. 约束右端项变化的范围（Right Hand Side RANGES） 如本例中：第2行约束中当前右端项（CURRENT RHS）=48， 允许增加（Allowable Increase）=INFINITY（无穷）、允许 减少（Allowable Decrease）=24，说明当它在
[48-24，48+ ) = [24，）
目标函数可以看作“效益”，成为紧约束的“资源”一旦增加， “效益”必然跟着增长。
输出中DUAL PRICES（对偶价格） 给出这3种资源在最优解 下“资源”增加1个单位时“效益”的增量：原料增加1个单位 （1桶牛奶）时利润增长48（元），劳动时间增加1个单位（1 小时）时利润增长2（元），而增加非紧约束车间甲的能力显 然不会使利润增长。
选择“是（Y）”按钮，这表示你需要做灵敏性分析。 然后，查看输出结果。
输出结果的前半部分：
LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE
VARIABLE VALUE
REDUCED COST
ROW SLACK OR SURPLUS DUAL PRICES
RHS
INCREASE
DECREASE
3
20.000000
4.000000

为了回答这些问题，可以在变化了的条件下重新求解
线性规划问题。但是这样做太麻烦，也不必要。本节的目
的是讲，如何在已经得到的最优解的基础上，进行适当的
修改计算，即可回答上面的问题。这就是灵敏度分析的基
本内容。
精选2021版课件2二、灵敏度分析的定义灵敏度分析就是研究cj、bi、aij等参数在 什么范围内变化时最优解不变，若最优 解发生变化，如何用简便的方法求出新 的最优解。
8 x2 0 1 1 1 1 8
f 0 0 C3-28 2 3 84
由上表可知：当C3-8≤ 0 ，即 0≤ C3≤8时，最优解不变。
精选2021版课件
9
1.2基变量对应价值系数变化
(1)基变量对应的价值系数C1的变化 C51 8 6 0 0
x1 x2 x3 x4 x5
bi
C51 x1 1 0 0 2 1
bi
5 x1 1 0 0 2 1 4
C82 x2 0 1 1 1 1
8
f 0 0 6-C22 C2-210 5-C32 -(2804+8C2)
由上表可知：当 6-C2 ≤ 0 ， C2-10 ≤ 0，同时 5-C2 ≤ 0 ，
即 6≤ C2≤10时，最优解不精变选。2021版课件
11
价值系数cj变化的分析总结
17
结论
当b1=22,b2=20时， 最优基改变，最优解变为： x1=20，x4=2
精选2021版课件
18
保持b2=20,分析b1在什么范围内
变化时，最优基不变?
B 1b' 2 1 1 1 2 b 1 0 2b b 1 1 2 2 0 0 0
解之得：10≤b1≤20
•b的变化量b可能导致原最优解变为非基可行解 设b’=b+ b