线性规划的对偶原理共49页文档

Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 + x12+ x13 = 50 x21 + x22+ x23 = 30 x31 + x32+ x33 = 10
s.t
x11 + x21+ x31 = 40
x12 + x22+ x32 = 15
x1


am 2 x2 amn xn x1, x2 , , xn 0

bm

b1,b2 , ,bm 0
右端常数
(3) 线性规划模型矩阵形式
Max Z CX
s.t
AX b

X
0
C c 1 c 2 c n
价值向量
x 1
X


目标函数为极小化 约束条件
分两种情况：大于、小于 决策变量
可能存在小于零的情况
3.2 线性规划问题的基本解
Max Z CX 1
(1) 解的基本概念
s.t

AX
b

2
X 0 3
定义 在线性规划问题中，约束方程组(2)的系
数矩阵A(假定m)的n任意一个 m 阶的m非奇异(可 逆)的子方阵B(即 )，B称为0线性规划问题的一 个基阵或基。
线性规划问题的解有四种情况
唯一最优解 无穷多最优解 无有限最优解 无可行解
若线性规划问题有解，则可行域是一个凸多边形 （或凸多面体）；
若线性规划问题有最优解，则

对偶问题的约束条件 对应于原问题的目标 函数和约束条件的系 数。
对偶问题的可行解集 是原问题可行解集的 凸包。
原问题与对偶问题关系
弱对偶性
对于任意一对原问题和对偶问题 的可行解，原问题的目标函数值 总是大于或等于对偶问题的目标
函数值。
强对偶性
当原问题和对偶问题都存在可行 解时，它们的最优解对应的目标
强对偶性定理
若原问题和对偶问题都有可行解，则 它们分别存在最优解，且这两个最优 解的目标函数值相等。
在满足某些约束规格（如Slater条件） 的情况下，强对偶性成立。
互补松弛条件
在原问题和对偶问题的最优解中，如果某个约束条件的对偶变量值为正，则该约束 条件必须是紧的（即取等号）。
如果原问题（对偶问题）的某个变量在最优解中取正值，则其对应的对偶问题（原 问题）的约束条件必须是紧的。
标准形式
通常将线性规划问题转化为标准 形式，即求解目标函数的最小值 ，约束条件为一系列线性不等式 。
对偶问题定义与性质
对偶问题定义：对于 给定的线性规划问题， 可以构造一个与之对 应的对偶问题，该问 题的目标函数和约束 条件与原问题密切相 关。
对偶问题性质
对偶问题的目标函数 是原问题约束条件的 线性组合。
解决对偶间隙等关键问题
在实际应用中，由于原问题和对偶问题之间可能存在对偶间隙，导致对偶理论的实用性受到一定的限制。 未来可以研究如何缩小或消除对偶间隙，提高对偶理论的实用性和应用范围。
THANKS
感谢您的观看
简化了复杂问题的求解过程
对偶理论能够将一些复杂的线性规划问题转化为相对简单的对偶问题进行求解，从而降低了问题 的求解难度和计算量。
揭示了原问题和对偶问题之间的内在联系

x6 -7 -2 -1 1
RHS
35 5 7 6
已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35 min z=35
3、初始解原始、对偶都不可行的问题
min y=bTW s.t. ATW ≥ C W≥0
引进松弛变量
max z=CTX s.t. AX+XS=b X, XS≥0
max y=bTW s.t. ATW-WS=C W, WS≥0
z
X -CT
XS 0T
RHS 0
max s.t. AX+XS=b X, XS≥0 min y=bTW s.t. ATW-WS=C W, WS≥0 WT=CBTB-1 WST=WTA- CT
x4 0 1 0 0
x5 0 -1
x6 -5 2 -1 -3
2 2 -7 2
RHS
30 -5 7 16
z z x1 x2 x3 1 0 0 0
x1 0 1 0 0
x2 0 0 1 0
x3 0 0 0 1
x4 -1 -1 0 2
x5 -5 -1 -1 0
min z=CTX s.t. AX=b X ≥0 min z=CTX s.t. AX≤b X ≥0
max y=bTW s.t. ATW≤C W ≥0 max y=bTW s.t. ATW≤C W ：unr max y=bTW s.t. ATW≤C W ≤0
三、原始对偶关系
1、可行解的目标函数值之间的关系
n n m XS
X
m W

