Определение разрешающей строки. Определение разрешающей колонки

Определение разрешающей колонки.

Определение разрешающего элемента.

Проверка альтернативности найденного оптимального решения.

Проверка оптимальности найденного базисного решения.

Если решение допустимое, то решение проверяется на оптимальность с помощью следующего признака.

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

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

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

Разрешающий элемент указывает одну свободную и одну базисную переменные, которые следует поменять местами, чтобы получить новое «улучшенное» базисное решение.

Разрешающий элемент может быть определен по следующему алгоритму:

Если базисное решение не допустимое, то в строке содержащей отрицательное свободное число, выбирается отрицательный элемент. Колонка, в которой находится выбранный элемент, принимается в качестве разрешающей.

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

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

(5.20)

где r – индекс разрешающей колонки;

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

В качестве разрешающей выбирается та строка, для которой найденное оценочное отношение минимальное, т.е.

(5.21)

где s – индекс разрешающей строки.

Дата добавления: 2014-01-04