Симплекс-метод

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

История

Идея последовательного перебора вершин многогранника допустимых решений восходит к работам советского математика Леонида Канторовича, который в 1939 году сформулировал задачу линейного программирования для планирования производства и предложил метод разрешающих множителей. Однако систематический алгоритм, пригодный для компьютерной реализации, был создан Джорджем Данцигом. Первое публичное изложение симплекс-метода состоялось в 1947 году, а в 1951 году Данциг опубликовал монографию «Linear Programming» (рус. «Линейное программирование»), закрепившую основы метода.

Название «симплекс-метод» не связано с геометрическим понятием симплекса. По одной из версий, Данциг использовал термин «симплекс» как техническое обозначение для некоторой вспомогательной процедуры в первоначальном варианте алгоритма. Позднее термин закрепился.

В 1950—1960-е годы алгоритм был усовершенствован, появились многочисленные модификации (двойственный симплекс-метод, модифицированный симплекс-метод). В 1979 году появился первый полиномиальный алгоритм линейного программирования — метод эллипсоидов (Л. Хачиян), однако на практике симплекс-метод оставался предпочтительным для большинства задач малой и средней размерности. В 1984 году Н. Кармаркар предложил метод внутренней точки, который для сверхбольших задач часто оказывается быстрее симплекс-метода. Несмотря на это, симплекс-метод продолжает активно применяться, в том числе в силу простоты реализации и хорошей интерпретируемости результатов.

Постановка задачи

Симплекс-метод решает задачу линейного программирования в стандартной форме:

\[ \max \; \mathbf{c}^T \mathbf{x} \] при \[ A \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}, \]

где

• \(\mathbf{x} = (x_1, x_2, \dots, x_n)^T\) — вектор переменных;
• \(\mathbf{c} \in \mathbb{R}^n\) — вектор коэффициентов целевой функции;
• \(A\) — матрица ограничений размерности \(m \times n\);
• \(\mathbf{b} \in \mathbb{R}^m\) — вектор правых частей ограничений (обычно \(b_i \geq 0\)).

Для приведения к стандартной форме используются дополнительные (слабиальные) переменные, которые переводят неравенства в равенства. В результате получается каноническая форма:

\[ \max \; \mathbf{c}^T \mathbf{x} \] при \[ A \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}, \]

где \(A\) теперь имеет размерность \(m \times (n+m)\), а \(\mathbf{x}\) расширен дополнительными переменными.

Основная идея

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

Алгоритм

1. Приведение к канонической форме

Исходная задача приводится к виду с равенствами и неотрицательными переменными. Для этого в каждое ограничение-неравенство вводится слабиальная переменная \(s_i\). Таким образом, число переменных становится \(n+m\), число уравнений — \(m\).

2. Построение начального допустимого базисного решения

Необходимо найти начальную вершину многогранника — некоторое допустимое базисное решение. Обычно это делается с помощью введения искусственных переменных и решения вспомогательной задачи (M-метод или двухфазный симплекс-метод). В простейшем случае, если все исходные ограничения имеют знак \(\leq\) и \(b_i \geq 0\), начальное базисное решение получается прямым: все исходные переменные равны нулю, а слабиальные переменные равны \(b_i\).

3. Симплекс-таблица

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

4. Проверка оптимальности

В задаче максимизации критерий оптимальности: если все элементы последней строки (исключая столбец свободных членов) неотрицательны, текущее базисное решение оптимально. Если есть отрицательные элементы — решение не оптимально.

5. Выбор разрешающего столбца

Выбирается столбец с наиболее отрицательным (по модулю наибольшим) элементом в последней строке. Этот столбец соответствует переменной, которая должна войти в базис.

6. Выбор разрешающей строки

Для каждой строки (кроме последней) вычисляется отношение свободного члена к положительному элементу в разрешающем столбце. Выбирается строка с минимальным таким отношением. Эта строка соответствует переменной, которая выходит из базиса. Если во всех строках элементы разрешающего столбца неположительны, задача неограничена (решение не существует).

7. Пересчёт таблицы

Производится преобразование таблицы методом Гаусса—Жордана: разрешающий элемент делается равным 1, остальные элементы разрешающего столбца — нулевыми. После пересчёта получается новая симплекс-таблица, соответствующая новому базисному решению с лучшим значением целевой функции.

8. Повторение

Шаги 4–7 повторяются до достижения оптимальности или обнаружения неограниченности.

Разновидности метода

Двойственный симплекс-метод

Используется для задач, где недопустимо текущее базисное решение, но выполнен критерий оптимальности. Позволяет эффективно решать задачи с большим числом ограничений и при небольших изменениях данных (после пересчёта).

Модифицированный симплекс-метод

Ориентирован на работу с большими и разреженными матрицами. Вместо полного пересчёта таблицы хранится обратная матрица к базису, что сокращает объём вычислений и повышает численную устойчивость.

Ревизованный симплекс-метод

Форма модифицированного метода, в которой операции производятся только с базисными столбцами, что особенно выгодно при большом числе переменных и ограничений.

Применение

Симплекс-метод широко используется в задачах:

• Планирование производства (оптимизация выпуска при ограниченных ресурсах);
• Транспортные задачи (минимизация стоимости перевозок);
• Финансовое планирование (портфельная оптимизация, управление рисками);
• Логистика (маршрутизация, складские задачи);
• Сельское хозяйство (оптимизация рационов кормления, распределение посевных площадей);
• Энергетика (эффективное распределение нагрузки между электростанциями).

Реализации симплекс-метода входят во все основные пакеты математического и статистического программного обеспечения: MATLAB, GNU Octave, SciPy, CPLEX, Gurobi (в последних — наряду с методами внутренней точки). В России разработкой и внедрением методов линейного программирования занимались, в частности, научные школы Л. В. Канторовича (Ленинградское отделение Математического института АН СССР) и В. С. Михалевича (Институт кибернетики АН УССР).

Критика и ограничения

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

Другая проблема — вырождение: когда несколько базисных решений соответствуют одной вершине, метод может зациклиться. Для борьбы с этим применяют антизацикливающие правила (правило Бланда, правило Лексикографического минимума). Также метод чувствителен к ошибкам округления при больших объёмах вычислений, что требует использования двойной точности или специальных методов коррекции.

Интересные факты

• Долгое время существовала гипотеза о том, что симплекс-метод является полиномиальным в среднем. Это было в некоторой мере доказано работами А. И. Добровольской, И. Б. Мучника и других российских математиков в 1980-е годы.
• За разработку теории линейного программирования Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономике 1975 года. При этом симплекс-метод был присуждён к разработке независимо.
• Первая компьютерная реализация симплекс-метода на машине SEAC была выполнена в 1952 году; задача содержала 71 переменную и 48 ограничений.

Источники

1. Данциг Дж. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
2. Канторович Л. В. Математические методы организации и планирования производства. — Л., 1939.
3. Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР. — 1979. — Т. 244, № 5. — С. 1093–1096.
4. Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988. — 208 с.
5. Зайченко Ю. П. Исследование операций. — Киев: Вища школа, 1988. — 552 с.