Метод больших М (Big-M) в линейном программировании (Пошаговый пример)
Освойте метод больших М для ограничений >= и = в линейном программировании. Различия между переменными слабины, избытка и искусственными переменными с пошаговой симплекс-таблицей.
Попробуйте пошаговый калькулятор симплекс-метода и чувствительности
Введите целевую функцию и ограничения, чтобы увидеть симплекс-таблицы, разрешающие элементы и анализ чувствительности в реальном времени.
Зачем нужен метод больших М (Big-M)?
Канонический симплекс-метод требует начального базисного плана (единичной матрицы). Если все ограничения задачи имеют вид ≤ с неотрицательными правыми частями, базис образуют дополнительные переменные слабины при $x=0$. Однако при наличии ограничений вида ≥ или строгих равенств = точка начала координат недопустима. Метод больших М (метод штрафных функций) позволяет построить искусственный начальный базис и запустить наш Калькулятор симплекс-метода.
Переменные слабины, избытка и искусственные переменные
- Переменные слабины ($s_i ≥ 0$): Прибавляются к ограничениям ≤ ($+s_i$). Отражают неиспользованный остаток ресурса.
- Избыточные переменные ($e_i ≥ 0$): Вычитаются из ограничений ≥ ($-e_i$). Показывают превышение минимального норматива. В точке $x=0$ дают $-e_i = b_i ⇒ e_i = -b_i < 0$, что нарушает условие неотрицательности.
- Искусственные переменные ($a_i ≥ 0$): Прибавляются ($+a_i$) к ограничениям ≥ и =. Они не имеют физического смысла и служат сугубо математическим инструментом для старта симплекс-метода.
Штрафная целевая функция метода Big-M
Чтобы исключить искусственные переменные из оптимального плана, им назначается колоссальный штраф $M$ ($M \gg 0$):
- При максимизации: Из целевой функции вычитается $M \times a_i$: $\max Z = \sum c_j x_j - M \sum a_i$.
- При минимизации: К целевой функции прибавляется $M \times a_i$: $\min Z = \sum c_j x_j + M \sum a_i$.
Пошаговый численный пример с валидацией
Решим задачу, которую вы можете также проверить на нашем Калькуляторе симплекс-метода:
Максимизировать Z = 3x₁ + 5x₂
При ограничениях:
x₁ + x₂ ≥ 2 (Ограничение 1: минимальный план)
2x₁ + 3x₂ ≤ 12 (Ограничение 2: лимит ресурса)
x₁, x₂ ≥ 0
Шаг 1: Каноническая форма
- Ограничение 1 (≥): $x_1 + x_2 - e_1 + a_1 = 2$
- Ограничение 2 (≤): $2x_1 + 3x_2 + s_2 = 12$
- Начальный базис: ${a_1, s_2}$. Все переменные неотрицательны.
Шаг 2: Предварительное преобразование строки Z
Уравнение целевой функции: $Z - 3x_1 - 5x_2 + M a_1 = 0$. Исключаем базисную переменную $a_1$, вычитая $M \times (\text{Строка } 1)$:
Новая строка Z = [Z - 3x₁ - 5x₂ + M a₁] - M × [x₁ + x₂ - e₁ + a₁ = 2]
⇒ Z - (3 + M)x₁ - (5 + M)x₂ + M e₁ + 0s₂ + 0a₁ = -2M
Шаг 3: Начальная симплекс-таблица (Итерация 0)
| Базис | x₁ | x₂ | e₁ | s₂ | a₁ | ПЧ (RHS) | Симплекс-отношение |
|---|---|---|---|---|---|---|---|
| Z | -(3 + M) | -(5 + M) | M | 0 | 0 | -2M | — |
| a₁ | 1 | 1 | -1 | 0 | 1 | 2 | 2 / 1 = 2 (мин) ← Направляющая строка |
| s₂ | 2 | 3 | 0 | 1 | 0 | 12 | 12 / 3 = 4 |
Шаг 4: Итерация 1
В базис входит $x_2$ (наибольшая отрицательная оценка $-(5+M)$), из базиса выходит $a_1$ (минимальное отношение 2). Разрешающий элемент равен 1. После преобразований Жордана-Гаусса искусственная переменная $a_1$ покидает базис, а константа $M$ сокращается из правой части:
| Базис | x₁ | x₂ | e₁ | s₂ | a₁ | ПЧ (RHS) | Симплекс-отношение |
|---|---|---|---|---|---|---|---|
| Z | 2 | 0 | -5 | 0 | 5 + M | 10 | — |
| x₂ | 1 | 1 | -1 | 0 | 1 | 2 | -1 ≤ 0 (пропуск) |
| s₂ | -1 | 0 | 3 | 1 | -3 | 6 | 6 / 3 = 2 ← Направляющая строка |
Шаг 5: Итерация 2 (Оптимальная таблица)
В базис входит $e_1$ (оценка $-5$), выходит $s_2$ (отношение $6/3 = 2$). Разрешающий элемент 3 в строке $s_2$:
| Базис | x₁ | x₂ | e₁ | s₂ | a₁ | ПЧ (RHS) |
|---|---|---|---|---|---|---|
| Z | 1/3 | 0 | 0 | 5/3 | M | 20 |
| x₂ | 2/3 | 1 | 0 | 1/3 | 0 | 4 |
| e₁ | -1/3 | 0 | 1 | 1/3 | -1 | 2 |
Интерпретация оптимального решения
Все оценки в строке Z неотрицательны ($1/3 ≥ 0, 5/3 ≥ 0, M ≥ 0$). Достигнут оптимальный план:
- Переменные решения: $x_1^* = 0$, $x_2^* = 4$.
- Остатки и избытки: $e_1 = 2$ (первое ограничение перевыполнено на 2 единицы), $s_2 = 0$ (второй ресурс израсходован полностью).
- Максимальное значение: $Z^* = 3(0) + 5(4) = 20$.
- Допустимость: Искусственная переменная $a_1 = 0$ и не входит в базис.
Геометрическую интерпретацию смотрите на нашем Калькуляторе графического метода.
Сравнение: Big-M или двухфазный метод?
В вычислительных программах метод Big-M может приводить к ошибкам округления из-за огромного $M$. Поэтому в профессиональных решателях стандартом является Двухфазный симплекс-метод.
Типичные ошибки студентов
- Пропуск предварительного исключения $M$ из строки Z перед первым шагом.
- Неправильный знак штрафа (должен быть $-M$ при максимизации и $+M$ при минимизации).
- Вычисление симплекс-отношений с неположительными элементами.
- Ознакомьтесь также с нашим руководством по теневым ценам в анализе чувствительности.
Готовы решить задачу линейного программирования?
Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.