运筹学二章 对偶线性规.ppt

本章学****要求
掌握对偶理论及其性质
掌握影子价格的应用
掌握对偶单纯形法
熟悉灵敏度分析的概念和内容
掌握右侧常数,价值系数,工艺系数的变换对原最优解的影响
掌握增加新变量和增加新约束条件对原最优解的影响,并求出相应因素的灵敏度范围
2018/9/9
1
浙江科技学院经济管理学院管工系

问题的提出
对称形式下对偶问题的一般形式
非对称形式下的原问题与对偶问题的关系
2018/9/9
2
浙江科技学院经济管理学院管工系
一、对偶问题的提出
每一个LP问题,都伴随着另一个LP,而且二者有密切关系,互为对偶,另其中一个问题为原问题,另一个问题为对偶问题,只要得到了其中一个问题的解(目标值),也得到另一问题的解,因此通常只求解一个问题就可以了。
例1:(美佳公司)
美佳公司应如何生产安排,使已有资源利润最大化。
某公司至少该出多大代价,使美佳公司愿意放弃自己的资源,
产品
资源
Ⅰ
Ⅱ
资源约束
A
0
5
15
B
6
2
24
调试工序
1
1
5
单位产品利润
2
1
产品
资源
A
B
调试
工序
单位资源利润
Ⅰ
0
6
1
2
Ⅱ
5
2
1
1
资源量
15
24
5
2018/9/9
3
浙江科技学院经济管理学院管工系
数学模型
Cj
2
1
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x3
15/2
0
0
1
5/4
-15/2
2
x1
7/2
1
0
0
1/4
-1/2
1
x2
3/2
0
1
0
-1/4
3/2
σj
0
0
0
-1/4
-1/2
cj
-15
-24
-5
0
0
-M
CB
YB
b
y1
y2
y3
y4
y5
y6
θ
-M
y6
2
0
6
1
-1
0
1
1/3
-15
y1
1/5
1
2/5
1/5
0
-1/5
0
5/2
σj
0
6M-18
M-2
-M
-3
0
-24
y2
1/3
0
1
1/6
-1/6
0
1/6
2
-15
y1
1/5
1
0
2/15
1/15
-1/5
-1/15
1/2
σj
0
0
1
-3
-3
-M+8
-24
y2
1/4
-5/4
1
0
-1/4
1/4
1/2
-5
y3
1/2
15/2
0
1
1/2
-3/2
-3
σj
-15/2
0
0
-7/2
-3/2
-M-3
①
②
Z*=
W*=
2018/9/9
4
浙江科技学院经济管理学院管工系
二、对偶问题的一般形式
一般认为变量均为非负约束的情况下,约束条件在目标函数取Max时均取“≤”号;当目标函数求Min值时均取“≥“号。则称这些线性规划问题具有对称性。
max z=c1x1+c2x2+……+cnxn
. a11x1+a12x2+……+a1nxn ≤b1
a21x1+a22x2+……+a2nxn ≤b2
……
am1x1+am2x2+……+amnxn ≤bm
x1, x2, ……, xn ≥0
min w=b1y1+b2y2+……+bmym
. a11y1+a21y2+……+am1ym ≥ c1
a12y1+a22y2+……+am2ym ≥ c2
……
a1ny1+a2ny2+……+amnym ≥ cn
y1, y2, ……, ym ≥0
Max Z=CX
. AX≤b
X≥0
Minw=Y’b
. A’Y≥C’
Y≥0
2018/9/9
5
浙江科技学院经济管理学院管工系
原问题
max z=CX
. AX≤b
X ≥0
对偶问题
min w=Y’b
. A’Y≥C’
Y ≥0
≥
max
b
C
C
AT
b
≤
min
m
n
m
n
A
2018/9/9
6
浙江科技学院经济管理学院管工系
举例:
maxZ=3x1+2x2
. -x1+2x2≤4
3x1+2x2≤14
x1-x2 ≤3
x1,x2≥0
minw=4y1+14y2+y3
. -y1+3y2+y3≥3
2y1+2x2-y3≥2
y1,y2,y3≥0
y1
y2
y3
第一种资源
第二种资源
第三种资源
第一种产品
第二种产品
x1
x2
2018/9/9