Двухфазный симплекс-метод в линейном программировании (Пошаговое руководство)
Пошаговое решение задач с искусственными переменными с помощью двухфазного симплекс-метода — надежной вычислительной альтернативы методу больших М.
Попробуйте пошаговый калькулятор симплекс-метода и чувствительности
Введите целевую функцию и ограничения, чтобы увидеть симплекс-таблицы, разрешающие элементы и анализ чувствительности в реальном времени.
Преимущества двухфазного метода
Для задач с ограничениями $\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) |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s₁ | 1 | 1 | 1 | 0 | 0 | 4 |
| a₁ | 1 | 2 | 0 | −1 | 1 | 6 |
Шаг 2 — Итерация Фазы I
- Входящая переменная: Столбец x₂ с коэффициентом 2.
- Симплекс-отношения: Строка s₁: 4/1 = 4; Строка a₁: 6/2 = 3 (минимум). Переменная a₁ покидает базис.
- Разрешающий элемент: Элемент (a₁, x₂) равен 2. Выполняются преобразования Жордана-Гаусса.
Таблица после итерации:
| Базис | x₁ | x₂ | s₁ | s₂ | a₁ | ПЧ (RHS) |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s₁ | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x₂ | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. Все искусственные переменные выведены из базиса. Начальный опорный план найден: x₁ = 0, x₂ = 3, s₁ = 1, s₂ = 0.
Фаза II: Оптимизация исходной функции
Столбцы искусственных переменных полностью удаляются. В таблицу возвращается исходная целевая функция $Z = 2x_1 + 3x_2$, выраженная через небазисные переменные.
Финальная таблица Фазы II
| Базис | x₁ | x₂ | s₁ | s₂ | ПЧ (RHS) |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s₂ | 1 | 0 | 2 | 1 | 2 |
| x₂ | 1 | 1 | 1 | 0 | 4 |
Все оценки Z-строки неотрицательны — оптимальное решение найдено:
- x₁ = 0, x₂ = 4, Z = 12
- s₂ = 2 (второе ограничение имеет запас в 2 единицы).
Сравнение: Двухфазный метод и метод Big-M
| Характеристика | Двухфазный метод | Метод Big-M |
|---|---|---|
| Численная точность | Высокая (без искусственных констант M) | Ниже (риск ошибок округления M) |
| Реализация в ПО | Стандарт в профессиональных решателях | Чаще используется при ручном счете |
| Проверка совместности | W > 0 в конце Фазы I | a_i > 0 в финальной таблице |
Готовы решить задачу линейного программирования?
Мгновенные пошаговые симплекс-таблицы с полным анализом чувствительности и теневыми ценами для любой задачи ЛП.