Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Критерий оптимальности допустимого базисного плана

Подводя итог сказанному, сформулируем критерий оптимальности допустимого базисного плана в симплекс-методе:

F план является оптимальным, если для всех j 1: n a0,j(q)) ≥ 0, и неоптимальным в противном

случае, т. е. если существует такое l l : n, что a0l(q)) < 0.

Значения a0,j(q)) также называют оценками столбцов матрицы А относительно текущего базиса, или симплекс-разностями.

В случае неоптимальности текущего базиса в алгоритме симплекс-метода осуществляется переход к следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для обеспечения улучшения значения целевой функции в базис должен быть введен вектор-столбец, имеющий отрицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется выбирать столбец, имеющий максимальную по модулю оценку. Отметим, что данное правило носит относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на этой стадии требуется принять решение о том, какой столбец следует вывести из базиса. Сделать это нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы {а2,а3} образуют допустимый базис, а векторы {а3,a4} —недопустимый, т. к. разложение b по а3 и а4 содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.