Основы симплекс–метода

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

Известен классический метод решения систем линейных уравнений, называемый методом Гаусса–Жордана. Основная идея этого метода состоит в сведении системы уравнений с неизвестными к каноническому или ступенчатому виду при помощи элементарных операций над строками. К ним относятся:

1) умножение любого уравнения системы на положительное или отрицательное число;

2) прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

При использовании первых переменных ( ) каноническая система имеет следующий вид:

(2.19)

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

Например, в системе (2.19) одно из базисных решений задаётся как Если к тому же неотрицательны, то полученное решение называется допустимым базисным решением. В указанной системе для удобства записи в качестве базисных используются первые переменных. В действительности для получения канонической системы уравнений и базисного решения любые m из переменных можно выбрать в качестве базисных.

Это означает, что максимальное число базисных решений задачи ЛП с m ограничениями и n переменными, записанной в стандартной форме, конечно и выражается следующим образом:

.

Интуитивный подход к решению задачи ЛП, обладающий оптимальным решением, состоит в нахождении при помощи метода Гаусса–Жордана всех возможных допустимых базисных решений и последующем выборе решения, которому соответствует наилучшее значение целевой функции. Однако при решении задач ЛП симплекс–метод оказывается более эффективным, так как при этом анализируется лишь часть всех допустимых базисных решений.

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

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

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

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

Рассмотрим шаг 2 симплекс–метода в предположении, что базисное решение, задаваемое системой (2.19), допустимо. Пусть допустимое базисное решение задано в следующем виде:

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

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

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

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

.

Симплекс–метод даёт возможность проверить существование допустимого базисного решения с большим значением . Для этого сначала проводится проверка оптимальности рассматриваемого решения. Если оно не оптимально, симплекс–метод позволяет перейти к смежному допустимому базисному решению с большим (или, по крайней мере, не меньшим) значением . Оно отличается от рассматриваемого только одной базисной переменной.

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

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

(2.20)

Из системы (2.20) при возрастании от 0 до 1 получаем новое решение: