文档介绍：§5 对偶问题的经济解释—影子价格
(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。
当某约束条件的右端常数增加一个单位时(假设原问题的最优基不变),原问题的目标函数最优值增加的数量。
Z*=CX*=Y*b
=(y1*,y2*, …,ym*)
b1
b2
﹕
﹒
bm
=y1*b1+y2*b2+…+ym*bm
当某个右端常数bi bi+1时
bi+1
yi*
+yi*(bi+1)
=Y*b+yi*
=Z*+yi*
第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时,目标函数增加的数量
甲乙
可用量
机械设备
1 2
8
原材料A
4 0
16
原材料B
0 4
12
X(3)=(4,2,0,0, 4)T, z3 =14
cj
2
3
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
2
0
3
x1
x5
x2
4
4
2
1
0
0
0
0
1
-2
½
-3/2
½
-1/8
1/8
0
1
0
-14
0
0
-3/2
-1/8
0
经济意义:在其它条件不变的情况下,
单位资源变化所引起的目标函数的最优值的变化。
影子价格
产品
资源
ⅠⅡ
现有资源数
钢材
1 2
100(吨)
煤
2 2
180(吨)
机时
1 6
240(小时)
利润(万元)
1 3
x1
x2
x3
x4
x5
-z
XB
-135
0
0
-3/4
0
-1/4
x1
30
1
0
3/2
0
-1/2
x4
50
0
0
-5/2
1
1/2
x2
35
0
1
-1/4
0
1/4
X*=(30,35,0,50,0)T,
Z*=135
y1*=3/4
y2*=0,
y3*=1/4
影子价格
经济意义:在其它条件不变的情况下,
单位资源变化所引起的目标函数的最优值的变化。
影子价格的意义
(1)影子价格客观地反映资源在系统内的稀缺程度。
如果某一资源在系统内供大于求(即有剩余),其影子价格就为零。如果某一资源是稀缺的(即相应约束条件的剩余变量为零),则其影子价格必然大零。影子价格越高,资源在系统中越稀缺。
(2)影子价格是对系统资源的一种优化估价,只有当系统达到最优时才能赋予该资源这种价值,因此也称最优价格。
(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化,都会引起影子价格的变化,它是一种动态价格。
(4)如果考虑扩大生产能力,应该从影子价格高的设备入手。
§6 对偶单纯形法
保持对偶可行性,逐步改进主可行性,求解主问题。
当b有负分量,A中有一明显初始对偶可行基(检验数均非正),因而易得一初始解时,可用对偶单纯形法求解。
设B为一个基
基本解
X(0)为基本可行解的条件?
B-1b≥0
X(0)为最优解的条件?
原
原始可行性条件
原始最优性条件
令Y=CBB-1,代入原始最优性条件,→YA≥C
对偶可行性条件
例用对偶单纯形法求解
单纯形法
大M 法
剩余变量、人工变量
用(-1)乘不等式两边,再引入松弛变量。
cj
-1 -4 0 -3 0 0
CB
XB
b
x1 x2 x3 x4 x5 x6
0
0
x5
x6
-3
-2
-1 -2 1 - 1 1 0
2 1 -4 -1 0 1
0
-1 -4 0 -3 0 0
先选出基变量
后选进基变量
原问题,符合原始最优性条件,但不可行
cj
-1 -4 0 -3 0 0
CB
XB
b
x1 x2 x3 x4 x5 x6
-1
0
x1
x6
3
-8
1 2 - 1 1 -1 0
0 -3 -2 -3 2 1
3
0 -2 -1 -2 -1 0
cj
-1 -4 0 -3 0 0
CB
XB
b
x1 x2 x3 x4 x5 x6
-1
0
x1
x6
3
-8
1 2 - 1 1 -1 0
0 -3 -2 -3 2 1
3
0 -2 -1 -2 -1 0
-1
0
x1
x3
7
4
1 7/2 0 5/2 -2 -1/2
0 3/2 1 3/2 -1 -1/2
7
0 -1/2 0 -1/2 -2 -1/2
最优解
X*=(7,0,4,0)T
Z*=-7
例6 用对偶单纯形法求解
(P)