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


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

Вновь выполняем подстановку, находим y9


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


Находим 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 и начинаем пробу возможных перемещений вдоль ребер из найденной вершины многогранника решений в вершину с меньшим значением целевой функции:


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



(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 приводит к системе


Решаем с помощью подстановок, находим 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 приводит к системе уравнений


Находим с помощью подстановок 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).


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