Cтраница 4
Во многих практических ситуациях не обязательно получить точное решение. Приемлемыми могут считаться такие решения, о которых известно, что их стоимость отличается от оптимальной на несколько процентов. Похожий Подход заключается в нахождении решений с помощью таких эвристических алгоритмов, для которых вычислены границы характеристик для наихудшего случая [36, 49, 46] ( см. гл. Эти границы являются фиксированными. Поскольку они должны быть справедливы во всех случаях ( включая вырожденные), то часто они оказываются весьма широкими. В методах, рассматриваемых в настоящей главе, допуск, определяющий величину максимального допустимого отклонения, может быть задан произвольно. Точность, определяемая этим допуском, в принципе достижима, но это может потребовать больше вычислительных ресурсов, чем выделено. Важную роль при этом играет получаемое эвристическими методами субоптимальное решение, которое дает начальную верхнюю границу. Алгоритм ветвей и границ может либо проверить, что данное решение удовлетворяет заданному допуску, либо построить новое решение, которое бы ему удовлетворяло. [46]