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

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

Симплекс-методпредставляет собой общий аналитический метод решения задачи линейного программирования^*.

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

При этом симплекс-метод предлагает алгоритм такого направленного перебора этих вершин, при котором нет необходимости рассматривать их все, поскольку при переходе от одного плана к другому происходит приближение к искомому решению (или установление неразрешимости).

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