Самым известным и широко применяемым на практике методом для решения задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным
алгоритмом, показал соответствующие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого заключается в комбинаторному характере симплекс-метода, последовательно перебирает вершины многоугольника допустимых решений при поиске оптимального решения.
Симплексный метод используют для решения любой задачи линейного программирования. С геометрического значения задачи линейного программирования получается, что для ее решения необходимо вычислить координаты всех вершин многоугольника ограничений и значения линейной формы в них. Решить задачи линейного программирования можно методом перебора. Действительно, перебором всех вершин можно найти такую вершину, где функция L имеет экстремальное значение. При этом возможны две трудности: поскольку при n> m система ограничений линейно зависима, то для построения многоугольника необходимо выделение всех линейно независимых систем уравнений и их решения; число вершин многоугольника резко возрастает с увеличением n> m, такой метод перебора всех вершин может оказаться очень трудоемким (n - число неизвестных, m - число ограничений). Симплексный метод обеспечивает более рациональное решение задачи, чем метод перебора. Его сущность заключается в том, что, отправляясь с некоторой произвольной вершины многоугольника ограничений, переходят к вычислению только такой вершины, в которой значение линейной формы будет больше, чем в предыдущей. Остальные варианты не вычисляют. Тогда при конечном сравнительно малом числе шагов может быть найден оптимальный план. Таким образом, проводится упорядоченный перебор вершин, при котором происходит постоянное увеличение линейной формы. Поэтому симплексный метод называют еще методом последовательного улучшения плана. Решение задачи симплексным методом включает два этапа. Первый заключается в нахождении одной произвольной вершины многоугольника ограничений, координаты которого определяют начальный опорный план. Второй этап заключается в последовательном упорядоченном переходе от одной вершины многоугольника к другому, смежному значение. Поскольку близлежащих вершин много, то каждый раз выбирают такую вершину, при переходе к которой обеспечивается наибольший рост линейной формы. На каждом шаге процесса улучшения плана проводят проверку на оптимальность. Очевидно, что план будет оптимальным, если среди вершин, прилегающих к переменной, нет такой, при переходе к которой рост линейной формы.
Рассмотрим алгоритм использования симплексного метода. Вычислительный процесс нахождения оптимального плана имеет итерационный характер. Каждая итерация состоит из двух этапов. Первый этап заключается в исследовании базисного решения на оптимальность. Если данный план удовлетворяет условиям оптимальности, то задача решена, в противном случае переходят ко второму этапу.