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



              

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


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

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

Отсюда Y1 = (2, 0, 9, 0, 3, 8, 0, 0, 0, 1, 0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее ребро, исключив в системе (5.14) уравнение y2 = 0 и заменяя его последовательно уравнениями из (5.16).

Замена y4 = 0 вместо y2 = 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 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_2\\y_3\\y_5\\y_6\\y_{10}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

Находим Y1 = (0, 2, 9, 0, 5, 6, 0, 0, 0, 1, 0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее ребро, исключив в системе (5.14) уравнение y7 = 0 и заменяя его последовательно уравнениями из (5.16).

Замена y3 = 0 вместо y7 = 0 приводит к тому, что в первом уравнении (9.29) не выполняется условие по ограничению y4 (y4 = 7).

Замена y4 = 0 вместо y7 = 0 приводит к тому, что в первом же уравнении (9.29) не выполняется условие по ограничению y3 (y3= 9).

Замена y5 = 0 вместо y7 = 0 приводит к формированию нулевой (четвертой) строки матрицы A.

Замена y6 = 0 вместо y7 = 0 приводит к формированию нулевой (пятой) строки матрицы A.

Замена y10 = 0 вместо y7 = 0 приводит к тому, что в третьем уравнении (5.15) не выполняется условие по ограничению y12

(y12 = 7).

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

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

Находим Y1 = (0, 0, 4, 7, 5, 1, 5, 0, 0, 8, 0, 0). Т.к. Z(Y1) = 104 и это не меньше уже полученной оценки, исследуем следующее ребро, исключив в системе (5.14) уравнение y8 = 0 и заменяя его последовательно уравнениями из (5.16).

Замена y3 = 0 вместо y8 = 0 приводит к образованию нулевой (шестой) строки матрицы A.

Замена y4 = 0 вместо y8 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).

Замена y5 = 0 вместо y8 = 0 приводит к образованию нулевой (четвертой) строки матрицы A.

Замена y6 = 0 вместо y8 = 0 приводит к тому, что в пятом уравнении (5.15) не выполняется условие по ограничению y10 (y10= 8).

Замена y10 = 0 вместо y8 = 0 приводит к тому, что в третьем уравнении (5.15) не выполняется условие по ограничению y12 (y12 = 7).

Замена y12 = 0 вместо y8 = 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 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{8}\\y_{10} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

Ее решение Y1 = (0, 0, 9, 2, 5, 1, 0, 5, 0, 8, 0, 0) определяет значение Z(Y1) = 134 > 104.


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