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



              

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


нулевую строку матрицы A, что опять говорит в пользу подстановок!

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

 \begin{equation} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{11} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

Ее решение Y1 = (0, 0, 4, 7, 5, 6, 0, 0, 0, 3, 5, 0) определяет значение целевой функции Z(Y1) = 89 < 104.

Полагаем Y0 := Y1. Теперь мы должны перемещаться по ребрам из вновь найденной вершины в поисках вершины с еще меньшим значением целевой функции. Придется перебрать до 6 ? 6 = 36 вариантов такого перемещения. Однако, достигнув ответа задачи в [15], положимся на его правильность и прекратим рассмотрение примера.




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