Принцип работы симплекс-метода

Симплекс-метод позволяет решать задачи линейного программирования любой размерности, т.е. с любым количеством переменных. Решение задач линейного программирования на основе симплекс-метода состоит в целенаправленном переборе угловых точек области допустимых решений (далее ОДР) в направлении улучшения значения целевой функции.

Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается при значениях переменных X₁,

X₂,...,X_n, соответствующих одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР.

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

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

Для новой угловой точки ОДР процесс повторяется, т.е. проверяются смежные угловые точки. Перебор угловых точек происходит до тех пор, пока не будет найдено оптимальное решение, т.е. пока не будет достигнута угловая точка ОДР, для которой ни в одной из смежных точек значение целевой функции не улучшается.

Поиск решения на основе симплекс-метода реализуется с помощью симплекс-таблиц. Основные этапы реализации симплекс-метода следующие.

1. Задача линейного программирования приводится к стандартной форме.

2. Определяется начальное допустимое решение (начальная угловая точка ОДР).

3. Строится исходная симплекс-таблица. Выполняются преобразования симплекс-таблиц, соответствующие перебору угловых точек ОДР, до получения оптимального решения.

Реализация симплекс-метода существенно различается в зависимости от вида математической модели задачи. В данном разделе рассматривается реализация симплекс-метода для случая, когда математическая модель задачи состоит только из ограничений "меньше или равно", и целевая функция подлежит максимизации (как в примере 2.1). Реализация симплекс-метода для задач с математической моделью любого вида рассматривается в разделе 3.