Home

# 线性规划学习笔记

由于时间的原因，线性规划并没有学明白... 在这一方面我的能力属实有限，先整个链接吧...
参考资料：
0. 运筹学
1. 线性规划之单纯性算法
2. 单纯性算法
3. 线性规划
4. 线性规划
5. 对偶理论
6. 线性规划的对偶问题
7. 单纯形法

# P3980 [NOI2008] 志愿者招募

# 题目描述

有一个需要 nn 天完成的项目，第 ii 天至少需要 aia_i 人。一共有 mm 类志愿者可以招募，第 ii 类志愿者可以从第 sis_i 天工作到 tit_i 天，招募的费用是每人 cic_i 元。请设计一种方案使其满足在招募到足够的志愿者的前提下，招募费用最少（当然不需要输出方案）。

#

记 xix_i 为需要的第 ii 类的志愿者的人数，pi,jp_{i, j} 为第 ii 天第 jj 类志愿者能否工作。
可以得到如下式子：

x1p1,1+x2p1,2+x3p1,3+...+xmp1,m≥a1x1p2,1+x2p2,2+x3p2,3+...+xmp2,m≥a2. . . . . . x1pn,1+x2pn,2+x3pn,3+...+xmpn,m≥an\begin{aligned} &x_1 p_{1, 1} + x_2 p_{1, 2} + x_3 p_{1, 3}+...+ x_m p_{1, m} \ge a_1 \\ &x_1 p_{2, 1} + x_2 p_{2, 2} + x_3 p_{2, 3}+...+ x_m p_{2, m} \ge a_2 \\ &.~.~.~.~.~.~\\ &x_1 p_{n, 1} + x_2 p_{n, 2} + x_3 p_{n, 3}+...+ x_m p_{n, m} \ge a_n \\ \end{aligned}

所需费用 f=c1x1+c2x2+...+cmxmf = c_1 x_1 + c_2 x_2 + ... + c_m x_m。

线性规划的对偶定理
原问题：

max z=∑j=1ncjxjs.t.{∑j=1nxjai,j≤bi(i=1,...,m)xj≥0(j=1,...,n)\begin{aligned} &max ~ z = \sum_{j = 1}^n c_j x_j\\ s.t. &\begin{cases} \sum\limits_{j = 1}^n x_j a_{i, j} \le b_i &(i = 1, ..., m) \\ x_j \ge 0 &(j = 1, ..., n) \end{cases} \end{aligned}

对偶问题：

min w=∑i=1mbiyis.t.{∑i=1myiai,j≥cj(j=1,...,n)yi≥0(i=1,...,m)\begin{aligned} &min ~ w = \sum_{i = 1}^m b_i y_i\\ s.t. &\begin{cases} \sum\limits_{i = 1}^m y_i a_{i, j} \ge c_j &(j = 1, ..., n) \\ y_i \ge 0 &(i = 1, ..., m) \end{cases} \end{aligned}

我们对这题的式子套一下上面的变换：
原问题：

min f=∑i=1mcixis.t.{∑i=1mxipi,j≥aj(j=1,...,n)xi≥0(i=1,...,m)\begin{aligned} &min ~ f = \sum_{i = 1}^m c_i x_i\\ s.t. &\begin{cases} \sum\limits_{i = 1}^m x_i p_{i, j} \ge a_j &(j = 1, ..., n) \\ x_i \ge 0 &(i = 1, ..., m) \end{cases} \end{aligned}

对偶问题：

max z=∑j=1najyjs.t.{∑j=1nyjpi,j≤ci(i=1,...,m)yj≥0(j=1,...,n)\begin{aligned} &max ~ z = \sum_{j = 1}^n a_j y_j\\ s.t. &\begin{cases} \sum\limits_{j = 1}^n y_j p_{i, j} \le c_i &(i = 1, ..., m) \\ y_j \ge 0 &(j = 1, ..., n) \end{cases} \end{aligned}

于是我们就将一个最小化型线性规划转化为了标准形式（最大化型线性规划）。
cic_i 都为非负整数，所以转化后的线性规划就有了基本解，那么就可以用单纯性算法（单纯形法）求取最优解。
贴个代码跑路了

#define Meteorshower_Y true
#include<iostream>
#include<climits>
#include<cstdio>
using namespace std;
const double inf = 1e-6;
const int MAXN = 1e3+10;
const int MAXM = 1e4+10;
const int MAXA = MAXN+MAXM;
auto simplex() -> double;
auto pivot(int r, int c) -> void;
int n, m, a[MAXN];
int s[MAXM], t[MAXM], c[MAXM];
double A[MAXM][MAXN], ans;
auto main() -> signed
{
    scanf("%d%d", &n, &m);
    for(int j = 1; j <= n; j += 1)
        scanf("%d", &a[j]);
    for(int i = 1; i <= m; i += 1)
        scanf("%d%d%d", &s[i], &t[i], &c[i]);
    for(int i = 1; i <= m; i += 1)
        for(int j = s[i]; j <= t[i]; j += 1)
            A[i][j] = 1;
    printf("%0.lf", -simplex());
    return 0;
}
auto simplex() -> double
{
    while(Meteorshower_Y)
    {
        int basic = 0, notbasic = 0;
        double mina = 1e16;
        for(int j = 1; j <= n; j += 1) 
            if(a[j] > a[notbasic]) notbasic = j;
        if(!notbasic) return ans;
        for(int i = 1; i <= m; i += 1) 
            if(A[i][notbasic] > inf and mina > c[i]/A[i][notbasic])
                basic = i, mina = c[i]/A[i][notbasic];
        if(!basic) return 1e16;
        pivot(basic, notbasic);
    }
    return ans;
}
auto pivot(int R, int C) -> void
{
    double cyr = 1.0/A[R][C];
    A[R][C] = 1;
    for(int j = 1; j <= n; j += 1) A[R][j] *= cyr;
    c[R] *= cyr; 
    
    cyr = a[C]; a[C] = 0;
    for(int j = 1; j <= n; j += 1) a[j] -= cyr*A[R][j];
    ans -= cyr*c[R];
    
    for(int i = 1; i <= m; i += 1)
    {
        if(i == R) continue;
        cyr = A[i][C]; A[i][C] = 0;
        for(int j = 1; j <= n; j += 1) A[i][j] -= cyr*A[R][j]; 
        c[i] -= cyr*c[R];
    }
}