文档介绍：对偶线性规划
第1页，共35页，编辑于2022年，星期六
一、对偶的定义
原始问题
min z=CTX
. AX≥b
X ≥0
对偶问题
max y=bTW
. ATW≤C
W ≥0
X ≥0
（2）
（3）
（4）
（1）
第10页，共35页，编辑于2022年，星期六
单纯形表和对偶(1)
min z=CTX
. AX-XS=b
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
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页，编辑于2022年，星期六
2、对偶单纯形法（初始解原始不可行的问题）
第19页，共35页，编辑于2022年，星期六
第20页，共35页，编辑于2022年，星期六
第21页，共35页，编辑于2022年，星期六
已获得最优解：
（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页，编辑于2022年，星期六
3、初始解