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

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

Это известно как проблема перечисления вершин: преобразовать многогранник из представления в полупространстве (которое есть у вас - набор неравенств) в представление вершины. В литературе существует ряд алгоритмов для эффективного выполнения этого в общем случае. Если вам нужно быть максимально эффективным, вы должны изучить один из этих алгоритмов.

Но только с шестью полупространствами, которые, как известно, образуют ограниченный невырожденный шестигранник, грубая сила, вероятно, просто прекрасна. Каждая вершина находится на пересечении трех граней. Поэтому возьмите каждое подмножество из трех неравенств и вычислите точку пересечения соответствующих уравнений. (См. Ниже, как это сделать.) Если пересечение не существует (например, две плоскости параллельны) или если точка пересечения не удовлетворяет ни одному из трех других неравенств, то эти три грани не встречаются на вершина; в противном случае точка является одной из вершин. Повторите эти действия для каждой из ⁶ комбинаций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, вы можете использовать правило Крамера. Тогда проверь [x y z] против трех других неравенств, чтобы определить, если это вершина.