文档介绍：对偶线性规划
第1页，本讲稿共35页
一、对偶的定义
原始问题
min z=CTX
. AX≥b
X ≥0
对偶问题
max y=bTW
. ATW≤C
W ≥0
≥
min
X, XS≥0
max y=bTW
. ATW+WS=C
W, WS≥0
min z=CTX
. AX≥b
X ≥0
max y=bTW
. ATW≤C
W≥0
对偶问题
原始问题
引进松弛变量
引进松弛变量
第11页，本讲稿共35页
min z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W, WS≥0
WT=CBTB-1
WST=CT-WTA
第12页，本讲稿共35页
min z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W ≤0, WS≥0
min z=CTX
. AX ≤ b
X ≥0
max y=bTW
. ATW≤C
W ≤ 0
单纯形表和对偶(2)
对偶问题
原始问题
引进松弛变量
引进松弛变量
第13页，本讲稿共35页
min z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W ≤0, WS≥0
WT=CBTB-1
WST=CT-WTA
第14页，本讲稿共35页
max z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW-WS=C
W ≤0, WS≥0
max z=CTX
. AX ≥ b
X ≥0
min y=bTW
. ATW ≥ C
W ≤ 0
单纯形表和对偶(3)
对偶问题
原始问题
引进松弛变量
引进松弛变量
第15页，本讲稿共35页
max z=CTX
. AX-XS=b
X, XS≥0
min y=bTW
. ATW-WS=C
W ≤0, WS≥0
WT=CBTB-1
WST=WTA- CT
第16页，本讲稿共35页
max z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW-WS=C
W, WS≥0
max z=CTX
. AX ≤ b
X ≥0
min y=bTW
. ATW ≥ C
W ≥ 0
单纯形表和对偶(4)
对偶问题
原始问题
引进松弛变量
引进松弛变量
第17页，本讲稿共35页
max z=CTX
. AX+XS=b
X, XS≥0
min y=bTW
. ATW-WS=C
W, WS≥0
WT=CBTB-1
WST=WTA- CT
第18页，本讲稿共35页
2、对偶单纯形法（初始解原始不可行的问题）
第19页，本讲稿共35页
第20页，本讲稿共35页
第21页，本讲稿共35页
已获得最优解：
（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35
对偶问题的最优解为：
（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35
第22页，本讲稿共35页
3、初始解原始、对偶都不可行的问题
第23页，本讲稿共35页
解法1：先解决原始可行性
第24页，本讲稿共35页
第25页，本讲稿共35页
在得到原始可行解时同时得到对偶可行解，已获得最优解：
（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17
对偶问题的最优解为：
（w1, w2, w3, w4, w5, w6）=（-7, 5,