对偶理论

[拼音]：dui’ou lilun

[外文]：duality theory

研究线性规划中原始问题与对偶问题之间关系的理论。

发展简史

在线性规划早期发展中最重要的发现就是对偶问题，即每一个线性规划问题(称为原始问题)都有一个与它对应的对偶线性规划问题（称为对偶问题）。1928年美籍匈牙利数学家 J.von诺伊曼在研究对策论时已发现线性规划与对策论之间存在着密切的联系。两人零和对策可表达成线性规划的原始问题和对偶问题。他于1947年提出对偶理论。1951年G.B.丹齐克引用对偶理论求解线性规划的运输问题，研究出确定检验数的位势法原理。1954年C.莱姆基提出对偶单纯形法，成为管理决策中进行灵敏度分析的重要工具。对偶理论有许多重要应用：在原始的和对偶的两个线性规划中求解任何一个规划时，会自动地给出另一个规划的最优解；当对偶问题比原始问题有较少约束时，求解对偶规划比求解原始规划要方便得多；对偶规划中的变量就是影子价格。

对偶问题

每一个线性规划问题都伴随有另一个线性规划问题，称为对偶问题。原来的线性规划问题则称为原始线性规划问题，简称原始问题。对偶问题有许多重要的特征，它的变量能提供关于原始问题最优解的许多重要资料，有助于原始问题的求解和分析。对偶问题与原始问题之间存在着下列关系：

（1）目标函数对原始问题是极大化，对对偶问题则是极小化。

（2）原始问题目标函数中的收益系数是对偶问题约束不等式中的右端常数，而原始问题约束不等式中的右端常数则是对偶问题中目标函数的收益系数。

（3）原始问题和对偶问题的约束不等式的符号方向相反。

（4）原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵。

（5）原始问题的约束方程数对应于对偶问题的变量数，而原始问题的变量数对应于对偶问题的约束方程数。

（6）对偶问题的对偶问题是原始问题，这一性质被称为原始和对偶问题的对称性。

基本定理

原始问题和对偶问题的标准形式如下：原始问题　　　　　　　　对偶问题max　　z＝cx　　　　　　　　min　　＝ybs.t.　　Ax≤b　　　　　　　　s.t.　　yA≥c

x≥0　　　　　　　　y≥0式中max表示求极大值,min表示求极小值,s.t.表示“约束条件为”；_z为原始问题的目标函数，w为对偶问题的目标函数；x为原始问题的决策变量列向量（n×1），y为对偶问题的决策变量行向量(1×m);A为原始问题的系数矩阵(m×n),b为原始问题的右端常数列向量（m×1），c为原始问题的目标函数系数行向量（1×n）。在原始问题与对偶问题之间存在着一系列深刻的关系，业已得到严格数学证明的有如下一些定理。

弱对偶定理

若上述原始问题和对偶问题分别有可行解x⁰和y⁰,则y⁰b≥cx⁰。这个定理表明极大化问题任一可行解的目标函数值总是不大于它的对偶问题的任一可行解的目标函数值。

强对偶定理

若上述原始问题和对偶问题都可行，则它们分别有最优解x^*和y^*，且cx^*=y^*b。

最优准则定理

若上述原始问题和对偶问题分别有可行解x⁰和y⁰,且两者的目标函数值相等，即y⁰b=cx⁰,则两个可行解分别为对应线性规划的最优解。

互补松弛定理

若上述原始问题和对偶问题分别有可行解x⁰和y⁰，且u⁰和v⁰分别为它们的松弛变量,则当且仅当v⁰x⁰+u⁰y⁰时，x⁰和y⁰分别为它们的最优解。

松弛定理

若上述原始问题和对偶问题分别有可行解x⁰和y⁰,且u⁰和v⁰分别为它们的松弛变量，则当且仅当v⁰x⁰=0 和u⁰y⁰=0时, x⁰和y⁰分别为它们的最优解。v⁰x⁰=0和u⁰y⁰=0这两个等式称为互补松弛条件。

对称对偶线性规划

具有对称形式的线性规划的特点是：

（1）全部约束条件均为不等式，对极大化问题为≤，对极小化问题为≥。

（2）全部变量均为非负。列出对称对偶线性规划的步骤是：

（1）规定非负的对偶变量，变量数等于原始问题的约束方程数。

（2）把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。

（3）把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。

（4）把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。

（5）把原始问题约束条件中的不等号反向作为对偶问题约束条件的不等号。

（6）将原始问题目标函数取极大化改成对偶问题目标函数取极小化。

非对称对偶线性规划

有时线性规划并不以对称方式出现，如约束条件并不都是同向不等式，变量可以是非正的或没有符号约束。列写非对称对偶线性规划可参照原始-对偶表（见表）按下列步骤进行：

（1）规定对偶变量，变量个数等于原始问题约束不等式数。

（2）把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。

（3）把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。

（4）把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。

（5）根据原始问题的约束不等式情况，确定对偶变量的符号约束。

（6）根据原始问题决策变量的符号约束，确定对偶问题约束不等式的符号方向。

对偶问题的最优解

从原始问题的最终单纯形表中（最优单纯形算子）可直接得到对偶问题的最优解。原始问题中松弛变量的检验数对应着对偶问题的解（符号相反）。在用单纯形法时每一步迭代可得到原始问题的可行解x⁰和对偶问题的补充解y⁰,且cx⁰=y⁰b,若x⁰不是原始问题的最优解，y⁰就不是对偶问题的可行解。最后一步迭代得到原始问题的最优解x^*和对偶问题的补充最优解y^*，且cx^*=y^*b。y^*是原始问题的影子价格。