Simplex

单纯形

表

对于一个单纯形问题 $\displaystyle \max{c^Tx}: Ax\leq b, x\geq 0$

假设有 $n$ 个变量，$m$ 个约束

即

$A=[a_{ij}]_{m\times n}$

$b=[b_{ij}]_{m\times 1}$

$c=[c_{ij}]_{1\times n}$

$A$ 是 $m$ 行 $n$ 列的矩阵

我们将 $A, b, c$ 填入一个表：

	$x_1$	$\cdots$	$x_n$	$b$
$(0)$	$c_1$	$\cdots$	$c_n$	$v$
$(1)$	$a_{11}$	$\cdots$	$a_{1n}$	$b_1$
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
$(m)$	$a_{m1}$	$\cdots$	$a_{mn}$	$b_m$

对于松弛变量，初始值为 $c$ 为 $0$, 同时对应的 $A$ 位置为单位矩阵

具体展开写：

	$x_1$	$\cdots$	$x_n$	$x_{n+1}$	$\cdots$	$x_{n+m}$	$b$
$(0)$	$c_1$	$\cdots$	$c_n$	$0$	$\cdots$	$0$	$v$
$(1)$	$a_{11}$	$\cdots$	$a_{1n}$	$1$	$\cdots$	$0$	$b_1$
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
$(m)$	$a_{m1}$	$\cdots$	$a_{mn}$	$0$	$\cdots$	$1$	$b_m$

这个矩阵是手动模拟使用的，上面的是写代码用的

具体运行过程可以看 OI-WIKI 单纯形法的思想与例子小节中的一个例子

轴

初始有 $m$ 个松弛变量，轴都在松弛变量 $x_{n+1},\cdots,x_{n+m}$ 上

每次换轴，由于轴上第 $l$ 行是 $1$, 其他 $0\to m$ 行是 $0$, 注意第 $0$ 行的 $c$ 值也是 $0$

如果我们考虑像手动模拟一样建一个 $m\times(m+n)$ 的表, 使用下标记录哪些变量是轴

注意每次换轴下标改变，再用下标记录哪些变量是轴会很麻烦

所以不需要记录哪些变量是轴

我们只要在数组里只存储 $n$ 个非轴，每次换轴，由于轴的值是已知的，并且取代他的非轴值也是已知的(存在数组里)，所以利用数组该列的原有值重新计算，更新自己，即可完成换轴

具体地，将轴 $l$ 与非轴 $e$ 交换

新的第 $l$ 行，第 $e$ 列改为 $a[l][e]=1/a[l][e]$，表示原本轴的值 $1$ 除以非轴的值 $a[l][e]$

其他列正常高斯消元

新非轴的第 $i$ 行 $a[i][e] = 0-a[i][e] * a[l][e]$, 即原本轴的值 $0$ 减去高斯消元代价 $a[i][e] * a[l][e]$, 即这个位置原本非轴的值 $a[i][e]$ 乘上消元的系数 $a[l][e]$

其他列都是正常高斯消元

判断无界

如果一个轴 $c_i>0$ 且所有 $a_{ij}=0$, 那么所有限制条件对于这个变量没有限制，但目标函数可以无限制增大，那么无界

对偶原理

不加证明的给出：

$\displaystyle \max{c^Tx}: Ax\leq b, x\geq 0$

$\displaystyle \min{b^Ty}: A^T y\geq c, y\geq 0$

两个问题是等价的

P3980

使用对偶原理转化题意后

$A$ 矩阵相当于在第 $i$ 行的 $l_i\cdots r_i$ 列置 $1$

