В примере, рассмотренном в статье «Симплекс-метод
решения задач линейного программирования: типичный пример и алгоритм», система
ограничений была совместной и имелся конечный оптимум, причём единственный. В этой статье
проиллюстрирован случай, когда одно из условий нарушается: система несовместна, то есть,
не имеет ни одного решения, в том числе и оптимального.
Пример. Найти максимум функции 
при ограничениях
Решение.
Сведём систему ограничений-неравенств к системе уравнений путём введения
неорицательных добавочных переменных:
Переменные 
,
, 
примем за основные. Соответствующее базовое решение (0; 0; -9; -2; 8) —
недопустимое. Поэтому прежде всего воспользуемся симплексным методом для нахождения
допустимого базисного решения.
Шаг I. Основные переменные: 
,
, 
;
неосновные переменные 
,
. Выразим
основные переменные через неосновные (линейную форму пока не рассматриваем):
Переводим 
в основные переменные. Полагаем 
.
При 
имеем
и
переходит в
неосновные переменные.
Шаг II. Основные переменные 
, 
, 
; неосновные
переменные 
,
.
Снова выразив основные переменные через неосновные, приходим к системе
Во втором уравнении полученной системы и свободный член, и все
коэффициенты при неосновных переменных отрицательны. Это является признаком того, что данная
система несовместна. Она не имеет ни одного решения, в том числе и оптимального.
Поделиться с друзьями
Загрузка...
