档案网站建设与知识管理,wordpress 和dokuwiki,深圳做网站推广的公司,营销公司是什么意思文章目录 多面体定义多面体是凸集多面体重要性质1. 有界多面体#xff08;Convex Polytope#xff09;2. 无界多面体#xff08;Unbounded Polyhedron#xff09;3. 极点表示#xff08;顶点形式#xff09;与极点-极射线表示定理 在数学中#xff0c;
多面体#xff… 文章目录 多面体定义多面体是凸集多面体重要性质1. 有界多面体Convex Polytope2. 无界多面体Unbounded Polyhedron3. 极点表示顶点形式与极点-极射线表示定理 在数学中
多面体polyhedron是指由有限个线性不等式和等式定义的一个凸集合。具体地说
多面体是线性约束条件下的解空间也可以看作是凸多面体的推广。在优化、线性规划和几何中多面体的定义尤为重要。 多面体定义
在 n n n-维空间 R n \mathbb{R}^n Rn中一个多面体可以定义为满足有限个线性不等式和等式的所有点的集合。
标准定义 一个集合 P ⊆ R n P \subseteq \mathbb{R}^n P⊆Rn是多面体当且仅当存在一个矩阵 A ∈ R m × n A \in \mathbb{R}^{m \times n} A∈Rm×n和一个向量 b ∈ R m b \in \mathbb{R}^m b∈Rm使得 P P P可以表示为 P { x ∈ R n : A x ≤ b } 。 P \{ x \in \mathbb{R}^n : A x \leq b \}。 P{x∈Rn:Ax≤b}。
这里 A x ≤ b A x \leq b Ax≤b表示一组线性不等式。 x ∈ R n x \in \mathbb{R}^n x∈Rn表示我们考虑的点在 n n n-维空间中。
更一般地多面体还可以包括一些线性等式即 P { x ∈ R n : A x ≤ b , C x d } 。 P \{ x \in \mathbb{R}^n : A x \leq b, \ C x d \}。 P{x∈Rn:Ax≤b, Cxd}。
其中 C ∈ R k × n C \in \mathbb{R}^{k \times n} C∈Rk×n和 d ∈ R k d \in \mathbb{R}^k d∈Rk定义了线性等式的约束。
在这个定义中多面体的边界由这些不等式和等式所定义的半空间的交集来确定。
所以多面体的定义为 一个集合 P ⊆ R n P \subseteq \mathbb{R}^n P⊆Rn是多面体当且仅当存在一个矩阵 A ∈ R m × n A \in \mathbb{R}^{m \times n} A∈Rm×n和一个向量 b ∈ R m b \in \mathbb{R}^m b∈Rm C ∈ R k × n C \in \mathbb{R}^{k \times n} C∈Rk×n和 d ∈ R k d \in \mathbb{R}^k d∈Rk使得 P { x ∈ R n : A x ≤ b , C x d } P \{ x \in \mathbb{R}^n : A x \leq b, \ C x d \} P{x∈Rn:Ax≤b, Cxd}
其中 A x ≤ b A x \leq b Ax≤b是一组定义边界的线性不等式【半空间】。 C x d C x d Cxd是一组定义面的线性等式可选【超平面】。
多面体是凸集
从几何上看多面体可以被认为是一个凸的几何对象。其几何结构可以分解为顶点、边、面等取决于空间的维数。例如
在三维空间中一个多面体可能是立方体、四面体等由平面限定的几何体。在二维空间中满足线性不等式的集合即为多边形。
多面体之所以凸是因为线性不等式和等式的交集形成了一个凸集。这意味着对于任何位于多面体内的两点 x , y ∈ P x, y \in P x,y∈P连接这两点的线段也完全位于 P P P内即 ∀ λ ∈ [ 0 , 1 ] , λ x ( 1 − λ ) y ∈ P 。 \forall \lambda \in [0, 1], \ \lambda x (1 - \lambda) y \in P。 ∀λ∈[0,1], λx(1−λ)y∈P。
多面体重要性质 有界多面体当多面体的定义约束使得 P P P的边界是有限的时我们称其为有界多面体通常也叫做凸多面体convex polytope。 无界多面体当多面体的定义约束不完全封闭 P P P时该多面体可能是无界的。 极点表示顶点形式多面体也可以通过顶点的凸组合来表示。这是极点-极射线表示定理的内容。
1. 有界多面体Convex Polytope
一个有界多面体或称为凸多面体是一个由有限个线性不等式所定义的有限闭凸集合即它的边界是有限的。这类多面体的几何形状是封闭的并且在有限的空间中存在。
数学定义
在 R n \mathbb{R}^n Rn 中一个集合 P P P 称为有界多面体或凸多面体当且仅当存在有限个向量 v 1 , v 2 , … , v k ∈ R n v_1, v_2, \dots, v_k \in \mathbb{R}^n v1,v2,…,vk∈Rn 和权重 λ i ≥ 0 \lambda_i \geq 0 λi≥0满足 P { x ∈ R n : x ∑ i 1 k λ i v i , ∑ i 1 k λ i 1 } 。 P \left\{ x \in \mathbb{R}^n : x \sum_{i1}^k \lambda_i v_i, \quad \sum_{i1}^k \lambda_i 1 \right\}。 P{x∈Rn:xi1∑kλivi,i1∑kλi1}。
也就是说 P P P 是由其顶点的凸组合convex combination所生成的集合。 凸组合凸组合表示权重的非负性和总和为1从而保证了组合后的点仍然在多面体内部。 这种定义也表明有界多面体是凸的即如果 x , y ∈ P x, y \in P x,y∈P那么对任意 λ ∈ [ 0 , 1 ] \lambda \in [0,1] λ∈[0,1] λ x ( 1 − λ ) y ∈ P \lambda x (1 - \lambda) y \in P λx(1−λ)y∈P。 有限个向量的非负线性组合系数非负且求和为1有界多面体必定是凸的 有界多面体是顶点的凸组合构成的
2. 无界多面体Unbounded Polyhedron
一个无界多面体是由线性不等式或等式约束定义的集合但这些约束并不完全限制集合在空间中的边界使得多面体在某些方向上可以延伸到无限远。
数学定义
在 R n \mathbb{R}^n Rn 中一个集合 P P P 称为无界多面体当且仅当它可以表示为 P { x ∈ R n : A x ≤ b } P \left\{ x \in \mathbb{R}^n : A x \leq b \right\} P{x∈Rn:Ax≤b}
其中 A ∈ R m × n A \in \mathbb{R}^{m \times n} A∈Rm×n 是一个矩阵 b ∈ R m b \in \mathbb{R}^m b∈Rm 是向量且存在非零向量 d ∈ R n d \in \mathbb{R}^n d∈Rn使得 x λ d ∈ P , ∀ λ ≥ 0 。 x \lambda d \in P, \quad \forall \lambda \geq 0。 xλd∈P,∀λ≥0。
这表明可以沿着某个方向 d d d 无限地延伸 x x x而仍然保持在 P P P 内因此 P P P 是无界的。
无界性多面体的无界性来自于满足约束 A x ≤ b A x\leq b Ax≤b 的同时存在一条无限延伸的方向。满足线性不等式的时候存在一条无限延伸的方向可以延伸到无限远
3. 极点表示顶点形式与极点-极射线表示定理
极点表示定理或称顶点形式指出每个多面体都可以表示为其极点顶点的凸组合且对于无界多面体还需要包含其极射线的正组合。
极点极点是多面体的顶点表示那些不能通过其他点的凸组合来表示的点。极射线对于无界多面体极射线或称为方向向量是那些可以沿其方向无限延伸的方向。
数学定义
设 P ⊆ R n P \subseteq \mathbb{R}^n P⊆Rn 是一个多面体。根据极点-极射线表示定理 P P P 可以表示为其极点和极射线的凸组合 P { x ∈ R n : x ∑ i 1 k λ i v i ∑ j 1 l μ j d j , λ i ≥ 0 , ∑ i 1 k λ i 1 , μ j ≥ 0 } 。 P \left\{ x \in \mathbb{R}^n : x \sum_{i1}^k \lambda_i v_i \sum_{j1}^l \mu_j d_j, \quad \lambda_i \geq 0, \ \sum_{i1}^k \lambda_i 1, \ \mu_j \geq 0 \right\}。 P{x∈Rn:xi1∑kλivij1∑lμjdj,λi≥0, i1∑kλi1, μj≥0}。
其中 v 1 , v 2 , … , v k v_1, v_2, \dots, v_k v1,v2,…,vk 是 P P P 的极点 d 1 , d 2 , … , d l d_1, d_2, \dots, d_l d1,d2,…,dl 是 P P P 的极射线 λ i \lambda_i λi 和 μ j \mu_j μj 分别为非负权重使得点 x x x 是这些顶点和射线的线性组合。
解释
有界多面体仅由其极点的凸组合生成因此没有极射线项无界多面体需要极点和极射线的组合才能表示出所有在多面体内部的点。有界多面体极点的凸组合没有极线无界多面体极点极线多面体内部
