整数规划——第三章全单模矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了整数规划——第三章全单模矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

整数规划——第三章全单模矩阵

若线性规划问题的约束矩阵为全单模矩阵，则该问题可行域的顶点都是整数点，从而线性规划与整数规划的最优解相同。

3.1 全单模性与最优性

考虑线性整数规划问题：
$\text{(IP)}\quad\begin{aligned} &\min c^Tx,\\ &s.t.\ Ax\le b,\\ &\qquad x\in \Z_+^n \end{aligned}$
其中 $A$ 是 $m \times n$ 整数矩阵， $b$ 是 $n$ 维整数向量。用如下线性规划作为其松弛问题：
$\text{(LP)}\quad\begin{aligned} &\min c^Tx,\\ &s.t.\ Ax\le b,\\ &\qquad x\in \R_+^n \end{aligned}$
若线性松弛问题存在最优解，且其可行集合 $P={x\in \R_+^n|Ax\le b}
$ 的所有顶点都是整数点，则线性规划问题必有整数最优解。因此，求解线性松弛问题(LP)就可得到原整数规划问题§的最优解。下面给出一个保证问题(LP)的最优解是整数点的充分条件

定理3.1 若线性规划问题(LP)的最优基矩阵B满足 $\text{det}(B)=\pm1$ ，这里 $B$ 是矩阵 $(A, I)$ 的 $m \times m$ 维子方阵，则线性规划问题(LP)的最优解是整数解。

定义3.1 设矩阵 $A$ 是 $m \times n$ 整数矩阵。若矩阵 $A$ 的任意子方阵的行列式等于0,1或者-1，则称矩阵A为全单模矩阵。

易知，若整数规划（IP）中的矩阵 $A$ 是全单模矩阵，求解线性规划（LP）等价于求解整数规划（IP)。

性质3.1若矩阵 $A$ 是全单模矩阵，则矩阵中元素a=0,1或者-1。

定理3.2 设矩阵 $A$ 是全单模矩阵，向量 $b$ 是整数向量，则多面体 $P=\{x\in \R_+^n|Ax\le b\}$ 的顶点都是整数点。

定理3.3 若对任意整数向量 $b$ ，多面体 $P=\{x\in \R_+^n|Ax\le b\}$ 的顶点都是整数点，则 $A$ 是全单模矩阵。

3.2 全单模矩阵的性质

性质3.2 设整数矩阵 $A$ 是全单模矩阵，对 $A$ 进行以下运算不改变其全单模性：

对矩阵 $A$ 进行转置；
矩阵 $(A, I)$ 是全单模的；
去掉 $A$ 的一行（或者一列)：
将 $A$ 的一行（或者一列）乘以-1；
互换 $A$ 的两行（或者两列）：
对 $A$ 进行转轴运算.

定理3.4 矩阵 $A$ 是全单模矩阵等价于对于每个集合 $J\sube N=\{1,2,...,n\}$ ，必存在 $J$ 的分割 $J_1,J_2$ 使得
$\left| \sum_{j\in J_1}a_{ij} -\sum_{j\in J_2}a_{ij}\right|\le 1,\quad i=1,...,m.$
推论3.3 设矩阵 $A$ 是 ${0,1,-1\}$ 矩阵，并且每列至多有两个非零元素，则矩阵 $A$ 是全单模矩阵当且仅当存在 $A$ 的行分割 $Q_1,Q_2$ 使得同一列中的两个非零元素满足以下条件：

若符号相同，则一个元素位于 $Q_1$ ,另一元素位于 $Q_2$
若特号相反，则这两个元素同时属于 $Q_1$ ,或者同时属于 $Q_2$ 。

由以上讨论可得到一个易于验证的全单模矩阵的充分条件

推论3.4 设矩阵 $A$ 的任意元素都是0,1或者一1，若 $A$ 满足以下两个条件，则矩阵 $A$ 是全单模的：

$A$ 的每一列至多含有两个非零元素；
若某列含有两个非零元素，则两个元素之和为0.

3.3 全单模矩阵在网络问题中的应用

3.3.1 二部图

给定无向图 $G = (V, E)$ ，其中 $V$ 表示顶点集合， $E$ 表示边集合。定义图 $G$ 的关联矩阵 $M$ ，其行和列分别用顶点集 $V$ 和边集 $E$ 标记；若边 $e$ 经过项点 $v$ ,则 $M_{v,e}=1$ ；否则 $M_{v,e}=0$ 。

若一个图 $G = (V, E)$ 的顶点集合 $V$ 可分解成两个非空子集 $V_1,V_2$ ，使得 $E$ 中每条边的两个端点分别属于 $V_1,V_2$ ，则称该图为二部图。下面定理表明无向图的关联矩阵的全单模性与二部图之间的等价性。

