标准型与松弛型

线性规划是这样一类问题：

• 有一些非负变量 $x_1,x_2,\cdots,x_n$。
• 这些变量满足一些线性不等式。
• 最小化/最大化目标函数 $z=\sum_{i=1}^nc_ix_i$。

线性规划问题的标准型为
$$
\text{maximize}\ z=\sum_{i=1}^nc_ix_i
$$

$$
\text{s.t.}\ \begin{cases}\sum_{j=1}^n a_{i,j}x_j=b_i,&i\in[1,m]\\x_i\geq 0,&i\in[1,n]\end{cases}
$$

可以写成矩阵的形式
$$
\text{maximize}\ z=c\cdot x
$$

$$
\text{s.t.}\ \begin{cases}Ax=b\\x\geq 0\end{cases}
$$

线性规划问题的松弛型为
$$
\text{maximize}\ z=\sum_{i=1}^nc_ix_i
$$

$$
\text{s.t.}\ \begin{cases}\sum_{j=1}^n a_{i,j}x_j\leq(\text{or}\geq)b_i,&i\in[1,m]\\x_i\geq 0,&i\in[1,n]\end{cases}
$$

一些转标准线性规划的技巧

标准线性规划要求：

• 目标函数为 $\text{maximize}$。
• 约束条件均为等式。
• 决策变量非负约束。

目标函数是 $\text{minimize}$ 怎么办？

取负即可转为 $\text{maximize}$。

松弛型线性规划怎么办？

可以通过添加变量的方法将松弛型转为标准型，具体做法是对于不等式
$$
\sum_{j=1}^na_{i,j}x_j\leq(\text{or}\geq)b_i
$$
添加变量 $y_i$，满足 $y_i\geq 0$，不等式变为
$$
\left(\sum_{j=1}^na_{i,j}x_j\right)+(\text{or}-)y_i=b_i
$$
下面是一个例子（NOI2008 志愿者招募的样例）：

设 $X_i$ 为第 $i$ 类志愿者的招募数，则问题为
$$
\text{minimize}\ z=2X_1+5X_2+2X_2
$$

$$
\text{s.t.}\ \begin{cases}X_1\geq 2\\X_1+X_2\geq 3\\X_3\geq 4\\X_1,X_2,X_3\geq 0\end{cases}
$$

转为标准型即为
$$
\text{minimize}\ z=2X_1+5X_2+2X_2
$$

$$
\text{s.t.}\ \begin{cases}X_1-Y_1=2\\X_1+X_2-Y_2=3\\X_3-Y_3=4\\X_1,X_2,X_3,Y_1,Y_2,Y_3\geq 0\end{cases}
$$

取值无约束的变量怎么办？

可以转化为两个变量的差。

如 $-\infty<x<+\infty$，可以令 $x=x_1-x_2$，条件变为 $x_1,x_2\geq 0$。

对偶

定义线性规划
$$
\text{maximize}\ z=c^T\cdot x
$$

$$
\text{s.t.}\begin{cases}Ax\leq b\\x\geq 0\end{cases}
$$

的对偶问题为
$$
\text{minimize}\ z=b^T\cdot y
$$

$$
\text{s.t.}\begin{cases}A^Ty\geq c\\y\geq 0\end{cases}
$$

然后可以证明，这两个问题的最优解是相等的。感性理解可以看 hyj 的文章。

单纯形

我不会，待填