对偶理论的基本定理

Answer 1

原始问题和对偶问题的标准形式如下：
原始问题　对偶问题
max　z=cx　min　 w=yb
s.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）。在原始问题与对偶问题之间存在着一系列深刻的关系，现已得到严格数学证明的有如下一些定理。 若上述原始问题和对偶问题分别有可行解x0和y0,且u0和v0分别为它们的松弛变量，则当且仅当v0x0=0 和u0y0=0时, x0和y0分别为它们的最优解。v0x0=0和u0y0=0这两个等式称为互补松弛条件。
对称对偶线性规划 　具有对称形式的线性规划的特点是：
①全部约束条件均为不等式，对极大化问题为≤，对极小化问题为≥。
②全部变量均为非负。
列出对称对偶线性规划的步骤是：
①规定非负的对偶变量，变量数等于原始问题的约束方程数。
②把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。
③把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。
④把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。
⑤把原始问题约束条件中的不等号反向作为对偶问题约束条件的不等号。
⑥将原始问题目标函数取极大化改成对偶问题目标函数取极小化。
非对称对偶线性规划 　有时线性规划并不以对称方式出现，如约束条件并不都是同向不等式，变量可以是非正的或没有符号约束。
列写非对称对偶线性规划可参照原始-对偶表（见表）按下列步骤进行：
①规定对偶变量，变量个数等于原始问题约束不等式数。
②把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。
③把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。
④把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。
⑤根据原始问题的约束不等式情况，确定对偶变量的符号约束。
⑥根据原始问题决策变量的符号约束，确定对偶问题约束不等式的符号方向。
对偶问题的最优解 　从原始问题的最终单纯形表中（最优单纯形算子）可直接得到对偶问题的最优解。原始问题中松弛变量的检验数对应着对偶问题的解（符号相反）。在用单纯形法时每一步迭代可得到原始问题的可行解x0和对偶问题的补充解y0,且cx0=y0b,若x0不是原始问题的最优解，y0就不是对偶问题的可行解。最后一步迭代得到原始问题的最优解x*和对偶问题的补充最优解y*，且cx*=y*b。y*是原始问题的影子价格。