Понятие об М-методе (методе искусственного базиса)

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

В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную у ₁, y ₂,..., у_k которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию Т = F - M (у ₁ + у ₂ + … + у_k), где M — произвольно большое число, и ищем ее mах (Т -задача). Назовем М -функцией выражение: M (у ₁ + у ₂+ … + у_k). Справедлива теорема (доказательство здесь не приводится):

Если в оптимальном решении Т -задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. Т _mах = F _mах, если у ₁ = у ₂ = … = y_k = 0, т.е. min M -функции равен 0).

Если имеется оптимальное решение T -задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

Если Т _mах = , то исходная задача также неразрешима, причем либо F _mах = , либо условия задачи противоречивы.

Из теоремы следует, что вначале следует найти минимум M - функции. Если он равен 0 и все искусственные переменные обращаются в 0, то далее можно отбросить эти переменные и решать исходную задачу, исходя из полученного допустимого базисного решения. На практике находят не минимум М -функции, а максимум (- M)-функции.

Пример 5.11. Решить задачу, приведенную в примере 5.3, M -методом, используя симплексные таблицы.

Решение. Введем необходимое число искусственных переменных и столько же дополнительных строк в симплексной таблице.

Имеем при ограничениях:

X ₁=(0;0;-1;3;5) - недопустимое базисное решение с одной отрицательной компонентой, поэтому в первое уравнение введем искусственную переменную y ₁ с тем же знаком, что свободный член.

или

Составляем первую симплексную таблицу (табл. 5.5).

Таблица 5.5

Базис	Свободный член	Переменные	Оценочное отношение
		-1		-1				1
		-1
		-1	-2					max
Мф	М	М	- М	М			М	max

Последняя строка - это (- М)-функция, т.е. (- М) у ₁. Заполняем ее, умножая строку у ₁ на коэффициент (- М). Проверяя выполнение критерия оптимальности при отыскании максимума (- М)-функции, определяем, что в последней строке имеется отрицательный элемент во втором столбце; значит он является разрешающим, переменная x ₂ переходит в основные. Минимальное оценочное отношение в первой строке, она paзрешающая. Переменная у ₁ переходит в неосновные, обращается в 0 на следующем базисном решении и далее исключается из рассмотрения. В соответствии с общим алгоритмом получаем табл. 5.6.

Таблица 5.6

Базис	Свободный член	Переменные	Оценочное отношение
		-1		-1
		-3		-2			max
Мф							max

Последняя строка показывает, что критерий оптимальности выполнен; mах (- М_ф) = 0, значит min М_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение (0;1;0;2;3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом. Читателям рекомендуется завершить ее самостоятельно, а также выполнить решения примеров 5.2, 5.4—5.6 с помощью симплексных таблиц.

Замечание. При решении задачи на отыскание минимума линейной функции цели рекомендуется вместо находить .