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



              

Параллельный алгоритм решения - часть 4


Решение задачи найдено в том случае, если после перебора всех смежных вершин не отыскивается вершина с меньшим значением целевой функции.

Продолжим рассмотрение примера.

Итак, (5.8) — исходный вид системы уравнений, (5.9) — комбинация нулей ("отсутствующие" столбцы в (5.7) выделены), (5.8) и (5.9) определяют вершину Y0.

Исключим из (5.9) уравнение y1 = 0, а оставшуюся систему, с учетом остальных нулей из комбинации (5.9), будем решать совместно с уравнениями

y3 = 0, y4 = 0, y6 = 0, y8 = 0, y9 = 0, y12 = 0. (5.10)

Значит, в (5.8) положим первоначально y3 = 0 вместо y1 = 0. Левая часть шестого уравнения (последняя строка матрицы А) обратилась в нуль.

Положим y4 = 0 вместо y1 = 0. Получим систему

 \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_3\\y_6\\y_8\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

Из нее, как и ранее, за два шага подстановки находим y3 = 9, y6 = 9, y9 = 5, а затем — y1 = 2, y8 = 2, y12 = 3.

Таким образом, найдено новое допустимое решение Y1 = (2, 0, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) =149 > 141. Найденную вершину отвергаем. Вместе с тем, т.к. мы нашли вершину "на другом конце" анализируемого ребра, то и анализ этого ребра прекращаем.

Приступаем к анализу следующего ребра, исключив из (5.9) уравнение y2 = 0. Оставшуюся систему, с учетом остальных нулей из (5.9), будем решать совместно с теми же уравнениями (5.10).

Положим в (5.8) y3 = 0 вместо y2 = 0. Последняя строка матрицы A стала нулевой.

Замена y4 = 0 вместо y2 = 0 приводит к системе

 \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ \end{pmatrix} \times \begin{pmatrix} y_2\\y_3\\y_6\\y_8\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

На ее основе находим новый вектор — допустимое решение Y1 = (0, 2, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) = 151 > 141. Найденную вершину также отвергаем. Ребро исследовано полностью.

Исключим из (5.9) уравнение y5 = 0, а оставшуюся систему, с учетом остальных нулей из (5.9), будем решать совместно с теми же уравнениями (5.10).

Положим в (5.8) y3 = 0 вместо y5 = 0. Последняя строка матрицы A обратится в нуль.

Положим y4 = 0 вместо y5 = 0. В первом уравнении не выполняется ограничение по y3 (y3 = 9).

Положим y6 = 0 вместо y5 = 0. Пятая строка A обратилась в нулевую.

Положим y8 = 0 вместо y5 = 0.


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