2

我想找到一个由一些方程确定的对象的顶点。例如。

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
  }   
 }    
}
4

1 回答 1

3

这被称为顶点枚举问题:将多面体从半空间表示(这是你所拥有的——一组不等式)转换为顶点表示。在一般情况下,文献中有许多算法可以有效地做到这一点。如果您需要尽可能高效,您应该研究其中一种算法。

但是只有六个半空间可以形成一个有界的非退化六面体,蛮力可能就可以了。每个顶点都在三个面的交点处。因此,取三个不等式的每个子集并计算相应方程的交点。(如何做到这一点见下文。)如果不存在交点(例如,两个平面平行)或者如果交点不满足其他三个不等式中的任何一个,那么这三个面不会在顶点; 否则该点是顶点之一。对6 个C 3 = 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 │
└             ┘└   ┘   └    ┘

(矩阵行是每个不等式中 、 和 的系数xyz如果左边的矩阵是奇异的(即行列式为零),则没有共同的交点。否则,通过反转矩阵来计算解:

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

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

于 2016-03-14T03:54:42.297 回答