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

Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.
Симплексный метод — это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.
Допустимое множество базисных решений системы линейных уравнений образует в объеме многогранное тело, например тетраэдр, вершины которого - угловые точки.
Каждой угловой точке многогранника решений соответствует опорный план (допустимое базисное решение).
Количество перебираемых допустимых базисных решений можно сократить и проводить не беспорядочный перебор, а последовательный по специальному алгоритму, улучшая значение целевой функции.
В тех случаях, когда модель содержит n уравнений, для построения опорных решений используются т переменных, принимающих некоторые положительные значения при нулевых значениях остальных свободных переменных. Вычислительная процедура может быть представлена в виде следующей последовательности.
Итеративный переход от одного допустимого базисного решения проводится направленно от одной вершины области допустимых решении к другой, заключающегося в обмене базисных и свободных переменных: базисная переменная приравнивается к нулю и переходит в свободную, а соответственно свободная переменная переводится на место базисной. Если в столбце свободных членов все элементы положительны, то решение является допустимым. Если в строке целевой функции все элементы неотрицательные, то решение является оптимальным при решении задачи на максимум.
В соответствии с симплексным методом на первом шаге находят начальное опорное решение - допустимый вариант, удовлетворяющий всем ограничениям. Затем последовательно за определенное число итераций направленно осуществляется переход от одного опорного решения к другому вплоть до оптимального. Следует заметить, что на первом шаге в качестве базисных переменных следует выбрать такие т переменные, каждая из которых входит только один раз в одно из т уравнений системы, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. При этом если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях, то полученное базисное решение будет допустимым. В процессе решения системы линейных уравнений необходимо ориентироваться на сохранение неотрицательности всех переменных, поскольку это определяет допустимость решения.
Для использования рассмотренного алгоритма симплексного метода к минимизации линейной формы связи F(X) следует искать максимум функции F(X) = — F(X), а затем полученное решение взять с обратным знаком.
Предложенный алгоритм приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система линейных уравнений задачи совместна.