上一节内容回顾
对偶理论是线性规划的重要内容之一。对于每个线性 规划问题,都有另一个线性规划问题(对偶)与之对应。
原问题和对偶问题紧密关联，它们不但有相同的数据集合， 相同的最优目标函数值，而且在求得一个线性规划的最优解 的同时，也同步得到对偶线性规划的最优解. 由此衍生出求 解线性规划问题的另一种算法---对偶单纯形法.
s.t. 6 x1 3 x2 5 x3 x4 45
3 x1 4 x2 5 x3 x5 30
x j 0, j 1, 2, 3, 4, 5
其中 x4 , x5 分别是资源甲和乙引进的松弛变量.
12
63 5 1 0
45
34 5 0 1
30
-3 -1 -4 0 0
0
最终表格为:
1 -1/3 0 1/3 -1/3 5
为影子价格(shadow price)
7
影子价格的大小客观地反映了各种不同资源在系
统内的稀缺程度。如果第i种资源供大于求，即在达
到最优解时，该种资源没有用完，或松弛变量
由互补松弛定理，在对偶最优解 Y* 中，第i种资源的
影子价格
反之如果第i种资源的影子价格 y*i 0
那么原问题的第i个约束为严格等式, 即
14
1. 甲乙两种资源中哪种资源的拥有量是制约利润进一步提 高的因素?
最优解为: x1 5, x2 0, x3 3, x4 0, x5 0
0 1 1 -1/5 2/5 3
0 2 0 1/5 3/5 27
因此最优解为: x1 5, x2 0, x3 3, x4 0, x5 0
13
因此最优解为: x1 5, x2 0, x3 3, x4 0, x5 0
即最优生产计划为:生产A产品5吨, C产品3吨,不生产B产品.
由于标准形的最优值为-27, 故此时对应的最题： ➢若数据发生变化，最优解会有什么变化? ➢数据集合在什么范围内波动, 最优解保持不变？
详情可以参考如下教材: <<运筹学>> 清华大学出版社
<<运筹学原理和方法>>华中科技大学出版社
3
例1、某工厂用甲,乙两种资源生产A,B,C三产品。 已知生产单位产品所需要的资源量,所获利润以及 每种资源的最大供给均列于表。试问如何安排生产 计划，即A,B,C三种产品各生产多少吨，可使该厂 所获得利润达到最大。
, 这表明
这表明第i种资源已经用完，成为稀缺资源。
8
资源的影子价格同时也是一种机会成本，在市场 经济的条件下，当某种资源的市场价格低于影子价 格时，企业应买进这种资源用于扩大生产；相反当 某种资源的市场价格高于影子价格时，企业应卖出 这种资源。随着资源的买进卖出，企业资源的影子 价格也将随之发生变化，一直到影子价格与市场价 格保持同等水平时，才处于平衡状态。
9
例1、某工厂用甲,乙两种资源生产A,B,C三产品。 已知生产单位产品所需要的资源量,所获利润以及 每种资源的最大供给均列于表。试问如何安排生产 计划，即A,B,C三种产品各生产多少吨，可使该厂 所获得利润达到最大。
原料 AB
甲
63
乙
34
利润 3 1
(千元/吨)
拥有总数 C
5
45
5
30
4
10
在此基础上,进一步考虑如下问题:
1. 甲乙两种资源中哪种资源的拥有量是制约利润 进一步提高的因素? 2. 若在市场上能按比正常价格贵0.5(千元)的单价买 到资源甲和乙, 问为了进一步提高净利润是否应该买?
3. 若欲通过提高售价提高产品B的单位利润,问B的 单位利润要提高多少(千元),才能仍在追求最大利润 的目标下考虑产品B的生产?
的右端数据向量，它代表各种资源的拥有量。
6
记
Y
( y, 1
y2 ,L
,
y ) m
是对偶问题的最优解,
由 Z=CTX* =Y*Tb=y*1b1 y*2b2 L y*mbm
得:
z bi
yi*
Y
(
y 1
,
y2
,L
, y ) m
的经济学意义是,它们代表
各单位资源在最优利用条件下所创造利润的估价，
这种估价不是资源的市场价格，为区别起见，称之
对偶问题的解有着重要的经济意义，据此可以作一些灵敏 度分析.
1
第五节 灵敏度分析
线性规划问题所对应的数据集合Ａ，b，Ｃ常常是通过 预测或估计所得到的统计数据，在实际使用中，不免会有 一定的误差。而且随着市场环境，工艺条件和资源数量的 改变，这些数据完全可能发生变化。
因此有必要来分析一下当这些数据发生波动时，对目前 的最优解或最优值会产生什么影响，这就是所谓的灵敏度 分析(结果分析)。
11
解：设该企业生产产品 A, B, C 分别为 x1, x2 , x3 吨， 则得如下数学模型:
max z 3 x1 x2 4 x3
s.t. 6 x1 3 x2 5 x3 45
3 x1 4 x2 5 x3 30
x j 0, j 1, 2, 3
化为标准形: min f 3 x1 x2 4 x3
5
对偶最优解的经济解释—影子价格
由强对偶定理可知，如果原问题有最优解 X ,
那么对偶问题也有最优解
Y
(
y , 1
y2 ,L
, y ) m
而且他们的目标函数值相等,即有:
Z=CTX* =Y*Tb=y*1b1 y*2b2 L y*mbm
其中 b=(b1 , b2 ,L , bm )T 是线性规划原问题约束条件
在此基础上,进一步考虑如下问题:
1. 甲乙两种资源中哪种资源的拥有量是制约利润进一步提 高的因素?
2. 若在市场上能按比正常价格贵0.5(千元)的单价买到资源 甲和乙, 问为了进一步提高净利润是否应该买?
3. 若欲通过提高售价提高产品B的单位利润,问B的单位利 润要提高多少(千元),才能仍在追求最大利润的目标下考虑 产品B的生产?
原料 AB
甲
63
乙
34
利润 3 1
(千元/吨)
拥有总数 C
5
45
5
30
4
4
在此基础上,进一步考虑如下问题:
1. 甲乙两种资源中哪种资源的拥有量是制约利润 进一步提高的因素? 2. 若在市场上能按比正常价格贵0.5(千元)的单价买 到资源甲和乙, 问为了进一步提高净利润是否应该买?
3. 若欲通过提高售价提高产品B的单位利润,问B的 单位利润要提高多少(千元),才能仍在追求最大利润 的目标下考虑产品B的生产?