第02章 线性规划的对偶理论与灵敏度分析 -运筹学.ppt

运筹学方法及其应用
讲授:毕德春
辽东学院信息技术学院信息管理系
11/11/2017
1
第2章线性规划的对偶理论与灵敏度分析
11/11/2017
2
Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工,加工每件Ⅰ产品或Ⅱ产品所需的设备机时数、利润值及每种设备可利用机时数列于下表,请问:充分利用设备机台时,工厂应生产Ⅰ和Ⅱ产品各多少件才能获得最大利润?试列出相应的线性规划数学模型。
A
B
C
产品利润/(元/件)
Ⅰ
2
4
0
2
Ⅱ
2
0
5
3
设备可用机时数(工时)
12
16
15
§1 对偶问题的提出
11/11/2017
3
解:设Ⅰ、Ⅱ产品的生产数量分别为x1和x2,建立问题数学模型如下:
max z =2x1+3x2
2x1+2x2≤12
4x1 ≤16
5x2 ≤15
xj≥0,j=1,2
现假设有另一家四海机器厂,为了扩大生产想租借常山机器厂拥有的设备资源,问常山厂分别以每小时什么样的价格才愿意出租自己的设备呢?
11/11/2017
4
设A、B、C设备的机时单价分别为y1、y2、y3,新的线性规划数学模型为
min w=12y1+16y2+15y3
2y1+4y2 ≥2
2y1 +5y3≥3
yj≥0,j=1,2,3
A(y1)
B(y2)
C(y3)
产品利润/(元/件)
Ⅰ(x1)
2
4
0
2
Ⅱ(x2)
2
0
5
3
设备可用机时数(工时)
12
16
15
11/11/2017
5
2
3
x1
x2
原问题
12
y1
2
2
≤
12
16
y2
4
0
≤
16
15
y3
0
5
≤
15
对偶问题
2
3
11/11/2017
6
X1 , X2 , …, Xn
xj
yi
原关系
对偶关系…
Min w
Max Z
Max Z =
Min w
原问题与对偶问题的形式关系
11/11/2017
7
原始问题
max z=CX
. AX≥b
X ≥0
对偶问题
min w=bTY
. ATY≤CT
Y ≥0
≥
max
b
A
C
CT
AT
bT
≤
min
m
n
m
n
11/11/2017
8
2 原问题与对偶问题
max z = c1x1 + c2x2 + …+ cnxn
. a11x1 + a12x2 + …+ a1nxn ≤ b1
a21x1 + a22x2 + …+ a2nxn ≤ b2
(1) ……
am1x1 + am2x2 + …+ amnxn ≤ bm
xj ≥ 0 (j = 1,2,…,n)
min w = b1 y1 + b2 y2 + …+bm ym
. a11y1 + a21 y2 + …+ am1ym ≥ c1
a12y1 + a22y2 + …+ am2 ym ≥ c2
(2) ……
a1ny1 + a2ny2 + …+ amnym ≥ cn
yi≥ 0 (i = 1,2,…,m)
设原 LP 问题为
则称下列 LP 问题
为其对偶问题,其中 yi ≥ 0 (i = 1,2,…,m)称为对偶变量,
并称(1)、(2)为一对对称型对偶问题
11/11/2017
9

min w=12x1+8x2 +16x3+12x4
. 2x1+ x2 +4x3  2
2x1+2x2 + 4x4  3
x1,x2 , x3 , x4  0
min w=12x1+8x2 +16x3+12x4
. 2x1+ x2 +4x3  2 y1
2x1+2x2 + 4x4  3 y2
x1,x2 , x3 , x4  0
解:该问题的对偶问题:
max z = 2y1 + 3y2
. 2y1 + 2y2  12
y1 + 2y2  8
4 y1  16
4y2  12
y1,y2  0
11/11/2017
10