运筹学基础-对偶线性规划(1).ppt

一、对偶线性规划问题
某工厂计划安排生产Ⅰ、Ⅱ两种产品,已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示:
【例1】
Ⅰ
Ⅱ
设备
1
2
8台时
原材料 A
4
0
16Kg
原材料 B
0
4
12Kg
每单位产品利润(万元)
2
3
原问题的策略:
问应如何安排生产才能使工厂获利最大?
现在的策略:
假设不生产Ⅰ、Ⅱ产品,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?
设x1、x2分别表示计划生产产品Ⅰ、Ⅱ的单位数量,由题意原问题的模型为:
工厂获得最大利润
符合资源限制
Ⅰ
Ⅱ
设备
1
2
8台时
原材料 A
4
0
16Kg
原材料 B
0
4
12Kg
每单位产品利润(万元)
2
3
原问题的模型
改变策略后,需要考虑如何给资源定价的问题!
设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.
y1+4y2≥2,
2y1+4y3≥3
则:
工厂出租设备、原材料的租金要大于生产的利润才合算。
工厂把所有设备台时和资源都出租和出让,其收入为:
要寻找使租用者支付的租金最少的策略。
Ⅰ
Ⅱ
设备
1
2
8台时
原材料 A
4
0
16Kg
原材料 B
0
4
12Kg
每单位产品利润(万元)
2
3
新问题的模型
工厂改变策略以后的数学模型为:
工厂获得相应利润
用户所付租金最少
联系在于,它们都是关于工厂生产经营的模型,并且使用相同的数据;
原模型和对偶模型既有联系又有区别
区别在于,它们所反映的实质内容是完全不同的:前者是站在工厂经营者的立场上追求工厂的销售收入最大,而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。
所谓对偶规划,就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。
原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化,对偶问题即求目标函数最小化;原问题目标函数的系数变成为对偶问题的右边项,而原问题的约束的右边项则变成为对偶问题目标函数的系数;对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样,原问题与对偶问题之间存在着严格的对应关系。
原问题的一般模型可定义为:
二、对偶规划的一般数学模型
n
n
x
c
x
c
x
c
Z
+
+
+
=
...
max
2
2
1
1
.
1
1
2
12
1
11
...
b
x
a
x
a
x
a
n
n
£
+
+
+
2
2
2
22
1
21
...
b
x
a
x
a
x
a
n
n
£
+
+
+
……….
m
n
mn
m
m
b
x
a
x
a
x
a
£
+
+
+
...
2
2
1
1
0
,...,
,
2
1
³
n
x
x
x
相应的对偶问题的一般模型可定义为:
m
m
y
b
y
b
y
b
S
+
+
+
=
...
min
2
2
1
1
.
1
1
2
21
1
11
...
c
y
a
y
a
y
a
m
m
³
+
+
+
2
2
2
22
1
12
...
c
y
a
y
a
y
a
m
m
³
+
+
+
………
n
m
mn
n
n
c
y
a
y
a
y
a
³
+
+
+
...
2
2
1
1
0
,...,
,
2
1
³
m
y
y
y
上述的原问题P和对偶问题 D还可以用矩阵形式写为:
(P) max Z= cx
. Ax
≤b
x
≥0
其中
)
,..,
,
(
2
1
m
y
y
y
y
=
上述的对偶模型都称作为对称型对偶模型。
而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的,如:
(P) maxZ= cx
. Ax =b
x≥0
. yA
y
≥
c
≥
0
(D) min S= yb
. yA≥c
y为自由变量
(D) minS= yb
原问题与对偶问题的矩阵形式
问题:如何由原模型写出对偶模型?其规律是什么?
三、原问题与对偶问题的对应关