表 3-5

可以证明，原线性规划问题的对偶问题具有以下基本性质：

（1)对称性。即对偶问题的对偶是原问题。

（2）弱对偶性。即若X是原问题的可行解，Y是对偶问题的可行

解，则存在如下关系：

cX≤Yb

（3)无界性。若原问题（对偶问题)为无界解，则其对偶问题（原问题) 无可行解。

（4)对偶定理：若原问题有最优解，那么对偶问题也有最优解，而且它们的最优目标值相等。

（5)松紧定理：若 X^*与 Y^*分别为原问题与对偶问题的可行解，则它们为最优解的充要条件为 cX^*=Y^*b

（6)设原问题是

它的对偶问题是

maxZ = cX

AX + Xs = b

X≥0，Xs≥0

minW = Yb

YA - Ys = c

Y≥0，Ys≥0

则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下表（表 3-6)。

表 3-6

∧ ∧

（7）互补松弛性。若X 和Y 分别是原问题和对偶问题的可行解。

∧ ∧ ∧ ∧

那么Y Xs = 0和Ys X = 0，当且仅当X 和Y 为最优解。

三、对偶单纯形法

由线性规划原问题与对偶问题的解之间的关系可知，在单纯形表中进行迭代时，在 b 列中得到的是原问题的基可行解，而在检验数行中得到的是对偶问题的基解。通过逐步迭代，当在检验数行中得到对偶问题的解也是基可行解时，则它就是最优解，这时原问题与对偶问题都是最优解。

根据对偶问题的对称性，我们也可以这样考虑问题：若保持对偶问题的解是基可行解，即 Cj-CBB^-1Pj≤0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得到了最优解。这种思路就是对偶单纯形法求解线性规划的思想。这种方法的优点是原问题的初始解不一定是基可行解， 可从非基可行解开始迭代。对偶单纯形法的基本原理如下：

对于原问题

max Z = OX

AX = b

X≥0

设 B 是一个基，不失一般性，令 B=[P1，P2，⋯，Pm]，它的应基变量为XB=[x1，x2，⋯，xm]。当非基变量都为零时，可以得到 XB=B^-1b。若在 B^-1b 中至少有一个负分量，设（B^-1b)i＜0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是

（1)对应基变量 x1，x2，⋯，xm 的检验数是

σi=Ci-Zi=Ci-CBB^-1Pi=0，i=1，2，⋯，m

（2)对应非基变量 xm+1，⋯，xn 的检验数是

σj=Cj-Zj=Cj-CBB^-1Pj≤0，j=m+1，⋯，n

每次迭代是将基变量中的负分量 x1 取出，去替换非基变量中的 xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。

对偶单纯形法的计算步骤如下：

（1)根据线性规划问题，列出初始单纯形表，检查 b 列中的各分量，若都为非负，且检验数都为非正，则已得到最优解，停止计算。若 b 列中至少有一个负分量，检验数保持非正，则需要进行以下计算。

（2)确定换出变量。按照法则

min｛（B^-1b） ｜（B b） ＜0｝ = （B^-1b）

i i -1 i l

确定对应的基变量 xl 为换出变量。

（3)确定换入变量。在单纯形表中检查 xl 所在行的各系数 alj（j=1， 2，⋯，n)，若所有 alj≥0，则无可行解，停止计算。若存在 alj＜0（j=1，2，⋯， n)，计算

C j − Z j

θ = min a lj

＜0 = C_k − Z_k

j 

alj

 a lk

按θ规则所对应的列的非基变量 xk 为换入变量，这样以保持得到的对偶问题的解仍为可行解。

（4)以 alk 为主元素，按原单纯形法在表中进行迭代运算，得出新的单

纯形表。

（5)重复（1)—（4)的步骤，直止求得最优解。例 2：试用对偶单纯形法求解如下线性规划问题

minW = 2x1 + 3x2 + 4x3

x + 2x + x ≥3

 1 3

2x - x + 3x≥4

 1 2

x1 ，x2 ，x3 ≥0

解：首先将这一问题化成下列型式，以便得到对偶问题的初始可行基。

maxZ = -2x₁ - 3x₂ - 4x₃

- x - 2x - x + x = -3

 1 2 3 4

- 2x + x - 3x + x = -4

 1 2 3 5

x j ≥0，j = 1，2， ，5

该问题的初始单纯形表，如表 3-7 所示。

表 3-7

从表 3-7 看到，检验数行对应的对偶问题的解是可行的。因为 b 列各分量均为负，所以需要进行迭代运算。

换出变量的确定：按照前述对偶单纯形法计算步骤（2)，计算可得

min｛（B^-1b） ｜（B^-1b） ＜0｝

i i i

=min｛-3，-4｝=-4 故 x5 为换出变量。

换入变量的确定：按照前述对偶单纯形法计算步骤（3)，计算可得

  − 2 − 4 

θ = m a_lj＜0 = min , 

= − 2 = 1

− 2

  − 2

− 3

故 x1 为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。按单纯形法计算步骤进行迭代运算，得表 3-8。

表 3-8

由表 3-8 看出，对偶问题仍是可行解，而 b 列中仍有负分量，故还需进行迭代运算。重复上述迭代步骤，得到表 3-9。

表 3-9

在表 3-9 中，b 列各分量全为非负，检验数全为非正，故问题的最优解为 X^*=[11/5，2/5，0，0，0]^T，而其对偶问题的最优解为 Y^*=[8/5，1/5]。