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

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

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

Решение.

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

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

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

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

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

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

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

Ссылка на основную публикацию