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



              

Пример - часть 2


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

 \begin{equation} \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_3 = 0 \hfill \\ q_5 = 0 \hfill \\ \end{gathered} \right. \end{equation}

(4.10)

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

Первая такая система имеет вид

 \begin{equation} \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_4 = 0 \hfill \\ \end{gathered} \right. \end{equation}

(4.11)

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

Можно показать, что в выпуклом многограннике несуществующее ребро не вызовет появления "ложной" вершины, и достаточно проверить (4.7).

Системы

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_6 = 0 \hfill \\ \end{gathered} \right. ,\quad \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_7 = 0 \hfill \\ \end{gathered} \right.,\quad \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_8 = 0 \hfill \\ \end{gathered} \right.,\quad \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \hfill \\ q_9 = 0 \hfill \\ \end{gathered} \right.

имеют не положительное решение.

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

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_3 = 0 \hfill \\ q_4 = 0 \hfill \\ \end{gathered} \right..

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

Следующая испытываемая система имеет вид

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_3 = 0 \hfill \\ q_6 = 0 \hfill \\ \end{gathered} \right..

Ее решением является вершина A (3, 0, 3), Z(A) = 141 < 592.

Т.к. мы нашли вершину на "другом конце" ребра, анализ данного ребра прекращаем.

Следующее исследуемое ребро, исходящее из вершины E, определяется подсистемой

 \begin{gathered} q_1 = 0\\ q_5 = 0, \end{gathered}

которая должна решаться совместно с уравнениями q4 = 0, q6 = 0, q7

= 0, q8 = 0, q9 = 0.

Первая же система

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_5 = 0 \hfill \\ q_4 = 0 \hfill \\ \end{gathered} \right.
определяет вершину L (6, 10, 4). Однако Z(L) = 440 < 592.

Следующее возможное ребро, исходящее из вершины E, определяется комбинацией

 \begin{gathered} q_2 = 0\\ q_3 = 0. \end{gathered}

Решая ее совместно с другими гранями R, - q4 = 0, q6 = 0, q7

= 0, q8 = 0, q9 = 0, пытаемся найти другую вершину в R, смежную E.

Очередная решаемая система уравнений

 \left\{ \begin{gathered} q_2 = 0 \hfill \\ q_3 = 0 \hfill \\ q_4 = 0 \hfill \\ \end{gathered} \right.

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




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