Алгебраический симплексный метод

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

Симплексный метод (симплекс-метод) является универсальным методом решения задач линейного программирования. Свое название данный метод берет от слова «симплекс», означающего простейшие многоугольники (многогранники).

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

Допустимое множество базисных решений системы линейных уравнений образует в объеме многогранное тело, например тетраэдр, вершины которого - угловые точки.

Каждой угловой точке многогранники решений соответствует опорный план (допустимое базисное решение).

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

Однако количество угловых точек области допустимых планов растет очень резко с ростом числа переменных и особенно числа ограничений. Так, для небольшой задачи линейного программирования с 20 переменными и 10 ограничениями число угловых точек составляет около 30 млн., а для задачи с 100 переменными и 20 ограничениями это число может достигать 47 трлн. (47×10¹²). Чтобы сосчитать значения целевой функции во всех этих точках, компьютеру, выполняющему миллион арифметических операций в секунду, потребуется около года непрерывной работы.

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

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

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

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

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