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

Алгоритм

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

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

• умножить выражения для связей в виде неравенства так, чтобы убедиться, что правая часть положительна;
• если ставится задача минимизации, то её надо преобразовать в задачу максимизации за счёт умножения целевой функции на −1;
• для любых ограничений, превышающих допустимые, введите избыточные переменные ${\displaystyle s_{i}}$ и искусственные переменные ${\displaystyle \varphi _{i}}$ ф _i так, как это показано ниже ^{[ уточнить ]} ;
• выбрать большое положительное значение ${\displaystyle M}$ и введите в целевую функцию формы соответствующее слагаемые вида ${\displaystyle -M}$ , умноженного на искусственные переменные;
• для ограничений вида «меньше или равно» вводятся переменные рассогласования ${\displaystyle s_{i}}$ s _i таким образом, чтобы все ограничения обратились в равенство;
• полученная задача решается обычным симплексным методом.

Например, ограничение ${\displaystyle x+y\leqslant 100x+y\leqslant 100}$ принимает вид ${\displaystyle x+y+s_{1}=100}$ , в то время как ограничение ${\displaystyle x+y\geqslant 100}$ записывается как ${\displaystyle x+y-s_{1}+a_{1}=100}$ . Должно быть показано, что искусственные переменные равны 0. Функция, подлежащая максимизации, переписывается так, чтобы включить в неё сумму всех искусственных переменных. Затем применяются сокращения строк для получения окончательного решения.

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

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

Альтернативные применения

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

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

${\displaystyle x-y\leqslant Mz}$

${\displaystyle x-y\geqslant -Mz}$

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

См. также

• — метод предлагающий ещё один подход к решению задач с ограничениями типа нестрогих неравенств.
• Условия Каруша — Куна — Таккера — условия, которые применяются к задачам нелинейной оптимизации с ограничениями типа неравенств.

Литература

• Griva, Igor. / Igor Griva, Stephan G. Nash, Ariela Sofer. — 2nd. — Society for Industrial Mathematics, 26 March 2009. — ISBN 978-0-89871-661-0 .

Ссылки

• , Lynn Killen, Dublin City University .
• , businessmanagementcourses.org
• , Mark Hutchinson
• , a recently introduced parameterless variant
• , Big M method for M=1