通过单纯形法获取对象的顶点

Question

我想找到一个物体的顶点，它是由一些方程式决定的。例如。

Eq1:   2x + y +  z <= 12;
Eq2:    x + y      >= 23;
Eq3:    x + y +  z <= 10;

并且受到

的限制

x >= 0
y >= 0
z => 0

它给出了一个六面体。我想知道创建此对象的顶点的位置。

做这个的唯一方法是编写一个代码来检查这个方程的所有可能的变化吗？

array = array with this equations (6 elements)

for( i = 1; i <= array.lenght; i++ ){
 for( j = 1; j <= array.lenght; j++ ){
  for( k = 1; k <= array.lenght; k++ ){
    //and there check is solve of a variation is possible
  }   
 }    
}

Answer 1

这被称为 vertex enumeration problem：将多面体从半 space 表示（这就是您所拥有的 - 一组不等式）转换为顶点表示。文献中有许多算法可以在一般情况下有效地执行此操作。如果您需要尽可能高效，您应该研究其中一种算法。

但是已知只有六个半 space 可以形成有界的非退化六面体，蛮力可能就可以了。每个顶点都在三个面的交点处。因此，取三个不等式的每个子集并计算相应方程的交点。（见下文了解如何做到这一点。）如果交点不存在（例如，两个平面平行）或者如果交点不满足其他三个不等式中的任何一个，那么这三个面不会相交顶点;否则该点是顶点之一。对 ⁶C₃ = 20 种组合中的每一种重复，您应该最终得到八个顶点。

要计算三个不等式的交点，您可以使用一些简单的线性代数。取任意三个不等式，例如：

2x +  y +  z <= 12
 x +  y      >= 23
 x           >= 0

将它们写成矩阵方程：

┌             ┐┌   ┐   ┌    ┐
│ 2    1    1 ││ x │   │ 12 │
│             ││   │   │    │
│ 1    1    0 ││ y │ = │ 23 │
│             ││   │   │    │
│ 1    0    0 ││ z │   │  0 │
└             ┘└   ┘   └    ┘

（矩阵行分别为x、y、z在每个不等式中的系数。）若左边矩阵为奇异矩阵（即行列式为零），没有共同的交点。否则，通过反转矩阵计算解决方案：

┌   ┐   ┌             ┐-1┌    ┐
│ x │   │ 2    1    1 │  │ 12 │
│   │   │             │  │    │
│ y │ = │ 1    1    0 │  │ 23 │
│   │   │             │  │    │
│ z │   │ 1    0    0 │  │  0 │
└   ┘   └             ┘  └    ┘

任何线性代数库都应该能够为您进行此计算，或者 — 因为这是 3D — 您可以使用 Cramer's Rule。然后检查 [x y z] 与其他三个不等式以确定它是否是一个顶点。

通过单纯形法获取对象的顶点

Get vertexes of object by simplex method

java

c++

math

linear-algebra

simplex