$b$ 矩阵与 $c$ 矩阵调换，原本的价值存在 $b$ 中，原本的限制存在 $c$ 中，再用单纯形即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 10010;
typedef double db;
int T, n, m, s, t;
db a[M][N], b[M], c[N], v;
void pivot(int l, int e)
{
    b[l] /= a[l][e]; 
    for (int i = 1; i <= n; ++i)
    {
        if (i != e)
            a[l][i] /= a[l][e];
    }
    a[l][e] = 1 / a[l][e]; 
    // instead of save 1 here, 
    // we save the value after we change pivot, 
    // that is, 1 / a[l][e]
    for (int i = 1; i <= m; ++i)
    {
        if (i == l)
            continue;
        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];
        // instead of save 0 here, 
        // we save the value after we change pivot
    }
    v += 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];
    // instead of save 0 here, 
    // we save the value after we change pivot
}
db simplex()
{
    while (1)
    {
        int l = 0, e = 0;
        db minn = 1e9;
        for (e = 1; e <= n; ++e)
            if (c[e] > 0)
                break;
        if (e == n + 1)
            return v; // all c <= 0, then is optimal
        for (int i = 1; i <= m; ++i)
        {
            if (a[i][e] > 0 && minn > b[i] / a[i][e])
            {
                minn = b[i] / a[i][e]; 
                // find relax variable which first become 0
                l = i;
            }
        }
        if (l == 0)
            return 1e9; 
        // unbounded because all a[i][e] = 0 and c[e] > 0,
        // so variable x[e] is not limited
        pivot(l, e); // change pivot
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= m; ++i)
    {
        cin >> s >> t >> b[i];
        for (int j = s; j <= t; ++j)
            a[i][j] = 1;
    }
    cout << (int)(simplex() + 0.5);
}
int main()
{
    solve();
    return 0;
}

几何意义

在凸多面体上随机选一个顶点，并沿着所有边计算目标函数，选择最优的点移动过去，知道当前点成为最优解，则停止

不足

最坏情况是指数级的

其他线性规划算法：

椭球法 (Ellipsoid Algorithm)：理论复杂度优于单纯形，实际表现有些慢

内点法 (Karmarkar's Algorithm)：理论复杂度和实际表现都不错

Seidel's algorithm

证明复杂度 $O(n)$

对于最后一步，假设最优解为 $a_{i}\cdot x = b_{i} $ 和 $a_{j}\cdot x = b_{j}$ 相交得到的点

如果这两条限制已经出现过，那么答案不会变，即一定满足 $a_{1}\cdot x \leq b_{1}$

这也说明最后一个直线 $a_{i}\cdot x = b_{i}$ 不是这两个直线中的一个，概率为 $1-2/n$，这是由于所有限制随机排列得来的

如果出现过，则答案变化，有一个 $O(n)$ 的check，概率为 $2/n$

所以最后一步的代价为 $(1-2/n)\cdot O(1) + 2/n \cdot O(n)=O(1)$

对于之前的步骤也可证明代价为 $O(1)$

所以总的期望复杂度为 $O(n)$

	\(x_1\)	\(\cdots\)	\(x_n\)	\(b\)
\((0)\)	\(c_1\)	\(\cdots\)	\(c_n\)	\(v\)
\((1)\)	\(a_{11}\)	\(\cdots\)	\(a_{1n}\)	\(b_1\)
\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)
\((m)\)	\(a_{m1}\)	\(\cdots\)	\(a_{mn}\)	\(b_m\)

	\(x_1\)	\(\cdots\)	\(x_n\)	\(x_{n+1}\)	\(\cdots\)	\(x_{n+m}\)	\(b\)
\((0)\)	\(c_1\)	\(\cdots\)	\(c_n\)	\(0\)	\(\cdots\)	\(0\)	\(v\)
\((1)\)	\(a_{11}\)	\(\cdots\)	\(a_{1n}\)	\(1\)	\(\cdots\)	\(0\)	\(b_1\)
\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)
\((m)\)	\(a_{m1}\)	\(\cdots\)	\(a_{mn}\)	\(0\)	\(\cdots\)	\(1\)	\(b_m\)

Simplex

单纯形

表

轴

判断无界

对偶原理

几何意义

不足

Seidel's algorithm

证明复杂度 \(O(n)\)