单纯形

OI 专题练习

---

---

常见的转化

（1）Minimize->Maximize：$C^T$的系数取反，求最大值，对答案取反。
（2）a=b：$a\leq b,a\geq b$
（3）变量本身的约束
$x\leq a$：设$x'=a-x$，则$x'\geq 0$
$x\geq a$：设$x'=x-a$，则$x'\geq 0$
$x$无限制：设$x=x'-x''$，则$x'\geq 0,x''\geq 0$
（4）对偶原理
下列两组线性规划的最优解相同。
①

$$\begin{aligned}Maximize~&C^Tx\\s.t. ~&Ax\leq B,x\geq 0\end{aligned}$$
② $$\begin{aligned}Minimize~&B^Ty\\s.t. ~&A^Ty\ge C,y\ge 0\end{aligned}$$

题目总览

• bzoj1061
   转化4

【bzoj1061】志愿者招募

实现小结：一定要明确行向量、列向量以及矩形的大小。

void Pivot(int l,int e) {
    c[l]/=a[l][e];
    F(j,1,n) if (j!=e)
        a[l][j]/=a[l][e];
    a[l][e]=1/a[l][e];
    F(i,1,m) if (i!=l&&a[i][e]!=0) {
        c[i]=c[i]-a[i][e]*c[l];
        F(j,1,n) if (j!=e)
            a[i][j]=a[i][j]-a[i][e]*a[l][j];
        a[i][e]=0-a[i][e]*a[l][e];
    }
    res=res+b[e]*c[l];
    F(j,1,n) if (j!=e)
        b[j]=b[j]-b[e]*a[l][j];
    b[e]=0-b[e]*a[l][e];
}
void Simplex(void) {
    F(t,1,INF) {
        int e=0;
        F(i,1,n)
            if (b[i]>0) {
                e=i;
                break;
            }
        if (!e) break;
        double mn=INF; int l=0;
        F(i,1,m)
            if (a[i][e]>0&&c[i]/a[i][e]<mn) {
                mn=c[i]/a[i][e];
                l=i;
            }
        if (mn==INF) {
            res=INF;
            return;
        }
        Pivot(l,e);
    }
}