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

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

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

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

Решение.

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

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

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

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

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

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

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

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