第二节 线性规划的对偶理论

一、对偶问题的提出

对于本章第一节中所介绍的资源利用问题

 n

max Z = ∑cj x j

(1)

 j=1

 n

∑aij x j ≤bi (i = 1, 2, , m) (2)

 j=1

x ≥0( j = 1,2, , n) (3)

 j



我们也可以从另一个角度去作这样的考虑，即资源拥有者为了实现一定的收入目标，他可以不用这 m 种资源去生产 n 种产品，而是将其所拥有的资源出售。这时，他就必须考虑给每一种资源如何定价的问题。

如果用 yi（i=1，2，⋯，m)表示出售单位数量的第 i 种资源的价格。显然，资源拥有者在作出出售资源的决策时，必须考虑到：出售资源的收入不应该低于生产所获得的收入，这样就有：

m

∑ aij yi ≥c j ( j = 1, 2, n)

i=1

显然 yi≥0（i=1，2，⋯，m)

如果资源拥有者将所有资源出售，则他得到的总收入为

W = ∑bi yi i=1

对于资源拥有者来说，他当然希望 W 愈大愈好；但对于资源接受者来说， 他当然希望 W 愈小愈好。所以，资源拥有者出售每一种资源的最低估价，应该通过求解线性规划问题而得到。

 m

minW = ∑bi yi

(4)

 i=1

 m

∑aij yi ≥c j ( j = 1,2, , n) (5)

 i=1

y ≥0(i = 1,2, , m) (6)





上述讨论表明，对于同样一个资源利用问题，从两个不同的角度去考虑， 可以得到两个不同但又相互联系的线性规划模型，这就是线性规划的对偶问题。其中，（1)—（3)称为原线性规划问题，（4)—（6)称为原线性规划问题的对偶线性规划问题。

一般地，称线性规划问题

max Z = CX

(Ⅰ  ≤b

)AX

X≥0

与线性规划问题

minW = Yb

(Ⅱ  ≥C

)YA

Y≤0

为相互对偶的线性规划问题。这就是说，如果将（Ⅰ)看作原问题，则（Ⅱ) 为其对偶问题；反之，如果将（Ⅱ)看作原问题，则（Ⅰ)为其对偶问题。

（Ⅰ)与（Ⅱ)是线性规划原问题与对偶问题的标准形式，它们之间的变换关系是对称形式（如表 3-4 所示)。因此，根据原问题的系数矩阵就能很容易地写出它的对偶问题。

表 3-4

当原问题的约束条件中含有等式约束方程时，原问题与其对偶问题之间的变换关系就是非对称形式了。这时，对偶问题的求法可按以下步骤进行：

（1)首先将原问题的约束条件中的每一个等式约束方程都用两个不等式约束方程代替，从而使原问题的约束条件中的所有约束方程都变为同号不等式约束。

（2)按对称形式变换关系（表 6-4)写出它的对偶问题。譬如 对于线性规划问题

 n

max Z = ∑c jx j

 j=1

 n

∑aij x j = b i (i = 1, 2, , m)

 j= 1

x ≥0 ( j = 1, 2, , n)

 j



可以按下述步骤求出其对偶问题：

第一步，将约束条件中的每一个约束方程（等式约束)都分解为两个不等式约束方程。这样，上述线性规划问题就可表示为

 n

max Z = ∑cj x j

(7)

 j=1

 n

∑aij x j ≤b

 j= 1

(8)

 n

∑(−a ij )x j≤ − b

j= 1

(9)

x ≥0( j = 1, 2,

n) (10)

 j

第二步，设y^′ 和y ^″ （i = 1，2， ，m）分别代表对应于（8）式和

（9)式的对偶变量，则可以按对称形式变换关系（表 6-4)写出它的对偶问题

 m m

minW = ∑b y^′ + ∑(−b y ^″ )

 i=1

 m m

i=1

∑a y^′ + ∑(−a y ^″ )≥c

( j = 1,2, , m)

 i=1

i=1

y^′ ≥0, y ^″ ≥0 (i = 1 2, , m)

 i i



上述线性规划问题的各式，经过整理后得到：

 m

minW = ∑b (y ^′ − y^″ )



m

∑a

 i=1

i=1

( y^′ − y^″ ) ≥c

( j = 1,2, , n)

y^′ ≥0, y^″ ≥0

(i = 1,

2, , m)

 i i



令y = y^{′ − y″ ，由于y′ ≥0，y″ ≥0，可见y 不受正、负限制，将yi代}

i i i i i i

入上述线性规划问题，便可得到原线性规划问题的对偶问题

 m

minW = ∑bi yi

i=1

m

∑ aij yi ≥c j ( j = 1,

2, , n)

yi (i = 1, 2, , m)无约束

二、原问题与对偶问题的关系

综上所述，线性规划原问题与对偶问题之间的形式变换关系可以由表3-5 予以概述。

利用表 3-5 所描述的形式变换关系，我们可以写出任何一个线性规划问题的对偶问题。譬如，对于线性规划问题

minZ = 2x1 +



3x2 − 5x3 + x4

 x1 + x2 − 3x 3 + x4 ≥5

 2x +

2x − x ≤4

 1 3 4

 x + x + x = 6





其对偶问题为

x1 ≤0;

x2 ,

2 3 4

x3

≥0; x4 无约束

max Z′ = 5y1 + 4y2 + 6y3

 y + 2y ≥2

 1 2

 y1 + y 3≤3

 − 3y + 2y + y ≤ − 5

 1 2 3

 y − 2y + y = 1

 1 2 3

 y1 ≤0, y 2 ≥0, y 3无约束