线性规划对偶理论及其应用30页PPT

max 2u1 u2
u1 u2 5
s.t.6uu11
u2 2u2
0 21
u1
0
u2 0
第5页/共51页
模型对比(对称形式)
m a xZ 1 0x1 1 8x2
5 x1 2 x2 1 7 0
2 x1 x1
3 x2 5 x2
100 150
x1 , x2 0
又由于X *是原问题的最优解，故 cT X * cBT B1b
由此得到
c T X * bTY * 可见Y *是对偶问题的最优解。
第22页/共51页
3、互补松弛性
在线性规划问题的最优解中， 如果对应某一约束条件的对偶变量值为非零，
则该约束条件取严格等式；
反之如果约束条件取严格不等式，
x5 1
x j 0, j 1,,5
解: c (5,0,21,0,0)T ,b (2,1)T , A 1 1 6 1 0 1 1 2 0 1
第4页/共51页
其对偶问题为
写成分量形式，即
max 2
1
u1 u2
1 1
s.t.
6
1
0
1
5
1 2 0
u1 u2
0
21
0
1
0
（2）无界性
如果原问题（对偶问题）具有无界解， 则其对偶问题（原问题）无可行解。
（3）最优性
如果xˆ j ( j 1, 2, , n)是原问题的可行解
yˆi (i 1, 2, , m)是其对偶问题的可行解
n
m
且有 cj xˆ j bi yˆi
j 1
i 1
则xˆ j ( j 1, 2, , n)是原问题的最优解

m a x S = 8 x 1 2 0 x 2 1 2 x 3 1 5 x 4 1 x 1 1 0 x 2 2 x 3 3 x 4 1 8 0 0 0
3 x 1 2 x 2 5 x 3 4 x 4 1 3 0 0 0 x 1 0 ,x2 0 ,x 3 0 ,x4 0
6
现在从另一个角度考虑问题。假设该厂不生 产A、B、C、D四种产品了，而是将甲、乙两种 资源出租给其它单位，其原则是：使别的单位 愿意租，又使本单位获利不低于原利润。问如 何给甲、乙两种资源定价最合理？
x1 x2 x3 12
x1 2x
1
x2 x
2
x3 x
3
10 14
x 1 , x 2 0
16
解 先化为对称形式
m ax S 3 x1 2 x2 x3
x1 x2 x3 12
x1 2x
1
x2 x
2
x3 x
3
10 14
x 1 , x 2 0
m a xS3x 12x 2x 3
10
对偶问题的矩阵表示： Y(y1,y2, ,yn)
原问题
m ax S CX
AX b
X
对偶问题
m in W b TY ATY C T Y
y1
Y
y
2
yn
C(c1,c2,
,cn), X
x1
x
2
,
b
b1
b2
,
xn
bm
11
对偶问题的矩阵表示： Y(y1,y2, ,yn)
是否会认为老师的教学方法需要改进？ • 你所经历的课堂，是讲座式还是讨论式？ • 教师的教鞭 • “不怕太阳晒，也不怕那风雨狂，只怕先生骂我

AX b
s.t.
X
0
YA C s.t.Y 0
• 其中Y=（y1,y2,…,ym）,其他同前。
• 3.1.3 一般问题旳对偶问题——非对称型对偶问题
• • 线性规划有时以非对称型出现，那么怎样从原始问题写出
它旳对偶问题呢？
11
OR:SM
• 例1 写出下列线性规划旳对偶问题
max Z ( x) 2x2 5x3
23
OR:SM
• 例4 求解下列线性规划问题
max Z ( x) 4 x1 3x2
Y1
x1
6
Y2
x2 8
Y3
s.t.
x1
x2
7
Y4
3
x1
x2
15
Y5
x2 1
x1, x2 0
(3 7)
• 解：该问题仅有两个变量，但约束较多，其对偶问题为
minW ( y) 6 y1 8 y2 7 y3 15 y4 y5
y1 y3 3y4 4
s.t.
y2
y3
y4
y5
3
y1, y2 , , y5 0
(3 8)
24
OR:SM
• 把上述问题（3-8）作为原始问题求解，其最终单纯形表见下 表（3.3）
22
OR:SM
• 3.1.5 对偶问题旳最优解
• 主要推论： • 1.原始问题单纯形表中松驰变量旳检验数恰好相应着对偶
问题旳一种解。 • 2.原始问题单纯形表中,原始问题旳松弛变量旳检验数相应
于对偶问题旳决策变量;而原始问题旳决策变量旳检验数相应 于对偶问题旳松弛变量,只是符号相反。
• 注意：在两个互为对偶旳线性规划问题中，可任选一种进行 求解，一般是选择约束条件少旳，因求解旳工作量主要受到 约束条件个数旳影响。

AX b
s.t.

X
0
对偶问题 :
min g( y) Yb
s.t.
YA C

Y

0
上两式中
X ( x1, x2 ,, xn )T Y ( y1, y2 ,, ym ) C (c1, c2 ,, cn ) b (b1,b2 ,,bm )T
a11 a12 a1n
s.t.
a12 y1

a22 y2

am2 ym

c2
a1n y1 a2n y2 amn ym cn

y1, y2 ,, ym 0
对偶问题习惯写为 : min g(Y ) bTY T
ATY T C T s.t.
Y 0
5
2.1.2 (max,)标准型的对偶变换
原问题(max,)
技术系数矩阵 A

价值系数 C

右端项 b

第 i 行约束条件为 型
第 i 行约束条件为 型
第 i 行约束条件为 = 型
决策变量 xj 0

