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

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

Алгоритм

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

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

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

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

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

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

Однако априорный выбор подходящего значения M не является тривиальной задачей. Способ преодоления необходимости указывать значение M описан в . ^[1]

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

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

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

x-y\leq Mz

x-y\geq -Mz

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

См. также

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

Внешние ссылки

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

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

Обсуждение

Симплекс – метод Big M , Линн Киллен, Дублинский городской университет .
Метод «Большого М» , businessmanagementcourses.org
«Метод большой М» , Марк Хатчинсон
Метод Big-M с Numerical Infinite M , недавно представленный вариант без параметров.
ТРЕХФАЗНЫЙ СИМЛЕКСНЫЙ МЕТОД ДЛЯ НЕВОЗМОЖНЫХ И НЕОГРАНИЧЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ , метод Big M для M=1

Ссылки

^ Кокоччони, Марко; Фиаски, Лоренцо (2021). «Метод Big-M с числовым бесконечным M» . Письма об оптимизации . 15 (1): 2455–2468. дои : 10.1007/s11590-020-01644-6 . hdl : 11568/1061259 .

[1] Кокоччони, Марко; Фиаски, Лоренцо (2021). «Метод Big-M с числовым бесконечным M» . Письма об оптимизации . 15 (1): 2455–2468. дои : 10.1007/s11590-020-01644-6 . hdl : 11568/1061259 .

[1]