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

Двухфазный симплекс-метод в линейном программировании (Пошаговое руководство)

Пошаговое решение задач с искусственными переменными с помощью двухфазного симплекс-метода — надежной вычислительной альтернативы методу больших М.

Интерактивный калькулятор

Попробуйте пошаговый калькулятор симплекс-метода и чувствительности

Введите целевую функцию и ограничения, чтобы увидеть симплекс-таблицы, разрешающие элементы и анализ чувствительности в реальном времени.

Открыть симплекс-калькулятор →

Преимущества двухфазного метода

Для задач с ограничениями $\ge$ и $=$ требуются искусственные переменные для формирования начального базиса. В отличие от метода Big-M, где использование произвольно большой константы $M$ может приводить к вычислительным погрешностям с плавающей точкой в программных решателях, двухфазный симплекс-метод разделяет поиск допустимого базиса и оптимизацию на два независимых этапа с точной арифметикой.

Постановка задачи: Стандартная форма

Рассмотрим задачу линейного программирования:

  Максимизировать   Z = 2x₁ + 3x₂
  При ограничениях:
    x₁ +  x₂ ≤ 4     (ограничение 1)
    x₁ + 2x₂ ≥ 6     (ограничение 2)
    x₁, x₂ ≥ 0
      

Приведем ограничения к каноническому виду:

  • Ограничение 1 (≤): прибавляем переменную слабины s₁ → x₁ + x₂ + s₁ = 4
  • Ограничение 2 (≥): вычитаем избыточную переменную s₂ и прибавляем искусственную переменную a₁ → x₁ + 2x₂ − s₂ + a₁ = 6

Фаза I: Поиск начального опорного плана

На Фазе I исходная целевая функция временно откладывается. Формируется вспомогательная целевая функция:

  Минимизировать   W = a₁
      

Если значение $W$ удастся свести к нулю, все искусственные переменные будут выведены из базиса, что предоставит допустимый опорный план для исходной задачи.

Шаг 1 — Построение таблицы Фазы I

Поскольку $a_1$ является базисной переменной со значением 6, выполняется элементарное вычитание строки ограничения 2 из строки функции $W$ для получения допустимой таблицы.

Базисx₁x₂s₁s₂a₁ПЧ (RHS)
W120−106
s₁111004
a₁120−116

Шаг 2 — Итерация Фазы I

  • Входящая переменная: Столбец x₂ с коэффициентом 2.
  • Симплекс-отношения: Строка s₁: 4/1 = 4; Строка a₁: 6/2 = 3 (минимум). Переменная a₁ покидает базис.
  • Разрешающий элемент: Элемент (a₁, x₂) равен 2. Выполняются преобразования Жордана-Гаусса.

Таблица после итерации:

Базисx₁x₂s₁s₂a₁ПЧ (RHS)
W0000−10
s₁1/2011/2−1/21
x₂1/210−1/21/23

W = 0. Все искусственные переменные выведены из базиса. Начальный опорный план найден: x₁ = 0, x₂ = 3, s₁ = 1, s₂ = 0.

Фаза II: Оптимизация исходной функции

Столбцы искусственных переменных полностью удаляются. В таблицу возвращается исходная целевая функция $Z = 2x_1 + 3x_2$, выраженная через небазисные переменные.

Финальная таблица Фазы II

Базисx₁x₂s₁s₂ПЧ (RHS)
Z2030−12
s₂10212
x₂11104

Все оценки Z-строки неотрицательны — оптимальное решение найдено:

  • x₁ = 0, x₂ = 4, Z = 12
  • s₂ = 2 (второе ограничение имеет запас в 2 единицы).

Сравнение: Двухфазный метод и метод Big-M

ХарактеристикаДвухфазный методМетод Big-M
Численная точностьВысокая (без искусственных констант M)Ниже (риск ошибок округления M)
Реализация в ПОСтандарт в профессиональных решателяхЧаще используется при ручном счете
Проверка совместностиW > 0 в конце Фазы Ia_i > 0 в финальной таблице

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

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

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

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

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