感谢 lcw 学长的 blog，讲的很清晰，受益匪浅。
本文使用大量非正式语言，如有需要可以去看原论文。
定义
称形如 \(f(x_1,\cdots,x_n)=\sum\limits_{i=1}^n a_ix_i\) 的函数为线性函数。
称 \(f(x_1,\cdots,x_n)\ge b,f(x_1,\cdots,x_n)= b,f(x_1,\cdots,x_n)\le b\) 为线性约束。
称满足所有限制的解 \((x_1,\cdots,x_n)\) 为可行解，使目标函数达到最优的可行解称为最优解，所有可行解构成的区域为解空间。
标准型线性规划
形如
\[\begin{aligned} \max&&\sum_{j=1}^nc_{j}x_j\\ \text{s.t.}&&\sum_{j=1}^na_{i,j}x_j&\leq b_i&&\forall i\in[1,m]\\ &&x_j&\geq 0&&\forall j\in[1,n] \end{aligned}\]的问题为标准型线性规划。
可用矩阵表示为
\[\begin{aligned} \max&&\mathbf c^T\mathbf x&\\ \text{s.t.}&&\mathbf A\mathbf x&\leq \mathbf b\\ &&\mathbf x&\geq 0 \end{aligned}\]松弛型线性规划
形如
\[\begin{aligned} \max&&&\sum_{j=1}^nc_jx_j\\ \text{s.t.}&&x_{i+n}&=b_i-\sum_{j=1}^na_{i,j}x_j&&\forall i\in[1,m]\\ &&x_j&\geq 0&&\forall j\in[1,n+m] \end{aligned}\]的问题为松弛型线性规划。
容易将标准型线性规划转化为松弛型线性规划
单纯形
单纯形算法是一种解决松弛型线性规划的算法。
\[\begin{aligned} \max&&&\sum_{j=1}^nc_jx_j\\ \text{s.t.}&&x_{i+n}&=b_i-\sum_{j=1}^na_{i,j}x_j&&\forall i\in[1,m]\\ &&x_j&\geq 0&&\forall j\in[1,n+m] \end{aligned}\]称 \(x_1,\cdots,x_n\) 为基变量，称 \(x_{n+1},\cdots,x_{n+m}\) 为非基变量。
定义转轴操作 \(\text{pivot}(i,j)\)，以实现一个交换基变量和非基变量的效果。具体地，将 \(x_{i+n}=b_i-\sum\limits_{j=1}^n a_{i,j} x_j\) 改写为 \(x_j=\dfrac{b_i}{a_{i,j}}-\sum\limits_{k\ne j} \dfrac{a_{i,k}}{a_{i,j}}x_k-\dfrac{1}{a_{i,j}}x_{i+n}\)，将其他式子中的 \(x_j\) 如是替换即可。
算法流程如下。先假设 \(b_i\) 均非负。
初始显然有一可行解 \(\forall i\in[1,n+m],x_i=0\)。此时答案为 \(0\)。
不断执行如下操作，找到一个 \(j\) 满足 \(c_j>0\)，然后：
- 若 \(\forall i\in[1,m],a_{i,j}\le 0\)，此时可令 \(x_j=-\infty\)，可使答案为正无穷且符合所有约束，故答案无界。
- 若 \(\exists i\in[1,m],a_{i,j}>0\)，找出所有 \(a_{i,j}>0\) 中 \(\dfrac{b_i}{a_{i,j}}\) 最小的 \(i\)，执行 \(\text{pivot}(i,j)\)，考虑 \(b\) 的非负性是否仍然满足。考虑 \(k\ne i\)，若 \(b'_k< 0\) 即 \(b_k-a_{k,j}\dfrac{b_i}{a_{i,j}}<0\)，显然 \(a_{k,j}>0\)，于是 \(\dfrac{b_k}{a_{k,j}}<\dfrac{b_i}{a_{i,j}}\)，这与 \(\dfrac{b_i}{a_{i,j}}\) 最小矛盾。这次转轴操作会使答案增加 \(c_j\frac{b_j}{a_{i,j}}\)。
若 \(\forall j\in[1,n],c_j\le 0\)，则解 \(\forall i\in[1,n+m],x_i=0\) 为最优解，原线性规划问题的答案即为所有转轴操作累加的答案。
算法理论复杂度上界是指数级的，期望时间复杂度 \(O(nm^2)\)。
关于算法的正确性，引用 lcw 博客的一段：
考察一个线性规划的解空间，这个解空间是多个线性不等式解空间的交。可以证明每个线性不等式的解空间都是一个凸形区域（凸形区域的一个直观定义是，区域内任意两点连线上的点都属于这个区域），那么它们的交也是一个凸形区域。
因为解空间是凸形的，所以考虑在解空间内从一个初始解开始，进行爬山算法，这样所找到的局部最优解一定是全局最优解，因为 “山顶” 只有一个。
我们还没解决存在 \(b_i\) 为负数的情况，考虑辅助线性规划
\[\begin{aligned} \max&&&-x_0\\ \text{s.t.}&&x_{i+n}&=b_i-\sum_{j=1}^na_{i,j}x_j+x_0&&\forall i\in[1,m]\\ &&x_j&\geq 0&&\forall j\in[0,n+m] \end{aligned}\]我这里也完全没看懂，直接把 lcw 的解释贺上来。
显然，若 \((x_1,\cdots,x_{n+m})\) 是原线性规划的一组可行解，那么辅助线性规划的最优解 \((x_0,\cdots,x_{n+m})\)
应当使 \(x_0=0\)
。另一方面，若辅助线性规划的最优解 \((x_0,\cdots,x_{n+m})\)
满足 \(x_0=0\)
，那么 \((x_1,\cdots,x_{n+m})\) 就是一组原线性规划的可行解。
从而我们只需求出辅助线性规划的最优解即可。
而对于辅助线性规划，找到 \(i\in[1,m],b_i\) 最小的那个。然后执行转轴操作 \(\text{pivot}(i,0)\)
。此时对于任意 \(k\ne i\)
有
\(b'_k=b_k-b_i\ge 0\)，从而转换成 \(b_k\) 均非负的线性规划问题。
namespace Simplex {
double a[N][N], b[N], c[N];
double ans;
int n, m;
void pivot(int l, int e) {
b[l] /= a[l][e];
for(int j = 1; j <= n; j++)
if(j != e) a[l][j] /= a[l][e];
a[l][e] = 1 / a[l][e];
for(int i = 1; i <= m; i++)
if(i != l && fabs(a[i][e]) > 0) {
b[i] -= a[i][e] * b[l];
for(int j = 1; j <= n; j++)
if(j != e) a[i][j] -= a[i][e] * a[l][j];
a[i][e] = -a[i][e] * a[l][e];
}
ans += c[e] * b[l];
for(int j = 1; j <= n; j++)
if(j != e) c[j] -= c[e] * a[l][j];
c[e] = -c[e] * a[l][e];
}
double simplex() {
while(1) {
int e = n, l = 0;
for(; e; e--)
if(c[e] >(double)0) break;
if(!e) return ans;
double mn = 1e18;
for(int i = 1; i <= m; i++)
if(a[i][e] > (double)0 && mn > b[i] / a[i][e])
mn = b[i] / a[i][e], l = i;
if(mn == 1e18) return 1e18;
pivot(l, e);
}
}
} using namespace Simplex;
对偶
标准型线性规划形如
\[\begin{aligned} \max&&\mathbf c^T\mathbf x&\\ \text{s.t.}&&\mathbf A\mathbf x&\leq \mathbf b\\ &&\mathbf x&\geq 0 \end{aligned}\]规定其对偶形式为
\[\begin{aligned} \min&&\mathbf b^T\mathbf y&\\ \text{s.t.}&&\mathbf A^T\mathbf y&\geq \mathbf c\\ &&\mathbf y&\geq 0 \end{aligned}\]规定以上两种线性规划互为对偶。
弱对偶定理
在上面的定义下，有 \(\max\mathbf c^T\mathbf x\le \min\mathbf b^T\mathbf y\)。
证明较显然。
强对偶定理
在上面的定义下，有 \(\max\mathbf c^T\mathbf x= \min\mathbf b^T\mathbf y\)。
证明极为复杂。
标签：mathbf,线性规划,cdots,&&,forall,aligned,对偶 From： https://www.cnblogs.com/Terac/p/18034428