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

Пошаговое решение задач симплекс-методом (с примерами)

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

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

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

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

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

Введение в симплекс-метод

Симплекс-метод — это систематический итерационный алгоритм для решения задач линейного программирования (ЗЛП). Разработанный Джорджем Данцигом в 1947 году, он остается фундаментальным инструментом исследования операций и численной оптимизации.

Шаг 1: Приведение к канонической (стандартной) форме

Перед применением симплекс-метода математическую модель ЗЛП необходимо привести к стандартной форме:

  • Целевая функция формулируется как задача максимизации (при минимизации: $\min Z = -\max (-Z)$).
  • Все ограничения-неравенства преобразуются в строгие равенства:
    • Для ограничений $\le$ прибавляется дополнительная переменная слабины ($+s_i$), отражающая неиспользованный объем ресурса.
    • Для ограничений $\ge$ вычитается избыточная переменная ($-s_i$) и вводится искусственная переменная.
  • Все переменные удовлетворяют условию неотрицательности: $x_j \ge 0, s_i \ge 0$.

Шаг 2: Построение начальной симплекс-таблицы

Коэффициенты системы уравнений и целевой функции заносятся в симплекс-таблицу. Переменные, входящие в начальный единичный базис, определяют вектор начального базисного решения (опорного плана). Строка целевой функции (Z-строка) содержит относительные оценки (симплекс-разности).

Шаг 3: Выбор разрешающего (ведущего) элемента

Итерационный шаг алгоритма состоит из следующих этапов:

  • Ведущий столбец (вход в базис): Выбирается переменная с наибольшим по модулю отрицательным коэффициентом в строке целевой функции при максимизации.
  • Ведущая строка (выход из базиса): Проводится тест минимального симплекс-отношения (деление свободных членов правой части RHS на положительные коэффициенты ведущего столбца: $\theta = \min \{ \text{RHS}_i / a_{ik} \mid a_{ik} > 0 \}$). Минимальное отношение определяет строку, покидающую базис.
  • Пересечение ведущего столбца и ведущей строки определяет разрешающий (опорный) элемент.

Шаг 4: Метод Жордана-Гаусса (пересчет таблицы)

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

Критерий оптимальности

Итерации повторяются до тех пор, пока в строке целевой функции не останется отрицательных оценок. Когда все оценки неотрицательны, найдено оптимальное решение задачи!

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

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

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

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

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