Параллельное программирование


              

4 ребер, образующих вершину E.


Находим q5(13, 8, 4)
0. Добавляем q5 в (4.9), полагаем полностью известным число p = 4 ребер, образующих вершину E. Т.е. вместо (4.9) получаем

(4.10)

Каждую возможную грань, определяемую двумя (n-1) уравнениями плоскостей из (4.10), будем решать совместно со всеми плоскостями из (4.8), не вошедшими в (4.10), — с гранями q4, q6, q7, q8, q9.
Первая такая система имеет вид

(4.11)

Ее решение (535, 8,7, -517,2) содержит отрицательную составляющую. Т.е. эта точка не принадлежит R. Если бы решение было не отрицательным, мы должны были бы проверить выполнение всех ограничений (4.7), не представленных в (4.11).
Можно показать, что в выпуклом многограннике несуществующее ребро не вызовет появления "ложной" вершины, и достаточно проверить (4.7).
Системы

имеют не положительное решение.
Следующая испытываемая система линейных уравнений на основе двух уравнений из (4.10) и не входящих в (4.10) уравнений из (4.8), имеет вид

Ее решение — приблизительно точка (5,2, 9,4, 4) не является вершиной R, т.к. не удовлетворяет всем ограничениям (9.7), q5(5,2, 9,4, 4) < 0.
Следующая испытываемая система имеет вид

Ее решением является вершина A (3, 0, 3), Z(A) = 141 < 592.
Т.к. мы нашли вершину на "другом конце" ребра, анализ данного ребра прекращаем.
Следующее исследуемое ребро, исходящее из вершины E, определяется подсистемой

которая должна решаться совместно с уравнениями q4 = 0, q6 = 0, q7
= 0, q8 = 0, q9 = 0.
Первая же система
определяет вершину L (6, 10, 4). Однако Z(L) = 440 < 592.
Следующее возможное ребро, исходящее из вершины E, определяется комбинацией

Решая ее совместно с другими гранями R, - q4 = 0, q6 = 0, q7
= 0, q8 = 0, q9 = 0, пытаемся найти другую вершину в R, смежную E.
Очередная решаемая система уравнений

имеет не отрицательное решение (13,625, 8,7, 4,175). Проверяем выполнение ограничений (9.7), не представленных в решенной системе. Находим, что q1(13,625, 8,7, 4,195) < 0. Этой проверки достаточно для вывода о том, что найденная точка не является вершиной многогранника R.

Содержание  Назад  Вперед