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



   http://dcpcinema.ru/ DCP конвертация кодирование видео из пакета DCP.             

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


Получим систему уравнений

 \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 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

Находим y3 = 9, y6 = 9 и после подстановки — y4 = 2, y5 = 2. Вновь выполняем подстановку, находим y9 = 3, и после следующей подстановки y12 = 5.

Итак, получена вершина Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0, 5). Т.к. Z(Y1) = 119 < 141, полагаем Y0 := Y1 и начинаем пробу возможных перемещений вдоль ребер из найденной вершины многогранника решений в вершину с меньшим значением целевой функции:

 \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 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

Запишем вновь аналогично (5.8) и (5.9) систему уравнений, решением которой является вершина Y0, отметив в ней "отсутствующие" столбцы:

 \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 & 0 & \colorbox[gray]{0.8}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 & 0 & \colorbox[gray]{0.8}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 & 1 & \colorbox[gray]{0.8}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 & 1 & \colorbox[gray]{0.8}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 & 0 & \colorbox[gray]{0.8}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 & 0 & \colorbox[gray]{0.8}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.11)

Находим

y1 = 0, y2 = 0, y7 = 0, y8 = 0, y10 = 0, y11 = 0. (5.12)

Начнем движение по ребрам из данной вершины. Для этого будем исключать из (5.12) одно из уравнений, а оставшуюся систему будем решать совместно с не вошедшими в (5.12) уравнениями:

y3 = 0, y4 = 0, y5 = 0, y6 = 0, y9 = 0, y12 = 0. (5.13)

При этом надо учесть, что могут формироваться ранее исследованные комбинации нулей. (Комбинации нулей удобно метить индексным кодом, который следует запоминать для исключения повторного анализа.)

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

Замена y1 = 0 уравнением y4 = 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 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_3\\y_5\\y_6\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix}

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

Примечание. Нам вновь не пришлось воспользоваться схемой Гаусса. По-видимому, вид уравнений и вхождение каждой переменной не более чем в два уравнения позволяют довольствоваться простой подстановкой. Ниже мы исследуем это подробнее.

Переходим к другому ребру, заменяя в (5.12) уравнение y2 = 0 уравнениями из (5.13).

Замена y3 = 0 вместо y2 = 0 приводит к тому, что последняя строка матрицы A становится нулевой.

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

Находим с помощью подстановок Y1 = (0, 2, 9, 0, 4, 7, 0, 0, 1, 0, 0, 7). Т.к. Z(Y1) = 127 > 119, найденную вершину отвергаем и переходим к анализу следующего ребра.

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




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