Алгоритм симплекс-метода

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

Алгоритм симплекс-метода включает следующие основные шаги:

1. Выбор начального допустимого базисного решения.

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

3. Проверка условий оптимальности текущего решения. Если некоторое допустимое базисное решение нельзя улучшить, то оно принимается в качестве оптимального, и алгоритм заканчивает работу. В противном случае переходим к шагу 2.

Рассмотрим подробно шаг 2 в предположении, что базисное решение, задаваемое системой (2.7), допустимо и имеет вид:

базисные переменные

небазисные переменные

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

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

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

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

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

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

Выведем формулу, по которой вычисляются оценки небазисных переменных. Пусть некоторой небазисной переменной присвоено значение 1. Исследуем, как это повлияет на значение целевой функции. Заметим, что поскольку рассматриваются только смежные допустимые базисные решения, то остальные небазисные переменные по-прежнему равны нулю. Поэтому систему (2.7) можно переписать в виде:

(2.8)

Если в системе (2.8) увеличить значение от нуля до единицы, то получим новое решение системы:

Для этого решения целевая функция примет новое значение:

Обозначим через приращение величины , получающееся при увеличении на единицу. Тогда

Новое значение - Старое значение =

(2.9)

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

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

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

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

Для ответа на этот вопрос вспомним, что при увеличении остальные базисные переменные также меняются, а их новые значения определяются из системы (2.8):

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

. (2.10)

Пусть минимальное отношение правой части достигается при , то есть, в -м уравнении:

.

Это означает, что при увеличении до базисная переменная первой среди базисных переменных обращается в нуль и заменяется в базисе переменной . То есть в -м уравнении новой базисной переменной становится и новое допустимое базисное решение имеет вид:

(2.11)

Поскольку при увеличении на единицу приращение составляет , то для нового решения общее приращение равно

.

Уравнение (2.10), на основании которого определяются базисные переменные, выводимые из базиса, носит название правила минимального отношения. При использовании симплекс–метода вычисление относительных оценок всех небазисных переменных текущего допустимого базисного решения (2.11) и проверка его оптимальности проводится до тех пор, пока не будут выполнены условия оптимальности.