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

СИМПЛЕКС-МЕТОД: СЛУЧАЙ, КОГДА СИСТЕМА НЕ ИМЕЕТ НИ ОДНОГО РЕШЕНИЯ

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

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

Решение.

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

Переменные , , примем за основные. Соответствующее базовое решение (0; 0; -9; -2; 8) - недопустимое. Поэтому прежде всего воспользуемся симплексным методом для нахождения допустимого базисного решения.

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

Переводим в основные переменные. Полагаем . При имеем и переходит в неосновные переменные.

Шаг II. Основные переменные , , ; неосновные переменные , . Снова выразив основные переменные через неосновные, приходим к системе

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

Нет времени вникать в решение? Можно заказать работу!

Начало темы "Линейное программирование"

Задача и теоремы линейного программирования, примеры формулировки задач

Графический метод решения задач линейного программирования

Пример задачи линейного программирования: задача использования ресурсов, её графическое решение

Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм

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

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

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