Алгоритм

симплекс–метода

1

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

Покажем итерационную природу симплекс- метода и вычислительные детали его алгоритма.

2

Итерационная природа симплекс-метода

На рисунке показано пространство решений ЗЛП из рассмотренного примера. Обычно алгоритм симплекс-метода начинается с исходной точки, где x1=х2=0 (точка А). В этой

начальной точке значение целевой функции z равно нулю. Возникает естественный вопрос: если одна или обе небазисные переменные x1 и

х2 примут положительные значения, то

приведет ли это к улучшению (возрастанию) значений целевой функции?

3

Для ответа на этот вопрос рассмотрим целевую функцию:

4

Очевидно, что если переменная х1 или переменная х2 (или обе сразу) примут

положительные значения, то это приведет к увеличению значения целевой функции (помните, что рассматривается задача

максимизации).

Однако алгоритм симплекс-метода на каждом шаге допускает изменение значения только одной небазисной переменной.

5

1. Если увеличивать значение переменной х1,

то (см. рисунок) ее значение должно возрасти таким образом, чтобы соответствовать угловой точке В (повторяю, что внутренние точки отрезка от точки А до точки В неприемлемы, поскольку кандидатом на оптимальное решение может быть только угловая точка).

В точке В симплекс-метод должен увеличить значение переменной х2, перемещаясь при этом

в угловую точку С.

6

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

2. Если сначала увеличивать значение переменной х2, то следующей угловой точкой

будет точка D, из которой процесс решения переходит в оптимальную точку С. Здесь алгоритм симплекс-метода создает путь .

7

Отметим, что оба пути, и , расположены вдоль границы пространства решений.

Это означает, что симплекс-метод не может сразу перескочить из точки А в точку С.

8

Возникает вопрос: существует ли правило, в соответствии с которым можно было бы определить, какую небазисную переменную сделать положительной в данной угловой точке?

Например, в точке А как переменная х1 так и переменная х2 могут увеличить значение

целевой функции.

Симплекс-метод предлагает простое правило выбора переменных, которое в основном применяется в его программных реализациях.

9

Т.к. рассматривается задача на максимум, то

следует	выбирать	такую	небазисную
переменную, которая		имеет	наибольший
положительный коэффициент			в выражении

целевой функции. Если таких переменных несколько, то выбор произвольный. ПОНИМАЕМ, что это - эмпирическое правило, сформулированное на основе компьютерных вычислений симплекс-метода.

В большинстве случаев (но не всегда!) применение этого правила ведет к наименьшему числу итераций, затрачиваемых

на поиск оптимального решения.

10

11