LP: метод большой М

Метод большой М

Когда симплекс имеет искусственные переменные, можно не найти очевидного начального решения (проверить, находится ли начало координат в поле определения). В этом случае начальное решение необходимо найти с помощью метода большого М.

Этот метод вычисляет вспомогательную задачу перед решением симплекса линейная программа, поэтому его называют двухфазным симплексом.

Почему искусственная переменная?

Прежде чем объяснять, как получить решение для запуска симплекса, важно понять, почему необходимо добавлять искусственную переменную в дополнение к резервная переменная.

В качестве примера рассмотрим следующую линейную программу:

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Добавим переменные пробела:

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Симплекс начинается с приведения базовых переменных к нулю, то есть со следующего вектора (0, 0, -19, 32). Это невозможно, потому что X3 не может принимать отрицательное значение. Вот почему необходимо добавить новую переменную, которая поэтому будет искусственной.

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Здесь вектор (0, 0, 0, 19, 32) является допустимым решением. Но поскольку это искусственная переменная, должна быть возможность удалить ее из Симплекса, чтобы иметь возможность найти глобальное решение. Поэтому необходимо, чтобы X5=0. Чтобы проверить, возможно ли это, мы стремимся минимизировать X5.

Строительство Фазы 1

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

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Мы знаем, что в базе только X4 и X5, поэтому первым шагом является выражение целевой функции с небазовыми переменными (здесь X1, X2, X3). В примере это возможно благодаря первому ограничению.

Первым шагом является решение следующей линейной программы:

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Фаза 2

Второй этап метода «Две фазы» разработан точно так же, как метод «Симплекс», за исключением того, что перед началом итераций необходимо удалить столбцы, соответствующие искусственным переменным, и восстановить исходную таблицу.

  • Удалить столбцы искусственных переменных: Если мы достигли вывод что исходная задача имеет решение, мы должны подготовить нашу таблицу ко второму этапу. Этот шаг очень прост, все, что вам нужно сделать, это удалить столбцы, соответствующие искусственным переменным.
  • Реконструкция исходной таблицы: Исходный массив при этом остается примерно равным последнему массиву первой фазы. Линию целевой функции следует изменить только на линию исходной задачи и пересчитать линию Z (так же, как в первой таблице этапа 1).

Условия остановки такие же, как и в симплекс-методе. Другими словами, когда в строке индикатора ни одно из значений приведенных затрат не является отрицательным (потому что мы находимся в случае максимизации).

Предыдущий симплекс дает оптимальное решение Z=0 с вектором (0, 19/3, 0, 20/3, 0). Это означает, что можно обойтись без искусственной переменной и что найденное решение находится в пространстве определения исходной задачи (поскольку X5 не вмешивается и находится вне базиса). Окончательное решение дает следующий симплекс:

вырожденный симплекс с недопустимым происхождением метод большой M искусственная переменная

Последний шаг фазы 1 состоит в том, чтобы взять начальную целевую функцию (здесь -2X1 – X2) и заменить все базовые переменные на внебазовые переменные (здесь X2 и X4 находятся в базе, X1 и X3 вне базы).

У нас есть для первого ограничения X2 = 19/3 – 2/3X1 + 1/3X3, поэтому мы можем переписать целевую функцию следующим образом: Z = – 4/3X1 – 1/3X2 -19/3.

С этого момента все итерации до достижения оптимального решения задачи не показывают разницы с симплекс-методом.

Симплексный алгоритм

Вот пересмотренный симплексный алгоритм:

вырожденный симплекс с недопустимым происхождением метод большой М искусственная переменная двухфазный симплекс

 

Делиться
ru_RURU