Вновь выполняем подстановку, находим 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).