定理3.5 令 $G = (V, E)$ 表示无向图， $M$ 表示图 $G$ 的 $V\times E$ 关联矩阵，则 $M$ 是全单模矩阵当且仅当图 $G$ 是二部图。

3.3.2 指派问题

指派问题是二部图问题的一种特殊情况，是指将 $n$ 项任务恰当地分配给 $n$ 个工人，每个工人只能执行一项任务。由于每个工人完成不同工作所的成本不同，我们的目的是在保证各项任务完成的前提下最小化成本。令表示 $c_{ij}$ 由工人 $i$ 完成任务 $j$ 的成本，则最小化成本的指派问题可表述如下：
$\begin{aligned}&\min \sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij},\\ &s.t.\ \sum_{j=1}^nx_{ij} =1,\ i = 1,...,n,\\ &\quad\quad\sum_{i = 1}^n x_{ij} =1,j=1,...,n, \\ &\quad\quad x_{ij}\in \{0,1\},\quad i,j = 1,...,n. \end{aligned}$
记 $U$ 表示工人集合， $V$ 表示任务集合，在此集合上建立边集 $E$ ：若工人 $i$ 能够胜任任务 $j$ ,则边 $(i, j) \in E$ 。故图 $G = (U, V, E)$ 是二部图。由于二部图的关联矩阵是全单模矩阵，则求解其线性规划松弛问题即可得到整数最优解.，

另一类指派问题是将工人们分派到不同小组进行轮班，称之为排班问题。假设工作时间有 $m$ 个小时，共有 $n$ 次轮班，每一次轮班需要连续工作几个小时。第 $j$ 次轮班用 $m$ 维 $0 - 1$ 向量 $a_j$ 表示：若在第 $i$ 个小时被排在第 $j$ 次轮班中，则 $a_{ij}=1$ ；否则 $a_{ij}=0$ 。所以向量中 1 元素是连续出现的，实际上。由 $a_j,j=1,...n$ 组成的矩阵 $A$ 是 $m\times n$ 维的区间矩阵。区间矩阵定义如下，其具有全单模性：

定义3.2 设 $A$ 是 $m\times n$ 维 ${0,1\}$ 矩阵，若该矩阵的每一列中 $1$ 元素连续出现，即如果 $a_{ij}={a_{kj}}=1$ ，且 $k>{i+1}$ ，那么对任意 $i<l<k,a_{lj}=1$ ，则称 $A$ 为区间矩阵。

定理3.6 区间矩阵是全单模矩阵。

所以求解上述问题的线性规划松弛即可得到整数最优解。

3.3.3 最小费用网络流问题

有向图关联矩阵介绍如下：

给定有向图 $D = (V, A)$ ， $V$ 表示顶点集， $A$ 表示弧的集合， $(u, v) \in A$ 表示从顶点 $u$ 流向顶点 $v$ 的弧.记其 $V \times A$ 相关矩阵为 $M$ 。若弧 $a$ 流入顶点 $v$ ，则 $M_{v,a}=1$ ；若弧 $a$ 流出顶点 $v$ ，则 $M_{v,a}=-1$ ；否则 $M_{v,a}=0$ 。

定理3.7 有向图 $D = (V, A)$ 的关联矩阵 $M$ 是全单模矩阵.

给定有向图 $D = (V, A)$ ， $h_{u,v}$ 表示弧 $(u, v)$ 上的最大容量， $b_v$ 表示顶点 $v$ 处的需求量， $c_{u,v}$ 表示弧 $(u, v)$ 上单位流量所需要的费用，记
$V^+(v)=\{u\in V|(v,u)\in A\},\quad V^-(v)=\{u\in V|(u,v)\in A\}$
则最小费用网络流问题可以表述为
$\begin{aligned} &\min \sum_{(u,v)\in A}c_{u,v}x_{u,v},\\ &s.t. \ \sum_{u\in V^+(v)}x_{v,u}-\sum_{u\in V^-(v)}x_{u,v}=b_v,\ \forall v\in V,\\ &\qquad 0\le x_{u,v}\le h_{u,v},\ \forall (u,v)\in A \end{aligned}$

最小费用网络流问题的输入是一个有向图，其中每条边都有一个容量和一个单位流量费用。该图还有一个源点和一个汇点。问题的目标是在满足源点到汇点之间流量约束的情况下，找到一种最小费用的流量分配方案。

记 $M$ 为该图的关联矩阵。上述最小费用网络流问题即
$\min \{c^Tx|Mx=b,\ 0\le x \le h\}$
应当注意的是，若该问题可行，则总需求量之和必为0，即 $\sum_{v\in V}b_v=0$ 。若容 $h_{u,v}$ 及各顶点需求量 $b_v$ 都是整数，由关联矩阵 $M$ 的全单模性可知该最小费用网络流问题有整数最优解。