Проверка допустимости базисного решения

Проверка ограниченности целевой функции.

Проверка совместности системы ограничений.

Следующим этапом, согласно вышеприведенному алгоритму симплекс-метода, является проверка совместности системы ограничений задачи линейного программирования, т.е. наличия области допустимых решений.

Признак несовместности системы ограничений задачи линейного программирования (признак 1): ограничения несовместны, если в любой строке (кроме строки целевой функции), имеющей отрицательное свободное число , нет ни одного отрицательного элемента.

Признак ограниченности целевой функции (признак 2): целевая функция ограниченна в области допустимых решений, т.е. существует конечное максимальное (минимальное) значение целевой функции, если на каждой итерации в каждом столбце, в строке целевой функции которого находится отрицательный (положительный) элемент, есть хотя бы один положительный элемент (данный признак не распространяется на колонку свободных чисел ).

Согласно определению допустимым базисным решением (опорным планом) называют базисное решение, удовлетворяющее условию неотрицательности, т.е. .

Удобно допустимость базисного решения проверять по симплекс-таблице в соответствии со следующим правилом (признак 3): базисное решение будет допустимым, если в симплекс-таблице все свободные числа (кроме строки целевой функции) неотрицательные.

Дата добавления: 2013-12-12