4. Симплекс – метод решения задачи лп.

Является основным методом решения задач ЛП, представленных в канонической форме записи.

Разработан в 1949 г. американским математиком Дж. Данценгом.

Идея симплекс – метода заключается в следующем.

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

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

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

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

Если экстремум не достигнут, то осуществляется переход к ближайшему допустимому

базисному решению, соответствующему соседней вершине многогранника, для которой

значение целевой функции возрастает (при поиске max) или убывает (при поискеmin).

Рассмотрим метод на примере:

при ограничениях

Если ввести дополнительные слабые переменные :

;;;;.

Перепишем задачу в следующем виде

;

Общее число переменных m+n= 5, число уравнений в системе ограниченийm= 3. Следовательно, в каждом базисном решении имеется две свободных и три базисных переменных.

Выберем в качестве свободных переменные и. Приравняем их нулю и получим базисное решение:

;;;;.

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

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

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

Укажем способ, по которому производится выбор таких переменных.

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

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

При увеличении дляуменьшаются значения переменныхи. Переменнаяпринимает нулевое значение при; переменнаяпри. Следовательно, свободной переменной вместодолжна стать переменная.

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

В частности для второго уравнения:

для третьего : - неустойчивость

для четвертого : .

Таким образом, для перехода к новому допустимому базисному решению, увеличивающему значение Fнеобходимо перевести:

- из свободных в базисные;

- из базисных в свободные переменные.

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

Процедура, с помощью которой это достигается, называется сменой базиса и осуществляется следующим образом:

- уравнение, соответствующее базисной переменной, переводимой в свободные () , делится на коэффициент при свободной переменной, переводимой в базисные ();

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

Продолжим пример:

После первого шага, называемого нормировкой:

После второго шага окончательно получаем:

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

;;;;;F=8.

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

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

Выполняем схему базиса и получаем:

;;;;;F=10.

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

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

В случае задачи максимизации – это неотрицательные коэффициенты в выражении целевой функции; минимизации – неположительные.

С учетом сказанного общая схема решения задачи ЛП симплекс – методом имеет вид:

Начало

Выбор исходного

допустимого базиса

проверка

отличимости

решения

Нет Конец

Определение свободной переменной,

переводимой в базисные

Определение базисной переменной,

переводимой в свободные

Смена базиса