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

Двумерные задачи линейного программирования решаются графически. Для случая n =3 нужно ужерассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

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

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

А поскольку экстремум функции цели (6.4) достигается в вершинах многогранника, то, казалось бы, достаточным вычислить значение функции цели во всех вершинах многогранника, а затем найти ту из них, в которой функция достигает своего минимума или максимума. Но такой путь решения задач ЛП, даже с относительно небольшим числом ограничений и неизвестных параметров, практически неосуществим, т.к. процесс отыскания вершин весьма трудоемкий, а число вершин может оказаться астрономически большим.

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

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

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

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

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

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

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