什么叫网站空间,企查查询官网入口,保定百度首页优化,室内效果图用什么软件做最好整数规划——第三章 全单模矩阵
若线性规划问题的约束矩阵为全单模矩阵#xff0c;则该问题可行域的顶点都是整数点#xff0c;从而线性规划与整数规划的最优解相同。
3.1 全单模性与最优性
考虑线性整数规划问题#xff1a; (IP) min c T x , s . t . A x ≤ b , x …整数规划——第三章 全单模矩阵
若线性规划问题的约束矩阵为全单模矩阵则该问题可行域的顶点都是整数点从而线性规划与整数规划的最优解相同。
3.1 全单模性与最优性
考虑线性整数规划问题 (IP) min c T x , s . t . A x ≤ b , x ∈ Z n \text{(IP)}\quad\begin{aligned} \min c^Tx,\\ s.t.\ Ax\le b,\\ \qquad x\in \Z_^n \end{aligned} (IP)mincTx,s.t. Ax≤b,x∈Zn 其中 A A A 是 m × n m×n m×n 整数矩阵 b b b 是 n n n 维整数向量。用如下线性规划作为其松弛问题 (LP) min c T x , s . t . A x ≤ b , x ∈ R n \text{(LP)}\quad\begin{aligned} \min c^Tx,\\ s.t.\ Ax\le b,\\ \qquad x\in \R_^n \end{aligned} (LP)mincTx,s.t. Ax≤b,x∈Rn 若线性松弛问题存在最优解且其可行集合 $P{x\in \R_^n|Ax\le b} $ 的所有顶点都是整数点则线性规划问题必有整数最优解。因此求解线性松弛问题(LP)就可得到原整数规划问题§的最优解。下面给出一个保证问题(LP)的最优解是整数点的充分条件
定理3.1 若线性规划问题(LP)的最优基矩阵B满足 det ( B ) ± 1 \text{det}(B)\pm1 det(B)±1这里 B B B 是矩阵 ( A , I ) (A,I) (A,I) 的 m × m m×m m×m 维子方阵则线性规划问题(LP)的最优解是整数解。
定义3.1 设矩阵 A A A 是 m × n m×n m×n 整数矩阵。若矩阵 A A A 的任意子方阵的行列式等于0,1或者-1则称矩阵A为全单模矩阵。
易知若整数规划IP中的矩阵 A A A 是全单模矩阵求解线性规划LP等价于求解整数规划IP)。
性质3.1若矩阵 A A A 是全单模矩阵则矩阵中元素a0,1或者-1。
定理3.2 设矩阵 A A A 是全单模矩阵向量 b b b 是整数向量则多面体 P { x ∈ R n ∣ A x ≤ b } P\{x\in \R_^n|Ax\le b\} P{x∈Rn∣Ax≤b} 的顶点都是整数点。
定理3.3 若对任意整数向量 b b b 多面体 P { x ∈ R n ∣ A x ≤ b } P\{x\in \R_^n|Ax\le b\} P{x∈Rn∣Ax≤b} 的顶点都是整数点则 A A A 是全单模矩阵。
3.2 全单模矩阵的性质
性质3.2 设整数矩阵 A A A 是全单模矩阵对 A A A 进行以下运算不改变其全单模性
对矩阵 A A A 进行转置矩阵 ( A , I ) (A,I) (A,I) 是全单模的去掉 A A A 的一行或者一列)将 A A A 的一行或者一列乘以-1互换 A A A 的两行或者两列对 A A A 进行转轴运算.
定理3.4 矩阵 A A A 是全单模矩阵等价于对于每个集合 J ⊆ N { 1 , 2 , . . . , n } J\sube N\{1,2,...,n\} J⊆N{1,2,...,n}必存在 J J J 的分割 J 1 , J 2 J_1,J_2 J1,J2 使得 ∣ ∑ j ∈ J 1 a i j − ∑ j ∈ J 2 a i j ∣ ≤ 1 , i 1 , . . . , m . \left| \sum_{j\in J_1}a_{ij} -\sum_{j\in J_2}a_{ij}\right|\le 1,\quad i1,...,m. j∈J1∑aij−j∈J2∑aij ≤1,i1,...,m. 推论3.3 设矩阵 A A A 是 { 0 , 1 , − 1 } \{0,1,-1\} {0,1,−1}矩阵并且每列至多有两个非零元素则矩阵 A A A 是全单模矩阵当且仅当存在 A A A 的行分割 Q 1 , Q 2 Q_1,Q_2 Q1,Q2 使得同一列中的两个非零元素满足以下条件
若符号相同则一个元素位于 Q 1 Q_1 Q1,另一元素位于 Q 2 Q_2 Q2若特号相反则这两个元素同时属于 Q 1 Q_1 Q1,或者同时属于 Q 2 Q_2 Q2。
由以上讨论可得到一个易于验证的全单模矩阵的充分条件
推论3.4 设矩阵 A A A 的任意元素都是0,1或者一1若 A A A 满足以下两个条件则矩阵 A A A 是全单模的 A A A 的每一列至多含有两个非零元素若某列含有两个非零元素则两个元素之和为0.
3.3 全单模矩阵在网络问题中的应用
3.3.1 二部图
给定无向图 G ( V , E ) G(V,E) G(V,E)其中 V V V 表示顶点集合 E E E 表示边集合。定义图 G G G 的关联矩阵 M M M 其行和列分别用顶点集 V V V 和边集 E E E 标记若边 e e e 经过项点 v v v ,则 M v , e 1 M_{v,e}1 Mv,e1否则 M v , e 0 M_{v,e}0 Mv,e0。
若一个图 G ( V , E ) G(V,E) G(V,E) 的顶点集合 V V V 可分解成两个非空子集 V 1 , V 2 V_1,V_2 V1,V2使得 E E E 中每条边的两个端点分别属于 V 1 , V 2 V_1,V_2 V1,V2则称该图为二部图。下面定理表明无向图的关联矩阵的全单模性与二部图之间的等价性。
定理3.5 令 G ( V , E ) G(V,E) G(V,E) 表示无向图 M M M 表示图 G G G 的 V × E V\times E V×E 关联矩阵则 M M M 是全单模矩阵当且仅当图 G G G 是二部图。
3.3.2 指派问题
指派问题是二部图问题的一种特殊情况是指将 n n n 项任务恰当地分配给 n n n 个工人每个工人只能执行一项任务。由于每个工人完成不同工作所的成本不同我们的目的是在保证各项任务完成的前提下最小化成本。令表示 c i j c_{ij} cij 由工人 i i i 完成任务 j j j 的成本则最小化成本的指派问题可表述如下 min ∑ i 1 n ∑ j 1 n c i j x i j , s . t . ∑ j 1 n x i j 1 , i 1 , . . . , n , ∑ i 1 n x i j 1 , j 1 , . . . , n , x i j ∈ { 0 , 1 } , i , j 1 , . . . , n . \begin{aligned}\min \sum_{i1}^n\sum_{j1}^n c_{ij}x_{ij},\\ s.t.\ \sum_{j1}^nx_{ij} 1,\ i 1,...,n,\\ \quad\quad\sum_{i 1}^n x_{ij} 1,j1,...,n, \\ \quad\quad x_{ij}\in \{0,1\},\quad i,j 1,...,n. \end{aligned} mini1∑nj1∑ncijxij,s.t. j1∑nxij1, i1,...,n,i1∑nxij1,j1,...,n,xij∈{0,1},i,j1,...,n. 记 U U U 表示工人集合 V V V 表示任务集合在此集合上建立边集 E E E若工人 i i i 能够胜任任务 j j j ,则边 ( i , j ) ∈ E (i,j)∈E (i,j)∈E 。故图 G ( U , V , E ) G(U,V,E) G(U,V,E) 是二部图。由于二部图的关联矩阵是全单模矩阵则求解其线性规划松弛问题即可得到整数最优解.
另一类指派问题是将工人们分派到不同小组进行轮班称之为排班问题。假设工作时间有 m m m 个小时共有 n n n 次轮班每一次轮班需要连续工作几个小时。第 j j j 次轮班用 m m m 维 0 − 1 0-1 0−1 向量 a j a_j aj 表示若在第 i i i 个小时被排在第 j j j 次轮班中则 a i j 1 a_{ij}1 aij1 否则 a i j 0 a_{ij}0 aij0 。所以向量 中 1 元素是连续出现的实际上。由 a j , j 1 , . . . n a_j,j1,...n aj,j1,...n 组成的矩阵 A A A 是 m × n m\times n m×n 维的区间矩阵。区间矩阵定义如下其具有全单模性
定义3.2 设 A A A 是 m × n m\times n m×n 维 { 0 , 1 } \{0,1\} {0,1} 矩阵若该矩阵的每一列中 1 1 1 元素连续出现即如果 a i j a k j 1 a_{ij}{a_{kj}}1 aijakj1且 k i 1 k{i1} ki1那么对任意 i l k , a l j 1 ilk,a_{lj}1 ilk,alj1则称 A A A 为区间矩阵。
定理3.6 区间矩阵是全单模矩阵。
所以求解上述问题的线性规划松弛即可得到整数最优解。
3.3.3 最小费用网络流问题
有向图关联矩阵介绍如下
给定有向图 D ( V , A ) D(V,A) D(V,A) V V V 表示顶点集 A A A 表示弧的集合 ( u , v ) ∈ A (u,v)∈A (u,v)∈A 表示从顶点 u u u 流向顶点 v v v 的弧.记其 V × A V×A V×A 相关矩阵为 M M M 。若弧 a a a 流入顶点 v v v则 M v , a 1 M_{v,a}1 Mv,a1若弧 a a a 流出顶点 v v v则 M v , a − 1 M_{v,a}-1 Mv,a−1否则 M v , a 0 M_{v,a}0 Mv,a0。
定理3.7 有向图 D ( V , A ) D(V,A) D(V,A)的关联矩阵 M M M 是全单模矩阵.
给定有向图 D ( V , A ) D(V,A) D(V,A) h u , v h_{u,v} hu,v 表示弧 ( u , v ) (u,v) (u,v) 上的最大容量 b v b_v bv 表示顶点 v v v 处的需求量 c u , v c_{u,v} cu,v 表示弧 ( u , v ) (u,v) (u,v) 上单位流量所需要的费用记 V ( v ) { u ∈ V ∣ ( v , u ) ∈ A } , V − ( v ) { u ∈ V ∣ ( u , v ) ∈ A } V^(v)\{u\in V|(v,u)\in A\},\quad V^-(v)\{u\in V|(u,v)\in A\} V(v){u∈V∣(v,u)∈A},V−(v){u∈V∣(u,v)∈A} 则最小费用网络流问题可以表述为 min ∑ ( u , v ) ∈ A c u , v x u , v , s . t . ∑ u ∈ V ( v ) x v , u − ∑ u ∈ V − ( v ) x u , v b v , ∀ v ∈ V , 0 ≤ x u , v ≤ h u , v , ∀ ( u , v ) ∈ 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} min(u,v)∈A∑cu,vxu,v,s.t. u∈V(v)∑xv,u−u∈V−(v)∑xu,vbv, ∀v∈V,0≤xu,v≤hu,v, ∀(u,v)∈A 最小费用网络流问题的输入是一个有向图其中每条边都有一个容量和一个单位流量费用。该图还有一个源点和一个汇点。问题的目标是在满足源点到汇点之间流量约束的情况下找到一种最小费用的流量分配方案。 记 M M M 为该图的关联矩阵。上述最小费用网络流问题即 min { c T x ∣ M x b , 0 ≤ x ≤ h } \min \{c^Tx|Mxb,\ 0\le x \le h\} min{cTx∣Mxb, 0≤x≤h} 应当注意的是若该问题可行则总需求量之和必为0即 ∑ v ∈ V b v 0 \sum_{v\in V}b_v0 ∑v∈Vbv0。若容 h u , v h_{u,v} hu,v 及各顶点需求量 b v b_v bv 都是整数由关联矩阵 M M M 的全单模性可知该最小费用网络流问题有整数最优解。
例3.2 有向图 G G G 由图3.1给出图 G G G 的关联矩阵和各顶点需求量由表3.1给出
