大规模线性规划对偶如何成？

去年寒假牛牛开始接触精确求解算法，小谷哥给牛牛推荐了一本绝世好书——《运筹优化常用模型、算法及案例实战》（刘兴禄 主编），于是牛牛开始日夜攻读，写了好多篇笔记。这篇笔记也是参（照）考（搬）这本书写的。 1. 原问题与对偶问题的关系 1.1 借助原问题与对偶问题的关系写对偶问题 当原问题不是标准形时，可以借助表4.1写出原问题的对偶，或者可以转成标准形再写对偶。 1.2 使用标准形式写对偶问题 表 4.1用于检查比较方便，但是用于写对偶问题可能有些烦琐。因此，可以首先把原问题全部化成统一的形式。如下： （1）\(max\)问题，变量都≥0，约束都≤0 （粗略理解为：资源都是有限的）。 （2）\(min\)问题，变量都≥0，约束都≥0 （粗略理解为：需求至少要被满足）。 符号说明： 原问题有\(n\)个决策变量和\(m\)个约束条件 \(c\)：目标函数系数向量，为一个\(n\)维列向量，\(c^T=(c_1,c_2,\dots,c_n)\)，\(c\in\mathbb{R^n}\)。\(c^T=\left[\begin{matrix}c^T_B&c^T_N\end{matrix}\right]\) \(c_B\)：目标函数中，基变量的系数向量，为一个列向量 \(c_N\)：目标函数中，非基变量的系数向量，为一个列向量 \(x\)：决策变量向量，是一个\(n\)维列向量，\(x^T=(x_1,x_2,\dots,x_n)\)，\(x\in\mathbb{R^n}\).\(x=\left[\begin{matrix}x_B\\x_N\end{matrix}\right]\) \(x_B\)：基变量，为一个列向量 \(x_N\)：非基变量，为一个列向量 \(A\)：线性规划的约束系数矩阵，\(A\in\mathbb{R^{m×n}}\)。\(A=\left[\begin{matrix}B&N\end{matrix}\right]\) \(B\)：基变量的约束系数矩阵 \(N\)：非基变量的约束系数矩阵 \(b\)：约束条件右端的常数向量，为一个\(m\)维列向量，\(b\in\mathbb{R^m}\) 原问题： \[max\quad{Z}=c^Tx\tag{1} \] \[s.t.\quad{Ax}\leq{b}\tag{2} \] \[\quad\quad{x}\geq0\tag{3} \] 对偶问题： \[min\quad{W}=b^Ty\tag{4} \] \[s.t.\quad{A^Ty}\geq{c}\tag{5} \] \[\quad\quad{y}\geq0\tag{6} \] 2. 对偶理论相关的重要定理 首先用矩阵的形式给出线性规划的解的一些重要公式： \[max\quad{z}=\left[\begin{matrix}c^T_B&c^T_N\end{matrix}\right]\left[\begin{matrix}x_B\\x_N\end{matrix}\right]\tag{7} \] \[s.t.\quad\left[\begin{matrix}B&N\end{matrix}\right]\left[\begin{matrix}x_B\\x_N\end{matrix}\right]=b\tag{8} \] 对于模型的约束（8），有： \[Bx_B+Nx_N=b \] 两边左乘\(B^{-1}\)有： \[B^{-1}Bx_B+B^{-1}Nx_N=B^{-1}b \] \[x_B=B^{-1}b-B^{-1}Nx_N\tag{9} \] 在解中，令所有非基变量均为\(0\)，即： \[x_N=0 \] 其中，\(0\)是一个维数为非基变量个数的零向量。因此根据上述表达式，可以得到模型的解。 把（9）代入目标函数中，化简得到： \[z=c^T_BB^{-1}b+(c^T_N-c^T_BB^{-1}N)x_N\tag{10} \] 在（10）中，\(c^T_N-c^T_BB^{-1}N\)就是检验数（reduced cost） 具体由来可以看单纯形法的推导 然后考虑下面的原问题和对偶问题： 其中，\(c,y,x\)均是列向量。并且在任一次的单纯形表迭代中，单纯形表的第0行 (row 0) 都是下面的形式。 在原问题中，检验数\(\sigma_j=c_j-z_j=c_j-\sum^m_{i=1}c_ia_{ij}\)，\(j\)代表第\(j\)个决策变量。