运筹学02.4对偶问题的经济意义-影子价格

cj
min(2,1) 2 y4 换出 换出
5 y3 1 1 5 1/ 6 2/3 1 0 1 0 0 y4 y5 1 0 0 1 0 0 1/ 6 0 1/ 3 1 4 0 y2 换出 1/ 4 1/ 4 1/ 2 3 / 2
例、用对偶单纯形法求解线性规划问题：
第三节
对偶单纯形法
对偶单纯形法的基本思路
继续
返回
用对偶原理求解原问题的一种方法， 而不是求解对偶问题解的单纯形法 对偶单纯形法的计算步骤
对 偶 问 题
对偶单纯形法的基本思路
单纯形法的基本思路：
原问题基可行解 C-CBB-1A≤0 最优解判断
~ 1 Xb B b 0
上页 下页 返回
* i 的意义——代表在资源最优利
上页 下页 返回
对 偶 问 题
影子价格的经济意义
1．资源的市场价格是已知数，相对比
上页 下页 返回
较稳定，而它的影子价格则有赖于资源 的利用情况，是未知数。由于企业生产 任务、产品结构等情况发生变化，资源 的影子价格也随之改变。
企业 市场价格 影子价格
市场
对 偶 问 题
最优解
对 偶 问 题
对偶单纯形法的优点：
不需要人工变量； 当变量多于约束时，用对偶单纯形法可减少 迭代次数； 在灵敏度分析中，有时需要用对偶单纯形法 处理简化。

上页 下页 返回
对偶单纯形法缺点：

对初始单纯形表形式要求较严格（在对偶问 题可行的前提下），普遍适用性较差。 因此，对偶单纯形法一般不单独使用。
对 偶 问 题
影子价格的经济意义
3．资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源的 市场价格低于1/4时，可以买进这种资源； 相反当市场价格高于影子价格时，就会卖 出这种资源。随着资源的买进卖出，它的 影子价格也将随之发生变化，一直到影子 价格与市场价格保持同等水平时，才处于 平衡状态。

灵敏度分析--影子价格
14
1. 甲乙两种资源中哪种资源的拥有量是制约利润进一步提 高的因素?
最优解为: x 1 5 ,x 2 0 ,x 3 3 ,x 4 0 ,x 5 0
解: (方法一) 由最终表格知,对偶问题的最优解为
y1
1 5
,
y2
3 5
.
又对偶问题最优解的经济学意义-----资源的影子价格得:
由于标准形的最优值为-27, 故此时对应的最大利润为27千元.
在此基础上,进一步考虑如下问题:
1. 甲乙两种资源中哪种资源的拥有量是制约利润进一步提 高的因素?
2. 若在市场上能按比正常价格贵0.5(千元)的单价买到资源 甲和乙, 问为了进一步提高净利润是否应该买?
3. 若欲通过提高售价提高产品B的单位利润,问B的单位利 润要提高多少(千元),才能仍在追求最大利润的目标下考虑 产品B的生产?
3. 若欲通过提高售价提高产品B的单位利润,问B的 单位利润要提高多少(千元),才能仍在追求最大利润 的目标下考虑产品B的生产?
灵敏度分析--影子价格
5
对偶最优解的经济解释—影子价格
由强对偶定理可知，如果原问题有最优解 X ,
那么对偶问题也有最优解 Y(y1 ,y2 ,
,y) m
而且他们的目标函数值相等,即有:
灵敏度分析--影子价格
9
例1、某工厂用甲,乙两种资源生产A,B,C三产品。 已知生产单位产品所需要的资源量,所获利润以及 每种资源的最大供给均列于表。试问如何安排生产 计划，即A,B,C三种产品各生产多少吨，可使该厂 所获得利润达到最大。
原料 AB
甲
63
乙
34
利润 3 1
(千元/吨)

1
若初始矩阵中变量 xj的系数向量为Pj, 迭代后为P’j, 则有 P’j=B-1 Pj
2
当B为最优基时，应有
3
令Y=CBB-1, 则
项 目
基变量
非基变量
XB
XN Xs
CB XB B-1b
I
B-1N B-1
cj-zj
0 -Ys1
XB XN
Xs
0 Xs b
B N
I
cj-zj
CB CN
0
项 目
基变量
非基变量
XB
XN Xs
CB XB B-1b
I
B-1N B-1
cj-zj
0
CN-CBB-1N -CBB-1
02
对偶性质
对偶性质
例2.4 已知线性规划 的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。 解：写出原问题的对偶问题，即 标准化
Y＊=(1,1)，最优值w=26。
解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：
对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：
在市场竞争的时代，厂长的最佳决策显然应符合两条： 吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。
设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：
原问题的松弛变量
x1
x2
x3
x4
x5
x3
15/2
0
0
1
5/4
-15/2
x1
7/2

在取得最优方案的前提下
比较第i种资源增加一个单 位，其余资源不增加时利 润的增加值
设B是最优基， Z*是最优值
(D )m S i b 1 y n 1 b 2 y 2 b m y m
a11y1 a21y2 am1ym c1
s.ta12y1
a22y2 am2ym
由互补松弛定理： 由 y2*370 ,y3*670 ,2xx11**53xx22**115000
现有资源中的煤炭和设备台时已经全部用完而没有剩余， 因此若增加这两种资源，必然会工厂带来新的效益。
若把最优方 约案 束5 带 x： 1* 入 2有 x2*钢 675材 0 170 现有资源中的钢材有剩余，因此若增加这种资源， 只能造成积压，不会给工厂增加效益。
源数、每种0 资源 限 0 的 制数 以 0 量 及-每 32/7 件-6产 得 /7 品 的 Z-41可 0利 0/7 获 润如下
问如何x安 3 排0 生产 才 0 计 能划 充 1 ， 分利 -23/7 用1现 1， /7 有 使 540/资 7获源 得的总
润最大x？ 1 1
0
0
5/7
-3/7 50/7
不增加木板，不在餐桌的销路上投资（如广告等） 若市场上1小时的漆工工资<10元，可增加漆工 若市场上1小时的木工工资<10元，可增加木工
影子价格是一种资源的虚拟价格 ≠资源的市场价格
3、影子价格在经济管理中的应用
影子价格能指示企业内部挖潜的方向
影子价格越大的资源，表明： 这种资源对目标增益的影响越大 这种资源对该企业 越稀缺、贵重
四、互补松弛定理
设X*和Y*分别是（P）和（D）的可行解， 则X*和Y*分别是（P）和（D）的最优解的 充要条件是方程组