|
|
相关文章推荐
|
深沉的电脑桌 · 學習幾何之立體摺紙系統__臺灣博碩士論文知識 ...· 10 月前 · |
|
|
深沉的电脑桌 · 卡塔蘭多面體的綜合作圖= ...· 10 月前 · |
|
|
深沉的电脑桌 · 【凸优化】3 多面体，单纯形，半正定锥- ...· 10 月前 · |
|
|
深沉的电脑桌 · 多面体定义+多面体是凸集+多面体的重要性质_ ...· 10 月前 · |
在数学中， 多面体 （polyhedron）是指由有限个线性不等式和等式定义的一个凸集 合。具体地说， 多面体是线性约束条件下的解空间 ，也可以看作是凸多面体的推广。在优化、线性规划和几何中，多面体的定义尤为重要。
多面体定义
C x = d 是一组定义面的 线性等式（可选）【超平面 】。多面体是凸集
从几何上看， 多面体可以被认为是一个凸的几何对象。其几何结构可以分解为 顶点 、 边 、 面 等，取决于空间的维数 。例如：
- 在三维空间中，一个多面体可能是立方体、四面体等，由平面限定的几何体。
- 在二维空间中，满足线性不等式的集合即为多边形。
多面体之所以凸，是因为 线性不等式和等式的交集形成了一个凸集 。这意味着，对于任何位于多面体内的两点 P 时，该多面体可能是无界的。
极点表示（顶点形式） ：多面体也可以通过顶点的凸组合来表示。这是 极点-极射线表示定理 的内容。
1. 有界多面体（Convex Polytope）
一个 有界多面体，或称为 凸多面体 ，是一个由有限个线性不等式所定义的有限闭凸集合，即它的边界是有限的 。这类多面体的几何形状是封闭的，并且在有限的空间中存在。
数学定义 ：
P = \left\{ x \in \mathbb{R}^n : x = \sum_{i=1}^k \lambda_i v_i, \quad \sum_{i=1}^k \lambda_i = 1 \right\}。 P = { x ∈ R n : x = i = 1 ∑ k λ i v i , i = 1 ∑ k λ i = 1 } 。
也就是说， λ x + ( 1 − λ ) y ∈ P 。
有限个向量的非负线性组合（系数非负且求和为1）+有界多面体必定是凸的+ 有界多面体是顶点的凸组合构成的
一个 无界多面体 是由 线性不等式或等式约束定义的集合，但这些约束并不完全限制集合在空间中的边界，使得多面体在某些方向上可以 延伸到无限远 。
数学定义 ：
A x ≤ b 的同时，存在一条无限延伸的方向。3. 极点表示（顶点形式）与极点-极射线表示定理
极点表示定理 （或称 顶点形式 ）指出， 每个多面体都可以表示为其极点（顶点）的凸组合，且对于无界多面体，还需要包含其极射线的正组合。
- 极点 ：极点是多面体的顶点，表示那些不能通过其他点的凸组合来表示的点。
- 极射线 ：对于无界多面体，极射线（或称为方向向量）是那些可以沿其方向无限延伸的方向。
数学定义 ：
P = \left\{ x \in \mathbb{R}^n : x = \sum_{i=1}^k \lambda_i v_i + \sum_{j=1}^l \mu_j d_j, \quad \lambda_i \geq 0, \ \sum_{i=1}^k \lambda_i = 1, \ \mu_j \geq 0 \right\}。 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 } 。
1.标准型的表示
通常将
多面体
P = {x ∈ Rn | Ax = b, x ≥ 0} 称为
多面体
的标准型，即
多面体
中所有约束都为等式。其中 A 为 m×n 的矩阵（通常认为m ≤ n）。
现在不妨通过标准型再来回顾一下基解。基解必然包含 n 个严格约束，而对于一个标准型来说，除了 n 个非负约束之外，其余的 m 个约束皆为等式约束，若想找到一个基解，需另寻找 n - m 个严格约束，即令 n - m 个非负约束成为严格约束，即存在 n - m 个变量的值为0，我们称这样的变量为非基变量，而其余的 m 个
一、
多面体
（
Polyhedron
）
P={x∣ajTx≤bj j=1,⋯ ,m,cjTx=dj j=1,⋯ ,r}P=\{x|a_j^Tx\le b_j\;j=1,\cdots,m,c_j^Tx=d_j\;j=1,\cdots,r\}P={x∣ajTx≤bjj=1,⋯,m,cjTx=djj=1,⋯,r}
有界
多面体
二、单纯形（Simplex）
一种特殊的
多面体
。
Rn\R^nRn空间中选择v0,⋯ ,vkv_0,\cdots,v
在学习列生成
和
分解算法的时候，会频繁用到线性规划
和
对偶的知识，可以说LP
和
DP是基础。因此理解线性规划
和
对偶的本质是很重要的。
单纯形法是纯代数运算，从一个顶点跳到另一个顶点；且我们知道最优解一定在顶点取得，可是为什么在顶点一定会取得最优解？为什么从一个顶点跳到另一顶点，通过进基出基就可以实现，它俩为什么是一一对应的？除此以外，在分解算法中的极点
和
极射线
和
LP的解是什么样的对应关系？
这些问题，应该说必须了解了线性规划
和
对偶的本质才能够深刻理解，而不至于陷入机械无脑的计算。大概看了慕课的课程，感觉山东大
如图，对于此非空闭
凸
集
，红色点均为极点（）。从图中可以发现极点不能被任意两不同点的严格
凸
组合得到。
如果C为非空闭
凸
集
，C中至少含有一个极点，当且仅当C中不存在直线。
C为中的闭
凸
集
，，如果对于，都有，则称为C的方向。
为C的方向，如果对于，都有，则称与方向不同。
为C的方向，若，其中，则称为C的极方向。
凸
集
C存在极方向，当且仅当C无界。
（标准线性规划问题的其可行域）为非空
多面体
，则其极点
集
非空，且存在有限个极点