- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
可行解Y =(2, 1, 0)T, w =20
4. 强对偶性
对偶定理 若原问题有最优解，则其对偶问题也具有最优解，且 两者的最优解对应的目标函数值相等。
设X*为原问题的最优解，对应的最优基为B，
X B X 0
XB B 1b, z C B B 1b
Y * ( y1* , y2* )T , 因 x1* , x2* 0, 由互补松弛性知 y1* 2 y2* 3 2 y1* 2y2* 4 * * 解方程组得 y1 1, y2 1, 故对偶问题的最优解为 Y * (1,1)T , w* 26.
例7.3：利用互补松弛定理求最优解
* * y y 由互补松弛性知 1 2 0, 又 5 y1* 6y2* y3* 3 * 得 y3 3, 故对偶问题的最优解为
Y * (0,0,3)T , w* 12.
例7.4 利用互补松弛定理求最优解
min z 2 x1 3x2 5x3 2 x4 3x5 s.t. x x 2 x x 3x 4 1 2 3 4 5 2 x1 x2 3x3 x4 x5 3 x 0, j 1, 2, ,5 j 设原问题的最优解为 X , 对偶问题为 max w 4 y1 3 y2 s.t. y1 2 y2 2 (1) y y 3 (2) 2 1 (3) 2 y1 3 y2 5 (4) y1 y2 2 3 y1 y2 3 (5) y1 , y2 0
X，Xs
min w=bTY s.t. ATY-YS= CT Y, YS≥0
Y，Ys
(X)T YS=0
(Y)T XS=0
互补松弛关系
Y X S 0
T
yx
i 1 n
m
i Si
0
X
T
YS 0
y
j 1
Sj
xj 0
由于所有的变量均为非负，要使求和式等于零，则每 一个分量必定为零，从而有下列关系成立：
求对偶问题的最优解。
min w 2 y1 y2 4 y3 s.t. 2 y1 3 y2 y3 1 3 y1 y2 y3 4 5 y1 6y2 y3 3 y1 0, y2 0, y3无约束
将 X * 代入原问题约束条件得
2 x1* 3x2* 5 x3* 20 2 * * * 3x1 x2 6 x3 24 1 * * * x x x 44 1 2 3
T T
1
T
C B B 1b z
由最优性定理，Y是对偶问题的最优解。
推论：对偶解定理
若用单纯形法解原问题 LP，得有最优解X*，相应的最 优基为 B，则
Y*=(CB B-1)T
为其对偶问题DP的最优解
原问题的检验数与对偶问题的解之间的对应关系
原问题(LP) 对偶问题(DP)
max z CX AX b s.t. X 0
原问题(对偶问题)最优解中某一个分量 = 0 对偶问题(原问题) 中该分量对应的约束以等式成立 以最优解代入原问题(对偶问题)的约束条件，为严 格不等式(松弛变量 = 0) 对偶问题(原问题) 的最优解中该约束条件的对应分 量=0
例7.2：利用互补松弛定理求最优解
max z 3x1 4 x2 x3 s.t. x1 2 x2 x3 10
CB XB CB XB B-1B 0
CN XN B-1N
0 XS B-1I B-1b
检验数
CN - CBB-1N - CBB-1
-YS1T
-YS2T
-Y T
在用单纯形法求解原问题的过程中，每一步中间迭代过 程的检验数行对应于其对偶问题的一个基本解(但不可 行)；只有当原问题达到最优解时，其检验数行对应于 其对偶问题的一个基本可行解，并且该基本可行解即为 其对偶问题的最优解。
yi 0 xSi 0
ySj 0 x j 0
xSi 0 yi 0
x j 0 ySj 0
原问题、对偶问题的最优解与松弛变量之间的关系
yi 0 xSi 0
ySj 0 x j 0
xSi 0 yi 0
x j 0 ySj 0
x 2x 8 1 2 x2 3 x1 , x2 0
DP min w 6 y1 8 y2 3 y3 s.t. y1 y2 3 一对对偶问题
y1 2 y2 y3 4 y , y , y 0 1 2 3
可行解X=(1, 2)T, z=11
第7讲 对偶理论与灵敏度分析II
7.1 对偶问题的基本性质 7.2 对偶解的经济含义——影子价格
7.3 对偶单纯形法
7.1 对偶问题的基本性质
对称性
弱对
对称性定理：对偶问题的对偶是原问题。
max z = CX s.t. AX ≤ b X ≥0
max z x1 4 x2 3x3 s.t. 2 x1 3x2 5 x3 2 3x x 6 x 1 1 2 3 x1 x2 x3 4 x1 0, x2 0, x3无约束 已知原问题的最优解是
X * (0,0, 4)T
可行解Y =(1, 2, 1)T, w =25
3. 最优性
最优性定理
若 X 和 Y 分别是原问题和对偶问题的可行解，且有
z CX bT Y w
则 X 和 Y 分别是原问题和对偶问题的最优解。
证明：设X为LP的任一可行解，由弱对偶定理
CX bT Y
因为
CX bT Y ，所以，对于LP的任一可行解X，有 CX CX
T
or
yx
i 1 n
m
i Si
0
y
j 1
Sj
xj 0
x1 x2 X : xn n1
xS 1 x XS S2 : xSm m1
y1 y2 Y : ym m1
利用原问题的最优单纯形表求对偶问题最优解
c
c cBs B 0B c x xBs B
cB xB
I B x xB s
cN xN
B-1 NN
-1N cN - c B c B N
0 xs
B I-1
-1 -c0 B B
b
-1b Bb
检验数
0B c
-cB0 B-1b
Y*=(CBB-1)T
例 7.1 求如下 LP 问题的对偶问题的最优解 max z = 4x1+3x2+7x3 s.t. x1+2x2+2x3 ≤100 3x1+ x2+3x3 ≤100 x1 , x 2 , x 3 ≥ 0 解： 对偶问题为 c
BT C B 1 T Y C T YSB 0 B SB B T 1 T T 1 T Y C C B N N CB B YSN CN SN N B
-YSB T
-YSN T
-Y T
兼容性定理：原问题的检验数对应于对偶问题的一个基本解
T T T
A Y C X A Y X C CX AX Y CX
T T T T T T T
根据弱对偶定理： 极大化问题(原问题)任一可行解对应的目标函数值不可 能超过其对偶问题任一可行解对应的目标函数值。
生产安排问题 资源定价问题
LP
max z 3x1 4 x2 s.t. x1 x2 6
对偶问题
min w = bTY s.t. ATY ≥CT Y≥0
min z = － CX s.t. － AX ≥－ b X≥ 0
对偶问题
max w = － bTY s.t. － ATY ≤－ CT Y≥0
2. 弱对偶性
原问题(LP) 对偶问题(DP)
max z CX AX b s.t. X 0
min w bT Y AT Y C T s.t. Y 0
min w bT Y
T T B, N Y YS CB , CN s.t. Y , YS 0
max z CB X B CN X N 0 X S BX B NX N IX S b s.t. XB, XN , XS 0
原问题的最优解和最优值为：
x*=(0,25,25)T
z*=250
由对偶解定理可知： w*= 250
对偶问题的最优解和最优值为 y*= (1/2 , 2)T
5. 互补松弛性
互补松弛定理 LP的可行解 X 与 DP的可行解 Y 是最优解的充分必要条件是：
Y X S 0
T
X YS 0
yS 1 y YS S 2 : ySn n1
LP问题和DP问题最优解之间的互补松弛关系图解
max z=CX s.t. AX ≤ b X ≥0
引进松弛变量
对偶
min w=bTY s.t. ATY ≥ CT Y≥0
引进剩余变量
max z=CX s.t. AX+XS=b X, XS≥0
min w bT Y BT Y YSB CBT T s.t. N Y YSN C N T Y , Y , Y 0 SB SN
min w bT Y
max z CB X B CN X N 0 X S BX B NX N IX S b s.t. XB, XN , XS 0
由于X*为原问题的最优解，必定所有的检验数小于等于零， 即 1
