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

Требуется найти максимальное значение критерия:

. (1.10)

При ограничениях:

,

,

. (1.11)

Введем дополнительные переменные , , , с помощью которых неравенства (1.11) можно представить в виде равенств

,

,

. (1.12)

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

, , , .

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

,

.

Значение критерия при этом равно нулю

.

Соответствующий этому решению исходный базис образован векторами

, , .

Небазисные векторы

, , .

Разложим небазисный вектор по векторам базиса

,

где , , – коэффициент разложения, величины положительные.

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

,

,

,

значит , , .

Отсюда значение

.

Проверка условия (3.17) для вектора дает

.

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

, , .

Минимальное значение имеет величина , поэтому примем

.

Приращение критерия равно

.

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

,

,

,

,

,

.

Или в векторной форме:

.

Этому решению соответствуют базисные векторы

, , .

Подставляя полученное решение в выражение критерия, найдем

.

Теперь разложим вектор по векторам нового базиса.

.

Получим систему уравнений

,

,

,

решение которой

, , ,

Для базисного решения , получим

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

Величина , определяемая как наименьшее положительное отношение , в данном случае равна

.

Таким образом, в новом базисе исключается вектор и вместо него вводится вектор :

, ,

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

,

,

,

,

,

.

В векторной форме:

.

Прирост критерия оптимальности при переходе от базисного решения к новому базисному решению составляет

и новое значение критерия

.

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

.

Коэффициенты в разложении находим из системы уравнений

,

,

;

, , .

Вычисляем значение

.

Следовательно , что означает: новое базисное решение дает большее значение критерия оптимальности.

При этом значение с учетом базисного решения получается равным

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

, , .

Соответствующее ему базисное решение

,

,

,

,

,

.

В векторной форме записи:

.

Прирост критерия оптимальности составляет

,

.

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