对偶变换的规则
原问题(或对偶问题)
目标函数 maxz 变量： n 个
≥0 ≤0 无约束
约束条件：m 个 ≤ ≥ =
约束条件右端项 目标函数变量系数
对偶问题(或原问题)
目标函数 minω
约束条件：n 个
≥
≤ =
变量： m 个
≥
≤ 无约束
目标函数变量系数
约束条件右端项
原问题与对偶问题的结构关系
（1）标准对称式的线性规划问题的对偶仍是标准对称式；
偶问题:
min
W
Y1
,
Y2
b
b
min W (Y1 Y2 )b
s.t.(Y1
,
Y2
)
A A
C
s.t.(YY11,
Y2 Y2
)A 0
C
Y1 , Y2 0
令Y=Y 1 - Y 2 因为Y 1 ,Y 2 ≥0, 所以Y为不受正负约束的变量
min
W Yb YA C
s.t . Y为 无 约 束 的 变 量
y2 y3
解：
x1 0, x2 0, x3取 值 无 约 束
min s.t.
b1 y1 b2 y2 b3 y3
a11 y1 a21 y2 a31 y3 c1
a12 y1 a22 y2 a32 y3 c2 a13 y1 a23 y2 a33 y3 c3
y1 0, y2取 值 无 约 束, y3 0
（2）原问题与对偶问题中的目标函数的优化方向相反 （一个为极大，另一个就为极小）；
3x1 2x2 2x2 20
s.t.
4x1
3x2 3x2 x1 x2 x2
10 5
x1 x2 x2 5

特点：
1． max min 2．限定向量b 价值向量C
其它形式 的对偶
?
（资源向量）
3．一个约束 一个变量。
4． max z的LP约束“ ” min z 的
LP是“ ”的约束。
5．变量都是非负限制。
二、原问题与对偶问题的数学模型
❖ 1．对称形式的对偶
当原问题对偶问题只含有不等式约束
时，称为对称形式的对偶。
根据对称形式的对偶模型,可直接 写出上述问题的对偶问题:
b max w (Y 1,Y 2 ) -b
(Y
1,Y
2
)
A A
C
Y1 0 ,Y2 0
max w (Y 1 Y 2 ) b
(Y
1
Y
2
)
A
C
Y 1 0, Y 2 0
令 Y Y，1 Y得2对偶问题为：
max w Yb
❖ （3）若原问题可行，但其目标函数值无 界，则对偶问题无可行解。
❖ （4）若对偶问题可行，但其目标函数值 无界，则原问题无可行解。
❖ （5）若原问题有可行解而其对偶问题无 可行解，则原问题目标函数值无界。
❖ （6）对偶问题有可行解而其原问题无可 行解，则对偶问题的目标函数值无界。
CX Yb
原问题
设备A 设备B 调试工序
产品Ⅰ 产品Ⅱ
0
5
6
2
1
1
利润（元） 2
1
D
15时 24时 5时
x 设 Ⅰ产量––––– 1
x Ⅱ产量––––– 2
如何安排生产， 使获利最多？
max z 2 x1 x2
s.t.
5x2 15
6 x1 2 x2 24

min z=CTX
max w=bTY s.t. ATY≤C Y ≥0
max w=bTY s.t. ATY≤C Y ：无约束
s.t.
AX≤b X ≥0
max w=bTY s.t. ATY≤C Y ≤0

例2 写出下列线性规划的对偶问题
max z x1 2 x 2 x3 x1 x 2 x3 2 x x x 1 2 3 s.t. 1 2 x1 x 2 x3 2 x1 0; x 2 , x3 无约束
*
*
*
*
4、无界性：若线性规划问题（4.2.1）的目标函数无上界， 则问题（4.2.2）无可行解；若问题（4.2.2）的目标函数 无下界，则问题（4.2.1）无可行解． 5、对偶定理：若问题（4.2.1）和（4.2.2）之一有最优解， 则另一个也有最优解，并且目标函数值相等．
1、对称性：对偶问题的对偶是原始问题．
min z=CTX s.t. AX≥b X ≥0
对偶的定义
max w=bTY s.t. ATY≤C Y ≥0
max z’=-CTX
s.t. -AX≤-b X ≥0
对偶的定义
min w=-bTY s.t. -ATY≥-C Y ≥0
2、弱对偶性：若 X 为问题
max z C T X AX b s.t. X 0
第四章 线性规划的对偶原理
线性规划的对偶性
对于线性规划的最大值问题，都相应存在着一个特 定的包含同样数据的最小值问题．也就是说，一个问题 可以从两个不同的方面提出：一个方面是在一定的资源 条件下，如何最合理地规划使用这种资源，使得完成的 任务量最大；另一个方面是根据已确定的任务如何规划 使用资源，使得消耗的资源为最少．这样的问题可以看 作是从两个不同的角度对同一个问题所进行的分析与研 究，是根据同样的条件与数据所构成的两个问题．它们 之间的关系是相对的，通常称一个问题是另一个问题的 对偶问题．如果把前者称为原始问题，后者就叫做对偶 问题．反之，如果把后者称为原始问题，前者就叫做对 偶问题，两者互为对偶．这便是线性规划的对偶性．

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）：

