← Назад в блог••10 мин чтения

Метод больших М (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)M00-2M—
a₁11-10122 / 1 = 2 (мин) ← Направляющая строка
s₂230101212 / 3 = 4

Шаг 4: Итерация 1

В базис входит $x_2$ (наибольшая отрицательная оценка $-(5+M)$), из базиса выходит $a_1$ (минимальное отношение 2). Разрешающий элемент равен 1. После преобразований Жордана-Гаусса искусственная переменная $a_1$ покидает базис, а константа $M$ сокращается из правой части:

Базисx₁x₂e₁s₂a₁ПЧ (RHS)Симплекс-отношение
Z20-505 + M10—
x₂11-1012-1 ≤ 0 (пропуск)
s₂-1031-366 / 3 = 2 ← Направляющая строка

Шаг 5: Итерация 2 (Оптимальная таблица)

В базис входит $e_1$ (оценка $-5$), выходит $s_2$ (отношение $6/3 = 2$). Разрешающий элемент 3 в строке $s_2$:

Базисx₁x₂e₁s₂a₁ПЧ (RHS)
Z1/3005/3M20
x₂2/3101/304
e₁-1/3011/3-12

Интерпретация оптимального решения

Все оценки в строке 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$. Поэтому в профессиональных решателях стандартом является Двухфазный симплекс-метод.

Типичные ошибки студентов

  1. Пропуск предварительного исключения $M$ из строки Z перед первым шагом.
  2. Неправильный знак штрафа (должен быть $-M$ при максимизации и $+M$ при минимизации).
  3. Вычисление симплекс-отношений с неположительными элементами.
  4. Ознакомьтесь также с нашим руководством по теневым ценам в анализе чувствительности.

Готовы решить задачу линейного программирования?

Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.

Запустить калькулятор
Operations Research

Пакет исследования операций

Исследуйте полную коллекцию интерактивных калькуляторов для линейного и дискретного программирования.