Критерий недопустимости (кн).
Он формирует достаточные условия невозможности достижения ни одного допустимого решения при движении вперед из данной точки. Если эти условия выполняются, то говорят, что критерий отсеивает данную точку (критерий в данной точке сработал). В этом случае необходимо прекратить движение по векторной решетке с помощью шагов вперед и сделать шаг назад.
Этот критерий применяется к каждой недопустимой точке векторной решетки после первоначального попадания в нее при движении с помощью шагов вперед.
Определим дополнительные преобразования исходной задачи и новые понятия и обозначения, которые необходимы для формализованного описания действия КН.
Исходная задача
должна быть приведена к форме, где все
ограничения имеют вид неравенства типа
"
"
:
.
(3.37)
В каждое
-
ое ограничение вводится балансовая
переменная
(
i =
).
Получается
следующая, эквивалентная исходной
система ограничений:
;
, ( i =
). (3.38)
Необходимо отметить,
что балансовые переменные
в отличие от линейного программирования
не вводятся
в состав оптимизационных переменных,
а служат лишь для проверки выполнения
ограничений. Так, если вычисленная в
некоторой точке
балансовая переменная
,
то соответствующее i-ое
ограничение исходной задачи не
выполняется. Если же все
(i=
),
то
соответствующее решение является
допустимым.
При движении по векторной решетке может быть организован итеративный пересчет балансовых переменных, что исключит необходимость прямой подстановки вектора оптимизационных переменных в ограничения для проверки их выполнения.
Введем в рассмотрение два множества:
- множество
не выполняющихся в точке
ограничений;
- множество
номеров переменных, по
которым из точки
еще
можно сделать шаг вперед,
и при
которых коэффициенты в
м
ограничении
отрицательны.
Формальное определение этих множеств - следующее:
; (3.39)
.
(3.40)
Очевидно,
что осуществление шага вперед по
переменной
увеличивает
балансовую переменную
.
С
учетом этого формальное
правило действия КН
определяется
следующим образом: если в рассматриваемой
точке
при последовательной проверке очередного
не выполняющегося ограничения
(
)оказывается,
что
, (3.41)
где
Æ,
Или, что одно и то же,
(слева- максимально возможное увеличение балансовой переменной при движении вперед из рассматриваемой точки меньше, чем та величина (справа), на которую балансовую переменную нужно увеличить, чтобы сделать i-ое ограничение выполняющимся):
, (3.42)
то точка отсеивается по КН.
Для комбинаторной задачи (h[j]=1) условие (3.42) может быть записано:
Обоснование
этого правила
состоит в том, что,
даже сделав все возможные шаги
вперед по всем переменным
,
невозможно
обеспечить такое возрастание
,
при котором она станет неотрицательной,
т.е.
невозможно
при движении вперед добиться выполнения
-го
ограничения.
Критерий планомерного исключения альтернатив (кпиа).
Сущность его работы состоит в том, что он отсеивает те шаги вперед, которые не могут привести к лучшим (меньшим) по значению целевой функции решениям по сравнению с найденным ранее лучшим допустимым решением.
КПИА применяется к отдельным шагам вперед из рассматриваемой точки после того, как найдено хотя бы одно допустимое решение исходной задачи.
Каждый раз при нахождении нового допустимого решения, лучшего прежнего, действие КПИА корректируется (ужесточается).
Действие КПИА основано на использовании фильтрующего ограничения
, (3.43)
которое после введения балансовой переменой y[0]>0 преобразуется к виду
. (3.44)
Формальное правило КПИА:
шаг вперед по
-й
переменной из точки
не реализуется, если выполняется
следующее неравенство:
. (3.45)
Еще раз подчеркнем, что КПИА включается в работу, как только в ходе работы алгоритма НПВР найдено первое допустимое решение оптимизационной задачи, или с самого начала работы алгоритма, если допустимое решение может быть сформировано на основе априорной информации.
Правая часть фильтрующего ограничения корректируется каждый раз, когда находится новое допустимое решение, лучшее предыдущего. После такой корректировки отсев шагов вперед с помощью КПИА еще более возрастает.