线性规划与整数规划

线性规划

最大化或最小化一个受限于一组有限的线性约束的线性函数

性质

标准型

最大化$\quad \sum\limits_{j=1}^{n} c_jx_j$

满足约束$~$ $\sum\limits_{j=1}^{n} a_{ij}x_j \le b_i,\ i=1,2,…,m$

$~$ $~$ $~$ $~$ $~$ $~$ $~$ $x_j \ge 0,\ j=1,2,…,n$

矩阵表示:${Max\ c^Tx\ :\ Ax \le b,\ x \ge 0}$

转化

  • 若目标函数要求取最小值,可以取相反数变成取最大值
  • 对于限制条件$f(x_1,x_2,…,x_n)\geq b$,可以用不等式$-f(x_1,x_2,…,x_n)\leq -b$描述
  • 对于限制条件$f(x_1,x_2,…,x_n)=b$,可以用两个不等式$f(x_1,x_2,…,x_n)\leq b$,$f(x_1,x_2,…,x_n)\geq b$描述
  • 对于无限制的变量$x$,可以将其拆成两个非负变量$x_0$,$x_1$,使得$x=x_0-x_1$

松弛型

最大化$\quad \sum\limits_{j=1}^{n} c_jx_j$

满足约束$~$ $x_{i+n}=b_i - \sum\limits_{j=1}^{n} a_{ij}x_j,~i=1,2,…,m$
$~$ $~$ $~$ $~$ $~$ $~$ $~$ $x_j \ge 0,\ j=1,2,…,n+m$

基变量:等式左侧的所有变量
非基变量:等式右侧的所有变量

单纯性法

通过变量的代换,实现在解空间内沿着边界朝着目标函数增大的方向移动

基本解:非基变量值为$0$,基变量值为$b_i$
可行解:使得$m$个限制条件能够满足的一组非基变量

转轴

选择一个基变量$X_l$,将其与非基变量$X_e$互换
根据$Bland$法则,选择系数大于$0$且标号最小的非基变量

初始化

如果基本解不是可行解,即存在$b_i<0$
在所有$bi<0$的约束中随机选一个作为$xl$,再随机选一个$a_{le}<0$的作为$x_e$,然后$Pivot(l,e)$后$b_i$就变正了

对偶性

${Max\ c^Tx\ :\ Ax \le b,\ x \ge 0}\ \quad {Min b^Ty\ :\ A^Ty \ge c,\ t \ge 0}$

最大化最小化互换,常数与目标函数互换,改变不等号,变量与约束对应

Sth

  1. 当只有两个变量时,解空间为约束条件的半平面交,可以在半平面交上二分求解
  2. 单纯性法在一般情况下可以在多项式时间内出解,当然存在最坏情况可以被卡到指数复杂度

全幺模矩阵

全幺模矩阵是指一个满足:任意一个行数和列数相等的满秩子矩阵行列式的值都是$1$或$-1$的矩阵

充分条件

  1. 仅有$-1,0,1$构成

  2. 每列至多两个非零数

  3. 行可分为两个集合:

    一列包含两个同号非零数,两行不在同一个集合

    一列包含两个异号非零数,两行在同一个集合

性质

若线性规划中$A$为全幺模矩阵,则单纯形法过程中所有系数$∈−1,0,1$

能转化成全幺模矩阵的整数规划问题可以使用相同的线性规划解决

整数规划

整数规划指最后解中的变量都必须是整数的线性规划

$NP-hard$问题

0-1 分数规划

整数规划的特殊形式,即每个变量$x \in ${$0,1$}

分享到: