Метод Big M - Big M method

В исследование операций, то Метод Big M это метод решения линейное программирование проблемы с использованием симплексный алгоритм. Метод Big M расширяет симплекс-алгоритм на задачи, содержащие ограничения «больше». Это достигается путем связывания ограничений с большими отрицательными константами, которые не были бы частью какого-либо оптимального решения, если оно существует.

Алгоритм

Симплексный алгоритм является оригинальным и до сих пор одним из наиболее широко используемых методов решения задач линейной максимизации. Однако для его применения начало координат (все переменные равны 0) должно быть допустимой точкой. Это условие выполняется только тогда, когда все ограничения (кроме неотрицательности) меньше ограничений и с положительной константой в правой части. Метод Big M вводит избыточные и искусственные переменные для преобразования всех неравенств в эту форму. «Большое М» относится к большому количеству искусственных переменных, представленных буквой М.

Шаги в алгоритме следующие:

Умножьте ограничения неравенства, чтобы убедиться, что правая часть положительна.
Если проблема заключается в минимизации, преобразуйте в максимизацию, умножив цель на -1.
Для любых ограничений больше, чем, введите избыточные и искусственные переменные (как показано ниже)
Выберите большое положительное значение M и введите член цели в форме −M, умножающий искусственные переменные.
Для ограничений, меньших или равных, введите резервные переменные, чтобы все ограничения были равенствами
Решите проблему обычным симплексным методом.

Например, Икс + у ≤ 100 становится Икс + у + s₁ = 100, а Икс + у ≥ 100 становится Икс + у - с₁ + а₁ = 100. Должно быть показано, что искусственные переменные равны 0. Максимизируемая функция переписывается, чтобы включить в нее сумму всех искусственных переменных. потом сокращение строк применяются для получения окончательного решения.

Значение M должно быть выбрано достаточно большим, чтобы искусственная переменная не была частью какого-либо возможного решения.

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

Другое использование

При использовании в целевой функции метод Big M иногда относится к формулировкам задач линейной оптимизации, в которых нарушения ограничения или набора ограничений связаны с большой положительной константой штрафа M.

При использовании в самих ограничениях одно из множества применений Big M, например, относится к обеспечению равенства переменных только тогда, когда определенная двоичная переменная принимает одно значение, но оставлять переменные «открытыми», если двоичная переменная принимает на себя одно значение. его противоположное значение. Один из примеров этого: для достаточно большой двоичной переменной M и z (0 или 1) ограничения

{ Displaystyle х-у leq Mz}

{ Displaystyle х-у geq -Mz}

убедиться, что когда ${ displaystyle z = 0}$ тогда ${ displaystyle x = y}$ . В противном случае, когда ${ displaystyle z = 1}$ , тогда ${ displaystyle -M leq x-y leq M}$ , указывая, что переменные x и y могут иметь любые значения, пока абсолютное значение их разности ограничено ${ displaystyle M}$ (отсюда необходимость в том, чтобы M было «достаточно большим».)

Смотрите также

Двухфазный метод (линейное программирование) другой подход для решения проблем с> = ограничениями
Условия Каруша – Куна – Таккера., которые относятся к Нелинейная оптимизация проблемы с ограничениями-неравенствами.

Ссылки и внешние ссылки

Библиография

Грива, Игорь; Нэш, Стефан Г .; Софер, Ариэла. Линейная и нелинейная оптимизация (2-е изд.). Общество промышленной математики. ISBN 978-0-89871-661-0.

Обсуждение

Симплекс - метод Big M, Линн Киллен, Дублинский городской университет.
Метод Big M, businessagementcourses.org
Метод Big M, Марк Хатчинсон