"Чистая"
и прикладная математика

Симплекс-метод: случай, когда максимум целевой функции - бесконечность

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

Пример. Найти максимум функции при ограничениях

Решение.

Введём добавочные неотрицательные переменные и сведём систему ограничений-неравенств к системе уравнений

Получили два уравнения с четырьмя переменными. Если взять за основные переменные и , то исходное базисное решение (0; 0; 9,2) - допустимое.

Шаг I. Основные переменные: , ; неосновные переменные , . Выразим основные переменные и линейную форму через неосновные:

Переводим в основные переменные, так как входит в выражение F с бОльшим положительным коэффициентом. Полагаем . При имеем и переходит в неосновные переменные.

Шаг II. Основные переменные , ; неосновные переменные , . Выразив основные переменные и линейную форму через неосновные, получим

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

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

Назад<<<ЛистатьВперёд>>>
Начало темы "Линейное программирование"

Поделиться с друзьями