Альтернативный оптимум

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒

Задача № 3.3.

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

(3.21)

(3.22)

Решение.

Для решения поставленной задачи симплексным методом от стандартной формы записи задачи ЛП перейдем к канонической. Ведем балансовые переменные :

(3.23)

Составим расширенную матрицу системы :

По теореме Кронекера - Капелли система (3.23) совместна и имеет бесчисленное множество решений.

Так как ранг системы (3.23) равен двум, то базисных переменных будет ровно две. На первом шаге в качестве базисных переменных удобно взять балансовые переменные , так как система (3.23) легко разрешима относительно этих переменных.

I. - базисные переменные;

- свободные переменные.

Систему (3.23) решим относительно базисных переменных:

(3.24)

. (3.25)

Обнулив свободные переменные, получим опорное решение:

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

II. - базисные переменные;

- свободные переменные.

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

(3.26)

. (3.27)

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

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

, (3.28)

.

Обнулив свободные переменные, получим опорное решение:

; .

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

Для того, чтобы записать оптимальное решение, воспользуемся системой (3.26). Положим , где . В системе (3.26) переменная является свободной и в базисном решении . Отсюда ; .

Ответ. , .