Метод перебора решения ЗЛП

Пример 2.

1) Решить графически задачу

Решение. Выразим две переменные (базисные) через другие две (свободные).

Исключим переменные и из системы.

Исключим их из целевой функции. Получаем задачу:

Ответ:

2) Найти все базисные и опорные решения системы ограничений.

Решение.

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

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

Базис	Базисное решение	Опорное решение
	Не существует

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

Метод перебора решения ЗЛП

1. Найти все опорные решения системы ограничений задачи.

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

3. Выбрать наибольшее (наименьшее) значения.

Недостатки метода перебора?