Искусственный базис и M-метод

ОБЯЗАТЕЛЬНО

Архитектору Инженеру

Классический симплекс стартует с допустимого плана: неотрицательные RHS и базис из slack-переменных. В жизни часто встречаются:

• ограничения = без запаса slack;
• ограничения ≥ с отрицательными или нулевыми RHS после преобразований;
• необходимость сразу найти любой допустимый угол.

Тогда вводят искусственные переменные и либо двухфазный метод, либо M-метод (штраф M).

Когда «обычный» старт не работает (сценарии)

Ситуация	Почему slack не спасает	Что делают
Равенство 2x₁ + x₂ = 5	нет «запаса» в виде +s с положительным RHS в единичном базисе без фиктивной переменной	добавляют искусственную a₁
≥ после surplus	RHS в строке может стать отрицательным — классический старт с slack ломается	фаза 1 или M
Нужен любой угол области	симплексу нужна допустимая вершина, а не только формула цели	сначала минимизируют сумму искусственных

Аналогия: искусственная переменная — временная «прокладка», чтобы таблица имела единичный базис, как slack при ≤. Затем её выталкивают из плана с нулевым значением; если вытолкнуть нельзя — исходные ограничения несовместны.

Искусственная переменная

Для равенства

a₁x₁ + … + aₙxₙ = b,   b > 0

добавляют aᵢ ≥ 0:

a₁x₁ + … + aₙxₙ + aᵢ = b

На первом этапе aᵢ входит в базис (как slack), но не должна остаться в оптимуме исходной задачи с положительным значением — иначе равенство выполнено «фиктивно».

Двухфазный симплекс-метод

Фаза 1. Вспомогательная цель:

min W = Σ aᵢ   (сумма всех искусственных)

или max (−W). Решают симплексом.

Чтение цели фазы 1: если в оптимуме W = 0, все искусственные обнулились — «прокладки» не нужны, равенства выполняются настоящими x. Если W > 0, хотя бы одна искусственная осталась положительной — пересечение ограничений пусто (как два параллельных неравенства x₁+x₂≤1 и x₁+x₂≥5).

Итоги:

Результат фазы 1	Вывод
W = 0, все искусственные вышли из базиса	есть допустимый план исходной задачи → фаза 2
W > 0	исходная область пуста

Фаза 2. Исходная целевая Z, начальный базис — из конца фазы 1 (без искусственных в базисе). Продолжают обычный симплекс.

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

Числовой пример двухфазного метода

max Z = 4x₁ + 3x₂

 x₁ + 2x₂ ≤ 4      (1)  →  + s₁
2x₁ +  x₂  = 5      (2)  →  + a₁   (искусственная)
x₁, x₂, s₁, a₁ ≥ 0

Фаза 1: min W = a₁ (или max −W). Стартовый базис {s₁, a₁}: x₁=x₂=0, s₁=4, a₁=5, W=5.

Таблица фазы 1 (схема; считайте по правилам симплекса):

Базис	x₁	x₂	s₁	a₁	RHS
s₁	1	2	1	0	4
a₁	2	1	0	1	5
−W	0	0	0	1	5

В строке −W коэффициент при a₁ положителен → вводим x₁ или x₂ (по правилу Dantzig — смотрите знаки в вашей записи W). После итераций добиваются W = 0, a₁ вне базиса (или a₁=0 в плане).

Фаза 2: строку цели заменяют на −Z + 4x₁ + 3x₂ = 0, базис — из конца фазы 1 без a₁, снова симплекс до оптимума по Z.

Итог фазы 1	Действие
W* > 0	ограничения несовместны, исходной ЗЛП нет плана
W* = 0, a₁ не в базисе	переход к фазе 2
W* = 0, a₁ в базисе с нулевым RHS	вырождение; возможна ε-перестановка базиса

Совет

На экзамене фазу 1 часто делают в отдельной таблице с заголовком «min W». Не смешивайте коэффициенты Z и W в одной строке — типичная ошибка.

Мини-пример идеи (равенство без других ограничений)

x₁ + x₂ = 5,   x₁, x₂ ≥ 0

Добавляем a₁: x₁ + x₂ + a₁ = 5. Фаза 1: min a₁. Оптимум a₁=0 при x₁+x₂=5 — допустимо. Фаза 2: исходная Z.

M-метод (метод большого штрафа)

К коэффициенту каждой искусственной aᵢ в целевой функции добавляют −M (для max Z) или +M (для min Z), где M — очень большое положительное число.

Смысл: симплекс сначала «выгоняет» искусственные из базиса, потому что они катастрофически портят Z, пока M больше любых «нормальных» коэффициентов.

Условие успеха:

• в оптимальной таблице все искусственные вне базиса или равны 0;
• если искусственная в базисе с ненулевым RHS → задача несовместна.

Риски M-метода:

Проблема	Что делать
M слишком мал	солвер «любит» оставить искусственную
M слишком велик	плохая обусловленность, ошибки округления
на бумаге	часто используют символ M, не подставляя число

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

Сравнение подходов

Критерий	Двухфазный	M-метод
Понятность на экзамене	отдельная цель W	одна таблица, штраф в Z
Устойчивость в коде	хорошая	хуже при плохом M
Ограничения ≥	да, с surplus + искусственные	да
Равенства	да	да

Оба метода решают одну задачу: получить начальный допустимый базис для исходной ЗЛП или доказать несовместность.

Алгоритм M-метода (кратко)

1. Привести к канонической форме, ввести slack/surplus/искусственные.
2. Записать Z с коэффициентами −M у искусственных (для max).
3. Выразить строку Z только через небазисные (жордан по базису) — иначе знаки запутаются.
4. Симплекс до оптимума.
5. Проверить искусственные: все нули и не в базисе → читать решение по x; иначе → нет плана.

Пример записи цели с M (max)

Для ограничения 2x₁ + x₂ = 5 с искусственной a₁:

max Z = 4x₁ + 3x₂ − M·a₁

В таблице с базисом {s₁, a₁} подставьте a₁ = 5 − 2x₁ − x₂ в Z — в строке −Z появятся коэффициенты с M у x₁, x₂. Пока a₁ в базисе, симплекс сначала стремится вытеснить её (коэффициент при a₁ в строке Z после приведения). Когда a₁ вышла из базиса и в плане 0, отбрасывают столбец a₁ и продолжают с обычной целью (или оставляют M только вне базиса — по методичке).

Несовместность: если в «оптимуме» a₁ всё ещё в базисе с a₁ = 5 > 0 при x=0, задача не имеет допустимых точек, удовлетворяющих равенству без фиктивной переменной.

Связь с транспортной задачей

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

Практический совет

При ручном решении:

1. Сначала попробуйте slack — может, фаза 1 не нужна.
2. Если нужны искусственные — на экзамене двухфазный часто меньше путает знаки, чем числовой M = 10⁶.
3. Всегда подставьте найденные x в исходные неравенства.

Дальше: теория двойственности.

---