用\(A_{ij}=0/1\)表示第\(i\)天\(j\)类志愿者能否被招募，\(x_i\)为\(i\)类志愿者招募了多少人，\(need_i\)表示第\(i\)天需要多少人，\(C_i\)表示\(i\)类招募志愿者的花费。
那么我们需要\[最小化\ Cx\\s.t.\ Ax\geq need\\x\geq 0\]
（s.t.：subject to，使得满足）
这是一个最小化线性规划，而不是标准型的最大化线性规划。根据对偶原理(见这儿)，我们把它变成：\[最大化\ x*need\\s.t.\ xA\leq C\\x\geq 0\]
用非矩阵形式直观地写：\[最小化\ \sum_{i=1}^mC_ix_i\\s.t.\ \sum_{i=1}^nA_{ij}x_j\geq need_i\ ,\ j=1,2,\ldots,m\\x_j\geq 0\]
利用对偶原理，转化为：\[最大化\ \sum_{i=1}^nneed_ix_i\\s.t.\ \sum_{i=1}^mA_{ij}x_i\leq C_j\ ,\ j=1,2,\ldots,m\\x_i\geq 0\]
这样就可以直接用单纯形做了。
还有一个问题，线性规划的解是否可能非整数？
我不知道为什么有这么个...常识定理？
线性规划的问题的最优解为整数的一个必要条件是它的任意一个子方阵的行列式为\(-1, 0, 1\)。
反正这有\(Candy?\)的结论，我就记住吧。。
下面有洛谷上题解的证明，证明本题方阵的任意一个子方阵的行列式为\(-1, 0或1\)，
Proof：
用\(u\rightarrow v\ (f,\ c)\)表示一条\(u\rightarrow v\)容量为\(f\)，花费为\(c\)的边。
对于每一类志愿者，连边\(l_i\rightarrow r_i+1\ (INF,\ cost_i)\)；
每相邻的两天，连边\(i\rightarrow i+1\ (INF-need_i,\ 0)\)；
对于源点汇点，连边\(S\rightarrow 1\ (INF,\ 0)\)、\(n+1\rightarrow T\ (INF,\ 0)\)。
BZOJ.1061.[NOI2008]志愿者招募(线性规划 对偶原理 单纯形)
原文：https://www.cnblogs.com/SovietPower/p/9362857.html