则，原问题变为
（A）
max Z 4x1 5x2 s.t.
3x1 2x2 20
4x1 3x2 10
x1 x2 5
x1

0,
x
为自由
2
变量
max Z ' 4x1 5x3 5x4 s.t.
（A‘）
3x1 2x3 2x4 20 4x1 3x3 3x4 10 x1 x3 x4 5 x1 x3 x4 5 x1 0, x3 0, x4 0
max Z 4x1 5x2 s.t. 3x1 2x2 20 4x1 3x2 10 x1 x2 5 x1 0, x2为自由变量
4x1 3x2 10
xx11

x2 x2

5 5
x1 x2 5
设x 2 x 3 x 4 , x3 0, x 4 0
X 0
minW YB s.t. （B） YA C T Y 0
其中： C c1 c2 cn
Y y1 y2 ym
b1
B


b2 bm
a11 a12 a1n
A


a21 an1
a22 am2
a12 y1 a22 y2 am2 ym c2



a1n y1 a2n y2 amn ym cn y1 0, y2 0, ym 0
称为原问题（A）的对偶线性规划问题，
或称A、B互为对偶问题。
如果采用向量、矩阵来表示
max F CX
s.t. （A） AX B
min W ' 20 y1 '10 y2 '5 y3 '5 y4 ' s.t. 3 y1 '4 y2 ' y3 ' y4 ' 4 2 y1 '3y2 ' y3 ' y4 ' 5 2 y1 '3 y2 ' y3 ' y4 ' 5 y1 ' 0, y2 ' 0, y3 ' 0, y4 ' 0
当原问题的约束条件的符号不完全相同时，也存在 对偶问题，这种对偶问题称为非对称对偶问题。
例
max Z 4x1 5x2 s.t.
3x1 2x2 20
4x1 3x2 10
x1 x2 5
x1

0,
x
为自
2
由
变
量
分析：
为求对偶问题，可先做过渡，将问题对称化：
对称化
则（A’）的对偶问题如下：
（A‘）
（B‘）
max Z ' 4x1 5x3 5x4 s.t. 3x1 2x3 2x4 20 4x1 3x3 3x4 10 x1 x3 x4 5 x1 x3 x4 5 x1 0, x3 0, x4 0
∴ 对偶规划问题为
min W 48y1 60 y2 s.t. y1 y2 6 4 y1 2 y2 14 2 y1 4 y2 13 y1 0, y2 0
比较
max F 6x1 14x2 13x3 s.t. x1 4x2 2x3 48 x1 2x2 4x3 60 x1 0, x2 0, x3 0
a2n

amn

x1
X

x2

xn
可以将以上关系列成以下对偶表：
max min
x1
x2
…
xn
b
y1
a11
a12
…
a1n
≤
b1
y2
a21
a22
…
≤
b2
…
………………
ym
am1
am2
…
amn
≤
bm
≥≥…≥
c
c1
c2
…
cn
例
写出下列线性规划问题的对偶问题
第四章 对偶问题
对偶问题的一般形式 对偶问题的经济意义 对偶性质 对偶单纯形法 对偶单纯形法的解题原理
一、对偶问题的一般形式
若设一线性规划问题如下 ：
（A）
max F c1x1 c2 x2 cn xn s.t.
a11 x1 a12 x2 a1n xn b1
a21 x1 a22 x2 a2n xn b2



am1 x1 am2 x2 amn xn bm x1 0, x2 0, xn 0
则以下线性规划问题：
（B）
minW b1 y1 b2 y2 bm ym s.t.
a11 y1 a21 y2 am1 ym c1
min W 48y1 60 y2 s.t. y1 y2 6 4 y1 2 y2 14 2 y1 4 y2 13 y1 0, y2 0
以上我们介绍的对偶问题是严格定义的对偶问题，也 成为对称对偶问题 。
它满足两个条件：
两个条件：
1、所有变量非负：即X>0，Y>0 2、约束条件均为同向不等式。若原问题约束条件均 为“≤”，则它的对偶问题的约束条件都是“≥”。
max F 6x1 14x2 13x3 s.t. x1 4x2 2x3 48 x1 2x2 4x3 60 x1 0, x2 0, x3 0
解：
可以将原问题的有关参数列成下表
max
min
x1
x2
x3
b
y1
1
4
2
≤
48
y2
1
2
4
≤
60
≥
பைடு நூலகம்
≥
≥
c
6
14
13
对比结果
以上对偶问题（B‘）并非原问题（A）的对偶问题， 它是线性规划问题（A’）的对偶问题。
（A）
max Z 4x1 5x2 s.t. 3x1 2x2 20 4x1 3x2 10 x1 x2 5 x1 0, x2为自由变量
（B‘）
min W ' 20y1 '10y2 '5y3 '5 y4 ' s.t. 3y1 '4 y2 ' y3 ' y4 ' 4 2 y1 '3y2 ' y3 ' y4 ' 5 2 y1 '3y2 ' y3 ' y4 ' 5 y1 ' 0, y2 ' 0, y3 ' 0, y4 ' 0