利用对偶理论求解线性规划问题的策略探讨

赵芹，章舜哲，刘慧清，雷琪

(湖北大学数学与统计学学院，应用数学湖北省重点实验室， 湖北 武汉 430062)

0 引言

对偶理论是线性规划问题中非常重要的内容之一. 它反映出每一个线性规划问题必然与之相伴而生另一个线性规划问题，并揭示了两者之间的密切关系. 如何利用对偶理论求解线性规划问题是教学中的重点及难点之一. 然而，学生在练习中往往不能很好地根据线性规划问题的不同类型来灵活选择合适的互补松紧条件建立方程. 文献[3]中关于具有唯一最优解的多个变量两个约束条件的线性规划问题，给出了利用图解法来求解；文献[4]中则在此基础之上，对于一般的多个变量两个约束条件的线性规划问题，给出了结合互补松弛条件及图解法来求解的方法. 本研究从例子出发，详细探讨利用对偶理论来解线性规划问题的多种思路，以期使学生能够更好地掌握这一重要理论并灵活运用.

给定一个线性规划问题

其对偶问题为

则原始的LP问题及其对偶问题之间有如下关系.

定理1.1[1]如果一个线性规划问题有最优解，则其对偶问题也有最优解，且它们的最优值相等.

定理1.2[1](互补松弛定理)设x和w分别是原始和对偶问题的可行解，则它们分别是原始和对偶问题的最优解的充要条件是：对一切i=1, 2, …,m和j=1, 2, …,n有

(1.1)

vj=(cj-wTAj)xj=0

(1.2)

定理1.2中的 (1.1) 式说明，如果原始问题中的一个约束条件取严格不等式，即是“松的”，则对偶问题的最优解中对应的分量必为0，即为“紧的”；(1.2) 式说明，如果原问题的最优解中某个非负变量取正(松)，则对偶问题中相应的约束条件必取等号(紧).

因此，定理1.2可得到以下推论.

推论1.3[2]设两个互为对偶的线性规划都有可行解，若原规划某一约束是某个最优解的非临界约束，则它的对偶约束一定是对偶规划所有最优解的临界约束.

1 解题策略及例子

利用互补松弛定理求线性规划问题的最优解是教学的重点及难点之一. 在课堂教学中我们发现，这类问题可以分为以下两类情形：

1) 原线性规划问题最优解中的正分量的个数大于等于约束条件的个数.

一般情况下，这类问题常常仅需要利用互补松弛定理中的 (1.2) 式就能列出方程组，从而得到最优解.

例1已知下列线性规划问题的最优解为x*=(2,2,4,0)T，试求其对偶问题的最优解.

解原问题的对偶线性规划问题为

2) 原问题的最优解中正分量的个数小于约束条件的个数.

这类问题常常需要同时考虑互补松弛定理中的 (1.1) 式和 (1.2) 式. 先通过 (1.2) 式列出对偶问题中相应的条件约束方程组，由于该方程的个数小于变量的个数，因此还需要利用(1.1) 式找到对偶问题最优解中的零分量，从而得到最优解.

例2若在例1中的线性规划问题(P1)中增加约束条件x1+x2+x3≤9，所得的新的线性规划问题记作(P2)，其最优解仍为：x*=(2,2,4,0)T. 试求(P2)对偶问题的最优解.

例2的解法一由题意，线性规划问题(P2)及其对偶问题(D2)为

(2.1)

在实际练习中，学生往往能利用互补松弛定理的 (1.2) 式准确写出对偶问题中的条件约束等式，但常常忽略运用 (1.1) 式来找对偶问题最优解中的零分量，以致无法得到最优解. 那么，当这种情况发生时，是否还有其他的方法来补救呢？

在例2中，原问题最优解中正分量的个数等于约束条件个数减1. 对于这类特殊的情形，我们还有以下两种方法.

(i) 利用变量的非负性.

例2的解法二由 (2.1) 式解得

将上式代入对偶问题(D2)的目标函数得

z=8w1+6w2+6w3+9w4

(ii) 利用原问题的最优值

例2的解法三因为(P2)的最优解为x*=(2,2,4,0)T，故最优值

2 结论

上述研究表明，当原线性规划问题最优解中正分量的个数与条件约束的个数满足不同的大小关系时，我们所选择的互补松紧条件具备一定的规律性.特别地，当正分量的个数等于约束条件个数减1时，我们还有另外的方法来求线性规划对偶问题的最优解.这将有助学生更好的掌握及灵活运用对偶理论的相关知识.