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