Решение задач симплексным методом

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

Рис. 2. Переход от одной вершины к другой

Для решения задач симплексным методом надо освоить три основных элемента:

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

· правило перехода к лучшему решению

· критерий проверки оптимальности найденного решения

Кроме того, для решения задачи симплексным методом, она должна быть представлена в канонической форме (все неравенства должны быть заменены уравнениями). Для этого, если в неравенстве стоит знак " " или " ", надо ввести дополнительную переменную в левую часть уравнения, со знаком "-" при её коэффициенте, иначе со знаком "+". И так заменяются все неравенства.
Далее, на примере, показано как ищется оптимум в симплексной задаче, в алгебраическом виде.

Дана следующая функция цели:

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

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

Далее надо выбрать m - 4 основных (базисных) переменных. Они выбираются по следующему правилу: каждая из этих переменных должна входить в какое-либо уравнение один раз, при этом не должно быть такого уравнения, где не было бы ни одной из них (определитель этих переменных не должен быть нулевым). Исходя из этого правила, нам подходят x₃, x₄, x₅, x₆. Так как их знаки совпадают со знаком соответствующего свободного члена уравнения, то данное решение системы является допустимым, иначе надо искать первоначальное допустимое решение (смотрите следующий подраздел). Далее выражаем основные переменные через неосновные.

первое полученное решение выглядит как X₁=(0,0,18,16,5,21) - цифры это свободные члены в уравнении, где находится основная переменная (все переменные идут по порядку), если данная переменная неосновная, то пишем ноль. Так как в этом решении нет отрицательных компонент оно допустимо, о чём говорилось ранее. Но, глядя на функцию цели (5) мы видим, что в ней есть положительные переменные, а значит, её значение можно увеличить (за счёт любой из них). Выбираем для её увеличения, например, x₂. Сперва, надо определить границу роста этой переменной в каждом уравнении, при этом надо следовать следующим правилам:

· если переменной нет в уравнении, то граница роста равна бесконечности

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

· если свободный член отсутствует, а коэффициент больше или равен нулю, то граница так же равна бесконечности

· иначе (знаки при свободном члене и коэффициенте при переменной разные) граница равна частному от деления свободного члена на коэффициент при переменной

В данном примере получаем: x₂=min{18/3; 16/1; 5/1; ?}=5, выбирается самая маленькая граница, она и определяет разрешающее уравнение. В данном случае это третье уравнение. Теперь в разрешающем уравнении переводим x₂ в основные переменные (а значит x₅в дополнительные). И выражаем x₂ во всех уравнениях через его значение (уравнение).

Второе базисное решение так же допустимо и равно X₂=(0; 5; 3; 11; 0; 21). Теперь, надо выразить функцию через неосновные переменные.

Как видите, есть ещё положительная переменная x₁, а значит, текущее значение функции (F=15) можно увеличить. Повторяем все шаги, в итоге у вас должно получится значение 24. Из вышесказанного можно сделать вывод, что максимум функции цели достигнут тогда, когда в её уравнении нет ни одной положительной переменной, для минимума наоборот (задача на минимум решается так же, но надо убирать не положительные, а отрицательные переменные из уравнения функции).

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

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

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

Отсутствие конечного оптимума. Это когда на очередном шаге решения все границы роста равны бесконечности или минус бесконечности. Графически это выглядит, как отсутствие какое-то стороны многогранника области допустимых решений и функция может двигаться в эту сторону до бесконечности.

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