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

(湖北大学数学与统计学学院，应用数学湖北省重点实验室， 湖北 武汉 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，即为“紧的”；……