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