决策变量 xj 0

决策变量 xj 不限

对偶问题(min,)
技术系数矩阵 AT 右端项 b
价值系数 C 对偶变量 yi 0 对偶变量 yi 0 对偶变量 yi 不限 第 j 行约束条件为 型 第 j 行约束条件为 型 第 j 行约束条件为 = 型
9
2.2.2 最优解判别定理
定理 若原问题的某个可行解X0的目标函数值与对偶问题 某个可行解Y0的目标函数值相等，则X0, Y0分别是相 应问题的最优解
证：由弱对偶定理推论1，结论是显然的。

max z c1 x1 c2 x2 cn xn
a11x1 a12x2
a21x1 a22x2
a1nxn ≤ b1 ≤ a2nxn b2
≤
am1x1 am2 x2
amn xn bm
x
j
≥
0
j 1, 2,
,n
min w b1 y1 b2 y2 bm ym
a11 y1 a21y 2
a12
y1
a
22
y
2
a1n y1 a2n y2 yi ≥ 0 i 1, 2,
am1y m ≥ c1 am2xm≥ c2
amn ym ≥ cn ,m
6
第6页/共45页
规范形式下对偶关系的一般形式
max z CX
AX ≤b
X
≥
0
min w Yb YA≥ C Y ≥ 0
7
第7页/共45页
【证】因为X°、Y°是可行解，故有AX°≤b, X°≥0及Y°A≥C， Y°≥0,将不等式 AX°≤b
两边左乘Y°，得Y0AX°≤Y0b
再将不等式Y°A≥C两边右乘X°，得C X°≤Y°AX°
故
C X°≤Y°AX≤Y°b
这一性质说明了两个线性规划互为对偶时，求最大值的线性 规划的任意目标值都不会大于求最小值的线性规划的任一目 标值，不能理解为原问题的目标值不超过对偶问题的目标值。
6
y2
8 y3 y3
≥ ≤
5 4
y1
5 y2
≤9
y1≤0， y2≥0， y3无约束
15
第15页/共45页
线性规划对偶问题的基本性质
下面介绍对偶基本性质时，一般假定是如下规范对偶关系。
设原问题是（记为LP）： 对偶问题是（记为DP）：

3.1 线性规划的对偶模型 Dual model of LP
【例3.2】写出下列线性规划的对偶问 题
max Z (5, 2,3)(x1, x2, x3)T
max Z 5x1 2x2 3x3
4x1x1 7
x2 x2
x3 4 5x3 1
x1, x2, x3 0
4
1
1 7
1
5
x1 x2 x3
min w 36y1 40y2 76y3
3 4
y1 y1
5 y2 4 y2
9 y3 8 y3
32 30
yi 0, i 1, ,3
第4页/共31页
3.1 线性规划的对偶模型 Dual model of LP
max Z 32x1 30x2
3x1 4x2 36 5x1 4x2 40 9x1 8x2 76 x1, x2, x3 0
max Z 4x1 3x2
5x1 x2 6 7x1x1 35x2x2108 x1 0, x2 0
min w 6 y1 8y2 10 y3
5yy1175yy22
y3 3 y3
4
3
yi 0, i 1,2,3
第9页/共31页
线性规划问题的规范形式(Canonical Form 或叫对称形式) ：
下 (界2) ；(D在P)互的为任对一偶可的行两解个的问目题标中是，(LP若)的一最个优问值题的可上行界且； 具有无界解，则另一个问题无可行解；
(3) 若原问题可行且另一个问题不可行，则原问题具 有无界解。
注意: 上述结论(2)及(3)的条件不能少。一个问题无可
行解时，另一个问题可能有可行解(此时具有无界解)
40
8 x3 76

§3.4 线性规划对偶理论
min W 120y1 50 y2
43yy112yy223500 y1 0, y2 0
(3.4-2)
上述问题显然也是线性规划问题。通常称模型(3.4-1)
与模型(3.4-2)互为对偶问题；若称模型(3.4-1)为原问题，
则称模型(3.4-2)为模型(3.4-1)的对偶问题。
因为 Z / xN CN CBB1N ，所以，检验数也可解释为产 品对目标函数的边际贡献，即：增加该产品的单位生产量 给目标函数带来的贡献。
检验数与每一个变量相对应，当线性规划问题达到最 优时，检验数总是小于或等于零(对极大化问题)。这意味
重庆大学经济与工商管理学院 肖智
§3.4 线性规划对偶理论
§3.4 线性规划对偶理论
原问题的最优解为：X*=(15,20)T，最优值为：Z*=1350 对偶问题的最优解为：Y*=(5,15)，最优值为：W*=1350
重庆大学经济与工商管理学院 肖智
§3.4 线性规划对偶理论
THE END
重庆大学经济与工商管理学院 肖智
因此，对于该问题也可考虑另一种经营问题，即出租（或
出让）资源，来获得收入。该问题的关键是确定资源的价
格，特别是要确定资源的价格在什么条件下，使出租（或
出让）资源所获的最少收入与自己生产所获最大收入相同.
为此，不妨假设木工与油漆工的单位工时租金分别为：y1 和y2，可得数学模型如下：
重庆大学经济与工商管理学院 肖智
设X，Y分别是（P）和（D）的可行解， 则CX≤Yb。 定理3.4.3： (对偶定理)（P）和（D）存在以下对应关系: （1）（P）有最优解的充要条件是（D）有最优解； （2）若（P）无界，则（D）不可行； （3）若（D）无界，则（P）不可行；