4.4. Симплексный метод решения задачи

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод). По латыни симплекс означает – простой, что в данном случае интерпретируется как простой выпуклый многогранник. Идея симплекс-метода разработана русским ученым Л.В.Канторовичем в 1939 г. На основе этой идеи американский ученый Д.Данциг в 1949 г. разработал симплекс-метод, позволяющий решить любую задачу линейного программирования. В настоящее время на основе этого метода разработаны пакеты программ, с применением которых решаются задачи линейного программирования.

Метод основан на следующих свойствах ЗЛП:

1. Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.

2. Множество всех планов ЗЛП выпукло.

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

4. Каждой угловой точке многоугольника решений отвечает опорный план ЗЛП.

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

На основании этого можно предложить достаточно простой метод решения ЗЛП, который сводится к следующему алгоритму:

• необходимо найти все опорные решения (узлы многогранника), множество которых является конечным;

• вычислить для каждого из опорных решений значение целевой функции;

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

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

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

Сравним результаты применения схем простого и направленного перебора на конкретном примере.

П

Предположим, что первым найденным базисным решением является вектор X¹ = (x¹₁, x¹₂), компоненты которого соответствуют координатам угловой точки А. При использовании схемы прямого перебора решений, мы, последовательно переходя от вершины к вершине (начиная с А и кончая узлом Н), вынуждены были бы испытать все семь вершин многоугольника. Предположим, что это позволило нам определить, что оптимум достигается в узле С.

ример. Рассмотрим случай, когда область допустимых решений ЗЛП представлена замкнутым выпуклым многоугольником ABCDEGH, представленном на рис 13.

х₂

C

х₁

B

D

E

G

A

H

Рис. 13

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

Очевидно, что для практического применения метода направленного перебора необходимо знать:

• алгоритм определения какого-либо первоначального допустимого решения задачи;

• алгоритм перехода к лучшему (точнее, не к худшему) решению;

• признак, указывающий на то, что найденное решение оптимально.

Итак, фундаментом универсального симплекс-метода решения ЗЛП является метод направленного перебора. Геометрическая интерпретация симплекс-метода состоит в последовательном переходе от одной (первоначально выбранной) вершины многогранника допустимых решений к другой, у которой целевая функция принимает лучшее или, по крайней мере, не худшее значение. Этот процесс происходит до тех пор, пока не будет найдена вершина, где достигается оптимальное значение целевой функции (если задача имеет конечный оптимум).