定义

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

  • 有一些非负变量 $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\leq 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\leq b\\x\geq 0\end{cases} $$

为每个不等式建立一个不等式 $x_{n+i}=b_i-\sum_{j=1}^na_{i,j}x_j$,松弛型线性规划定义为

$$ \text{maximize}\ z=\sum_{i=1}^nc_ix_i $$

$$ \text{s.t.}\ \begin{cases}x_{i+n}=b_i-\sum_{j=1}^n a_{i,j}x_j,&i\in[1,m]\\x_i\geq 0,&i\in[1,n+m]\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 的文章

单纯形

我不会


版权属于:M_sea

本文链接:https://m-sea-blog.com/archives/linear-programming/

转载时须注明出处及本声明

最后修改:2020 年 01 月 30 日 02 : 42 PM