Cтраница 3
В задачах регулярного математического программирования значительная часть методов основана на следующем исходном положении: если точки ж1 Е G и х2 Е G близки, то значения / ( ж1) и / ( ж2) также близки. В задачах дискретной оптимизации это положение не имеет места. Если в этом классе задач удается ввести естественным образом понятие окрестности, то близкие точки из этой окрестности могут сколь угодно значительно отличаться по значениям функции. В некоторых задачах дискретной оптимизации не удается естественным образом ввести понятие окрестности, оно вводится с помощью искусственных построений. [31]
Таким образом, в настоящей книге речь идет об алгоритмах решения комбинаторных оптимизационных задач и их практическом применении с использованием ЭВМ. Рассматриваются алгоритмы как точные, так и приближенные. Точными алгоритмами на определенном множестве задач называем те алгоритмы, которые дают теоретическую гарантию получения глобального решения оптимизационной задачи из этого множества. Подмножеством приближенных алгоритмов являются алгоритмы, дающие локальное решение задачи. Основным понятием в таких алгоритмах служит понятие окрестности. [32]
При рассмотрении геодезических линий возникает вопрос, всегда ли можно соединить две точки поверхности геодезической линией и притом единственным образом. На него в общем случае следует отрицательный ответ. В частности, хорошо известно, что две точки на цилиндрической по-ве. Чтобы исключить подобные случаи, вводят понятие геодезической окрестности точки, понимая под ней примыкающую к полюсу часть поверхности, заключенную внутри кривой г г ( геодезический окружности), радиус которой выбран с таким расчетом, что через любую точку внутри нее проходит одна и только одна геодезическая линия, соединяющая ее с полюсом. Эту единственную геодезическую линию часто называют нормальной геодезической. [33]
В задачах регулярного математического программирования значительная часть методов основана на следующем исходном положении: если точки ж1 Е G и х2 Е G близки, то значения / ( ж1) и / ( ж2) также близки. В задачах дискретной оптимизации это положение не имеет места. Если в этом классе задач удается ввести естественным образом понятие окрестности, то близкие точки из этой окрестности могут сколь угодно значительно отличаться по значениям функции. В некоторых задачах дискретной оптимизации не удается естественным образом ввести понятие окрестности, оно вводится с помощью искусственных построений. [34]