Пошаговое решение задач симплекс-методом (с примерами)
Освойте симплекс-метод для линейного программирования. Узнайте, как составить начальную таблицу, выбрать ведущие переменные и найти оптимальное решение.
Попробуйте пошаговый калькулятор симплекс-метода и чувствительности
Введите целевую функцию и ограничения, чтобы увидеть симплекс-таблицы, разрешающие элементы и анализ чувствительности в реальном времени.
Введение в симплекс-метод
Симплекс-метод — это систематический итерационный алгоритм для решения задач линейного программирования (ЗЛП). Разработанный Джорджем Данцигом в 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: Метод Жордана-Гаусса (пересчет таблицы)
С помощью элементарных преобразований строк ведущая строка делится на разрешающий элемент, а коэффициенты ведущего столбца во всех остальных строках обращаются в нуль. В результате формируется симплекс-таблица следующей итерации.
Критерий оптимальности
Итерации повторяются до тех пор, пока в строке целевой функции не останется отрицательных оценок. Когда все оценки неотрицательны, найдено оптимальное решение задачи!
Готовы решить задачу линейного программирования?
Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.