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



     Автосервис митсубиси свао на http://www.autoservice-sever.ru. |          

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


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

Замена y5 = 0 вместо y7 = 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 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_6\\y_7\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

Находим Y1 = (0, 0, 7, 4, 0, 9, 2, 0, 5, 0, 0, 3). Однако Z(Y1) = 129 > 119.

Переходим к анализу следующего ребра, поочередно заменяя уравнениями из (5.13) уравнение y8 = 0 из (5.11).

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

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

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

Находим Y1 = (0, 0, 9, 2, 0, 9, 0, 2, 5, 0, 0, 3). Т.к. Z(Y1) = 141 > 119, найденную вершину отвергаем.

Переходим к анализу следующего ребра, поочередно заменяя уравнениями из (5.13) уравнение y10 = 0 из (5.11).

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

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

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

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

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

\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 & 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}

Находим Y1 = (0, 0, 9, 2, 5, 6, 0, 0, 0, 3, 0, 5). Т.к. Z(Y1) = 104 < 119, "перемещаемся" в найденную вершину с меньшим значением целевой функции.

Новая вершина характеризуется системой уравнений

y1 = 0, y2 = 0, y7 = 0, y8 = 0, y9 = 0, y11 = 0. (5.14)

Перепишем систему (5.11), выделив "отсутствующие" столбцы, вследствие (5.14):

 \begin{equation} \setcounter{MaxMatrixCols}{20} \begin{pmatrix} \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}1 & 1 & 1 & 0 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}0 & 0 \\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0 & 0 & 1 & 1 & \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}0 & 0 \\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0 & 0 & 0 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}1 & 1 & \colorbox[gray]{0.8}1 & 1 \\ \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}0 & 0 & 0 & 1 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}1 & 0 & \colorbox[gray]{0.8}0 & 0 \\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}1 & 0 & 0 & 0 & 1 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 1 & \colorbox[gray]{0.8}0 & 0 \\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 1 & 0 & 0 & 0 & \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}1 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_2\\y_3\\y_4\\y_5\\y_6\\y_7\\y_8\\y_9\\y_{10}\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

(5.15)

После исключения одного из уравнений (5.14) оставшаяся система (5.15), (5.14) будет решаться совместно с одним из уравнений

y3 = 0, y4 = 0, y5 = 0, y6 = 0, y10 = 0, y12 = 0 (5.16)

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




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