Искусственный базис и M-метод
Почему M-метод выделен в отдельную тему
Эта глава закрывает один из самых неприятных практических вопросов — что делать, когда "обычный" старт симплекса невозможен. В реальных постановках ограничения равенствами и >= встречаются постоянно, поэтому без искусственного базиса раздел был бы неполным.
Здесь важно освоить диагностику до вычислений — понять, можно ли построить допустимый старт, и корректно интерпретировать исходы (W=0 или W>0). Заодно закрепляются формулы фазы 1 и штрафа M.
После чтения вы должны уверенно отвечать на два вопроса — "когда нужен искусственный базис" и "как по итогам первой фазы доказать совместность или несовместность модели".
Классический симплекс стартует с допустимого плана — неотрицательные RHS и базис из slack-переменных. В жизни часто встречаются:
- ограничения
=без запаса slack; - ограничения
≥с отрицательными или нулевыми RHS после преобразований; - необходимость сразу найти любой допустимый угол.
Тогда вводят искусственные переменные и либо двухфазный метод, либо M-метод (штраф M).
Ниже — два классических подхода в логичном порядке: сначала искусственный базис (двухфазный старт), затем M-метод.
| Метод | Содержание | Якорь |
|---|---|---|
| Искусственный базис, фаза 1 / фаза 2 | двухфазный симплекс | #iskusstvennyj-bazis |
M-метод (штраф M) | метод большого штрафа | #m-metod |
Когда "обычный" старт не работает (сценарии)
| Ситуация | Почему slack не спасает | Что делают |
|---|---|---|
Равенство 2x₁ + x₂ = 5 | нет "запаса" в виде +s с положительным RHS в единичном базисе без фиктивной переменной | добавляют искусственную a₁ |
≥ после surplus | RHS в строке может стать отрицательным — классический старт с slack ломается | фаза 1 или M |
| Нужен любой угол области | симплексу нужна допустимая вершина | сначала минимизируют сумму искусственных |
Аналогия — искусственная переменная — временная "прокладка", чтобы таблица имела единичный базис, как slack при ≤. Затем её выталкивают из плана с нулевым значением; если вытолкнуть нельзя — исходные ограничения несовместны.
Метод искусственного базиса (двухфазный симплекс)
Цель двухфазного метода — получить допустимый опорный план исходной ЗЛП или доказать, что ограничения несовместны, без введения символа M в целевую функцию.
Искусственная переменная
Для равенства
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-метод (метод большого штрафа)
В M-методе вместо отдельной фазы 1 штраф за искусственные переменные вшивают в одну целевую функцию коэффициентом M.
К коэффициенту каждой искусственной aᵢ в целевой функции добавляют −M (для max Z) или +M (для min Z), где M — очень большое положительное число.
Смысл — симплекс сначала "выгоняет" искусственные из базиса, потому что они катастрофически портят Z, пока M больше любых "нормальных" коэффициентов.
Три исхода М-задачи —
| Исход | Что видим в оптимальной таблице | Вывод по исходной ЗЛП |
|---|---|---|
| 1 | все искусственные вне базиса или равны 0 | допустимый план найден, читаем x |
| 2 | хотя бы одна искусственная в базисе с положительным значением | область пуста (несовместность) |
| 3 | М-задача не имеет решения | исходная задача неразрешима в постановке |
Риски M-метода —
| Проблема | Что делать |
|---|---|
M слишком мал | солвер "любит" оставить искусственную |
M слишком велик | плохая обусловленность, ошибки округления |
| на бумаге | часто используют символ M, не подставляя число |
В программных решателях предпочитают двухфазный или внутренние точки, не гигантский M.
Сравнение подходов
| Критерий | Двухфазный | M-метод |
|---|---|---|
| Наглядность при ручном счёте | отдельная цель W | одна таблица, штраф в Z |
| Устойчивость в коде | хорошая | хуже при плохом M |
Ограничения ≥ | да, с surplus + искусственные | да |
| Равенства | да | да |
Оба метода решают одну задачу — получить начальный допустимый базис для исходной ЗЛП или доказать несовместность.
Алгоритм M-метода
- Привести к канонической форме, ввести slack/surplus/искусственные.
- Записать
Zс коэффициентами−Mу искусственных (для max). - Выразить строку
Zтолько через небазисные (жордан по базису) — иначе знаки запутаются. - Симплекс до оптимума.
- Проверить искусственные — все нули и не в базисе → читать решение по
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-метод в большую таблицу — структура задачи богаче.
Практический совет
При ручном решении —
- Сначала попробуйте slack — может, фаза 1 не нужна.
- Если нужны искусственные — двухфазный метод при ручном счёте часто меньше путает знаки, чем числовой
M = 10⁶. - Всегда подставьте найденные
xв исходные неравенства.
Как понять, что фаза 1 выполнена корректно
Перед переходом ко второй фазе проверьте четыре пункта —
- Значение вспомогательной цели
W* = 0. - В базисе нет искусственных переменных с положительным RHS.
- Все строки ограничений соответствуют исходной модели (без фиктивных допущений).
- Строка исходной цели
Zпересобрана относительно текущего базиса.
Если пропустить пункт 4, вторая фаза часто даёт формально корректные таблицы, но неверное значение Z.
Где в практике встречается "фаза 1"
- Балансовые задачи с большим числом равенств (
=). - Модели с обязательными нижними границами (
≥) по сервисным уровням. - Перезапуск оптимизации после резкой смены ограничений, когда старый базис перестал быть допустимым.
Именно поэтому понимание искусственного базиса полезно даже при использовании готовых солверов — вы лучше диагностируете сообщения вида infeasible и быстрее находите конфликтующие ограничения.
Дальше — теория двойственности.