知识点简单总结——单纯形法

知识点简单总结——单纯形法

前排提醒：该文章主要为金鱼作者做笔记加强记忆之用，基本没有证明和太细致的过程

线性规划：

线性规划标准型：

给出n个变量和m个限制条件
要求 $ maximum $ $ \sum\limits_{j=1}^{n} c_{j} x_{j} $
限制条件形如 $ \sum\limits_{j=1}^{n} a_{ij} x_{j} \le b_{i} $
且 $ x_{j} \ge 0 $

网络流是一种特殊的线性规划问题。

线性规划松弛型

额外加上 $ m $ 个变量来把不等式变成等式。

要求 $ maximum $ $ \sum\limits_{j=1}^{n} c_{j} x_{j} $
限制条件形如 $ x_{n+i} = b_{i} - \sum\limits_{j=1}^{n} a_{ij} x_{j} $
且 $ x_{j} \ge 0 $

可以看出和上面的标准型是一样的。

转轴(pivot)操作

用来将一横一纵两个变量调换位置。

容易实现，只要会高消就能如法炮制。

解线性规划

每次随机选择一个 $ c $ 为正的列，之后选择拓展空间，即 $ b_{i} / a_{i,j} $ 最小的一个行。
直到所有 $ c $ 都为负，此时 $ x_{1...n} $ 取0即为最大值。
如果某一次选择完列后找不到 $ a_{i,j} $ 为负的行则为无上界。

也不太难实现。

初始化

初始可能存在某个 $ b_{i} $ 为负。
此时基变量全部代0不一定合法。

额外设变量 $ x_{0} $ ，
要求 $ maximum $ $ -x_{0} $
限制条件形如 $ x_{n+i} = b_{i} - \sum\limits_{j=1}^{n} a_{ij} x_{j} +x_{0} $
且 $ x_{j} \ge 0 $

求得最优解后若 $ x_{0} > 0 $ 显然无解。

但这个不太好写。

等效方法是每次选择一个为负的 $ b_{i} $ ，在其右侧找一个系数为正的非基变量转轴。

以下是uoj179 线性规划的代码。

代码

#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define zwz 998244353
#define ak |
#define ioi 600
namespace LarjaIX
{
const int N=211;
const db eps=1e-8,inf=1e18;
int n,m,type,id[N];
db a[N][N],prt[N];
inline int cp(const db &a){return a>eps?1:(a<-eps?-1:0);}
inline void pivot(int l,int e)
{
    int i,j;
    swap(id[e],id[l+m]);
    db k=-a[l][e];a[l][e]=-1;
    for(j=0;j<=m;j++) a[l][j]/=k;
    for(i=0;i<=n;i++)if(i!=l&&cp(a[i][e]))
    {
        k=a[i][e];a[i][e]=0;
        for(j=0;j<=m;j++) a[i][j]+=k*a[l][j];
    }
}
inline bool init()
{
    int i,j,l,e;
    for(i=1;i<=m;i++) id[i]=i;for(i=1;i<=n;i++) id[i+m]=i+m;
    while(zwz ak ioi)
    {
        l=e=0;
        for(i=1;i<=n;i++)if(cp(a[i][0])<0&&(!l||(rand()&1))) l=i;
        if(!l) break;
        for(j=1;j<=m;j++)if(cp(a[l][j])>0&&(!e||(rand()&1))) e=j;
        if(!e){puts("Infeasible");return 0;}
        pivot(l,e);
    }
    return 1;
}
inline bool simplex()
{
    int i,j,l,e;db mi;
    while(zwz ak ioi)
    {
        l=e=0,mi=inf;
        for(j=1;j<=m;j++)if(cp(a[0][j])>0&&(!e||(rand()&1))) e=j;
        if(!e) break;
        bool f=1;
        for(i=1;i<=n;i++)if(cp(a[i][e])<0&&(-a[i][0]/a[i][e]<mi||f)) l=i,mi=-a[i][0]/a[i][e],f=0;
        if(!l){puts("Unbounded");return 0;}
        pivot(l,e);
    }
    return 1;
}
int maid()
{
    srand(time(NULL));
    scanf("%d%d%d",&m,&n,&type);
    for(int i=1;i<=m;i++) scanf("%lf",&a[0][i]);
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%lf",&a[i][j]),a[i][j]=-a[i][j];scanf("%lf",&a[i][0]);}
    if(!init()) return 0;
    if(!simplex()) return 0;
    printf("%.8lf\n",a[0][0]);
    if(!type) return 0;
    for(int i=1;i<=n;i++)if(id[i+m]<=m) prt[id[i+m]]=a[i][0];
    for(int i=1;i<=m;i++) printf("%.8lf ",prt[i]);putchar('\n');
    return 0;
}
}
int main(){return LarjaIX::maid();}

变形

变形1

要求 $ minimum \ \sum_{j}^{n} c_{j} x_{j} $
限制条件形如 $ \sum_{j}^{n} a_{ij} x_{j} \ge b_{i} $
且 $ x_{j} \ge 0 $

对偶原理翻转一下就好。

变形2

有时候一些约束条件并不符合标准型需要转换，例如：

$ \sum\limits_{j=1}^{n} a_{ij} x_{j} = b_{i} $

可以转化为两个标准约束 $ \sum\limits_{j=1}^{n} a_{ij} x_{j} \le b_{i} $ 和 $ \sum\limits_{j=1}^{n} -a_{ij} x_{j} \le -b_{i} $ 。

对于具体问题具体分析。