文档介绍：§3 线性规划的对偶问题的提出
每个线性规划都有另一个线性规划(对偶问题)与它密切相关,对偶理论揭示了原问题与对偶问题的内在联系。
0
,
0
76
8
9
40
4
5
36
4
3
.
30
32
max
2
1
2
1
2
1
2
1
2
1
³
³
ï
î
ï
í
ì
£
+
£
+
£
+
+
=
x
x
x
x
x
x
x
x
t
s
x
x
z
矩阵形式
0
.
max
³
£
=
X
b
AX
t.
s
CX
z
实际问题提出:
某厂生产甲、乙两种产品,产量、利润、设备台时如下模型所示
从另一个角度讨论这个问题:工厂决定转让设备收取租金,如何确定租价? 设y1,y2,y3分别为出租单位设备台时的租价和出让单位原材料A、B的附加额。
为什么目标取最小?租金定的越高就不会有人来租,问题就没有实际意义,工厂和接受者都愿意的条件为上述规划问题的解。其中Y=(y1,y2,y3)
î
í
ì
³
=
+
î
í
ì
³
£
=
=
0
,
.
0
.
max
max
X
b
IX
AX
t
s
X
b
AX
t
s
CX
Z
CX
Z
s
理论上
因为Y的上界为无限大,所以Y只能有最小值。
§4 线性规划的对偶理论
原问题与对偶问题的数学模型
原问题标准形式:
对偶问题标准形式:
标准对偶问题
标准形式下原问题与对偶问题的对应关系
根据下表写出原问题与对偶问题的表达式
xj
yj
x1
x2
b
y1
y2
y3
1
4
0
2
0
4
8
16
12
c
2
3
如果原问题约束条件是等式约束
原问题中的价值向量与对偶问题中的资源向量对换(上下对换) 原问题: X在C和A的右边;
对偶问题:Y在b和A的左边(左右对换)