получить вершины объекта симплекс-методом
Я хотел бы найти вершины объектов, которые определяются некоторыми уравнениями.
Например.
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
}
}
}
Решение
Это известно как задача перечисления вершин: преобразовать многогранник из представления в полупространстве (а это то, что у вас есть — набор неравенств) в представление вершины. В литературе существует ряд алгоритмов для эффективного выполнения этого в общем случае. Если вам нужно быть максимально эффективным, вы должны изучить один из этих алгоритмов.
Но только с шестью полупространствами, которые, как известно, образуют ограниченный невырожденный шестигранник, грубая сила, вероятно, просто прекрасна. Каждая вершина находится на пересечении трех граней. Поэтому возьмите каждое подмножество из трех неравенств и вычислите точку пересечения соответствующих уравнений. (См. Ниже, как это сделать.) Если пересечение не существует (например, две плоскости параллельны) или если точка пересечения не удовлетворяет ни одному из трех других неравенств, то эти три грани не встречаются на вершина; в противном случае точка является одной из вершин. Повторите для каждого из 6С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 │
└ ┘└ ┘ └ ┘
(Строки матрицы представляют собой коэффициенты x, y, а также z в каждом неравенстве.) Если матрица слева сингулярна (т.е. определитель равен нулю), то нет общей точки пересечения. В противном случае вычислите решение, перевернув матрицу:
┌ ┐ ┌ ┐-1┌ ┐
│ x │ │ 2 1 1 │ │ 12 │
│ │ │ │ │ │
│ y │ = │ 1 1 0 │ │ 23 │
│ │ │ │ │ │
│ z │ │ 1 0 0 │ │ 0 │
└ ┘ └ ┘ └ ┘
Любая библиотека линейной алгебры должна быть в состоянии выполнить этот расчет за вас, или, поскольку это 3D, вы можете использовать Правило Крамера. Тогда проверь [x y z] против трех других неравенств, чтобы определить, если это вершина.
Другие решения
Других решений пока нет …