这表明， 从不同角度考虑同一问题可得 到相互联系的线性规划模型，这就是线性规划 的对偶问题 。
一般地，称线性规划问题（I) 和(Ⅱ)互为 对偶问题的标准形式。
（I)
max Z CX AX b X 0
(Ⅱ)
min W Yb YA C Y 0
①对偶问题的变换关系为对称关系时， 根据原问题的系数矩阵就能容易地写出对偶问 题。如表5.2.1。
min W 2 x1 3 x 2 4 x3 x 2x x 3 1 2 3 2 x1 x 2 3x3 4 x1 , x 2 , x3 0
首先将该问题化为
max Z 2 x1 3 x2 4 x3 x 2 x x x 3 1 2 3 4 2 x1 x2 3 x3 x5 4 x j 0, j 1,2, ,5
二、原问题与对偶问题的关系
线性规划原问题与对偶问题之间的形 式变换关系可以由表5.2.2予以概述。
表5.2.2
原问题（或对偶问题）
目标函数 变 量 约 束 方 程 对偶问题（或原问题） 目标函数 约 束 方 程 变 量
max Z
个数n ≥0 ≤0 无约束 个数m ≤ ≥ =
min W
个数n ≥ ≤ = 个数m ≥0 ≤0 无约束
①对称性：即对偶问题的对偶是原问题。 ②弱对偶性：即若 X 是原问题的可行解， Y 是对偶问题的可行解，则存在关系： X Yb 。 C
③无界性：若原问题（对偶问题）为无界 解，则其对偶问题（原问题）无可行解。 ④对偶定理：若原问题有最优解，那么对 偶问题也有最优解，而且它们的最优目标值相 等。
⑤松紧定理：若 X 和 Y 分别为原问题与对 偶问题的可行解，则它们为最优解的充要条件为

（3）（LP）问题目标函数的价值系数C，在（ LD ）问题 中为约束条件右端函数。
（4）（LP）问题约束条件右端常数，在（ LD ）问题中 为目标函数价值系数。
（5）（LP）问题约束条件系数矩阵转置，在（ LD ）问 题中为约束条件系数矩阵。
（6）（LP）问题决策变量为大于等于0，在（ LD ）问题 中约束条件符号为“≤”，且变量个数恰好为（ LD ） 约束条件个数。

管理运筹学
12
用矩阵可表示为
min Z cx
maxW wb
s.t.xAx 0 b
wA c s.t.w 0
• 其中
C (c1, c2 , , cn ), X (x1, x2 , , xn )T A (aij )mxn,b (b1,b2 , ,bm )T ,
束
≤
条
≥
件
=
≥0
量
≤0
无符号限制
变 n个变量
量
≥0
≤0
无符号限制
n个约束条件
约
≥
束
≤
条
=
件
目标函数价值系数
约束条件右端常数
约束条件右端常数
目标函数价值系数
系数矩阵 A
系数矩阵转置AT
例2.3写出下列线性规划的对偶规划
• minz=2x1-x2+x3-3x4
• s.t.x1+2x2
+4x4=1
•
2x2-3x3 -4x4≤2
minG=24w1+26w2 2w1+3w2≤4 3w1+2w2≥3 w1,w2 ≥0
例2.2 假如某种作物，全部生产过程至 少需氮肥32公斤，磷肥24公斤，钾 肥42公斤已知甲乙丙丁四种复合肥 料每公斤的价格以及氮磷钾的含量 如表？