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