Получить вершины объекта методом симплекс

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: преобразовать многогранник из полупространства представления (что у вас есть — набор неравенств) в представлении вершины. В литературе имеется ряд алгоритмов, позволяющих сделать это эффективно в общем случае. Если вам нужно быть максимально эффективным, вы должны изучить один из этих алгоритмов.

Но только шесть полупространств, которые, как известно, образуют ограниченный невырожденный гексаэдр, грубая сила, вероятно, просто прекрасна. Каждая вершина находится на пересечении трех граней. Поэтому возьмем каждое подмножество трех неравенств и вычислим точку пересечения соответствующих уравнений. (См. Ниже, как это сделать.) Если пересечение не существует (например, две из плоскостей параллельны) или если точка пересечения не удовлетворяет ни одному из трех других неравенств, то эти три грани не встречаются при вершина; в противном случае точка является одной из вершин. Повторите для каждого из C = 20 комбинаций, и вы должны иметь восемь вершин.

Чтобы вычислить точку пересечения трех неравенств, вы можете использовать некоторую простую линейную алгебру. Возьмем любые три неравенства, например:

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

Запишите их в виде матричного уравнения: (. Матричные строки являются коэффициенты x, y и z в каждом неравенстве)

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

Если матрица слева сингулярна (т. е. детерминант равен нулю), нет общей точки пересечения. В противном случае вычислить решение переворачивания матрицы:

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

Любых линейная алгебра библиотека должна быть в состоянии сделать это для Вас расчета или — поскольку это 3D — вы можете использовать Cramer's Rule. Затем проверьте [x y z] на три других неравенства, чтобы определить, является ли это вершиной.