Понятие релаксации (комбинаторная релаксация, линейная релаксация, ранцевая релаксация, релаксация Лагранжа).
Релаксация
Для анализа задач-кандидатов (ЗК) (P) используется релаксация (ослабление) (PR), позволяющая находить верхнюю границу .
Определение. Задача (PR) называется релаксацией задачи (P), если выполняются следующие условия:
(1) ;
(2) для ;
(3) для из неравенства следует нераенство .
Именно трудности с решение задач-кандидатов обусловливают необходимость использования релаксаций. В качестве релаксаций используются либо линейные релаксации (когда опускаются условия целочисленности и решается соответствующая задача линейного программирования), либо лагранжевы релаксации.
Зондирование
Говорят, что задача-кандидат прозондирована, если выполняется одно из следующих условий:
(F1) анализ релаксированной задачи (PR) показал, что (P) недопустима. Так, из следует, что .
(F2) анализ релаксированной задачи (PR) показал, что (P) не имеет допустимых решений, лучших, чем текущий рекорд. Если , то .
(F3) анализ релаксированной задачи (PR) позволил найти оптимальное решение (P). Например, если ‑ оптимальное решение (PR), которое допустимо в (P), то ‑ оптимальное решение (P).
Если задача-кандидат (P) прозондирована с помощью одного из вышеописанных критериев, то дальнейшее исследование (P) или ее потомков (подзадач) не нужно. Если выполняется (F3) и , то рекорд заменяется на , а заменяется на .
Дата добавления: 2016-06-05; просмотров: 2079;