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