Cтраница 1
Решение оценочных задач является наиболее трудоемкой частью алгоритмов типа ветвей и границ. Предположим, что имеется список алгоритмов Р ( Pi... [1]
Для решения оценочных задач целесообразно применять алгоритм, основанный на построении 1-дерева. [2]
Опишем более подробно алгоритм решения оценочной задачи. [3]
О выборе ПН, используемых для решения конкретных оптимизационных и оценочных задач, говорилось в § 2.5. Критерий надежности определяется решаемой оптимизационной задачей надежности. [4]
При т 1 применение основного алгоритма связано с использованием симплексного алгоритма для решения оценочных задач, что не всегда удобно. Решим m линейных одномерных задач. В задаче с номером г рассматривается лишь ограничение с этим номером. [5]
Нормативы надежности должны представлять собой систему взаимосогласованных между собой нормативов, обеспечивающих в свою очередь возможность взаимосогласованного решения оптимизационных и оценочных задач надежности при управлении развитием и эксплуатацией СЭ. Кроме того, нормативы надежности для отдельных специализированных СЭ должны быть согласованы в рамках ЭК в целом. [6]
Под методом ветвей и границ понимается алгоритм решения задачи, имеющий древовидную структуру поиска оптимального решения и использующий результаты решения оценочных задач. Древовидная структура называется обычно деревом ветвления. [7]
Последнее утверждение следует из того, что для числа вершин дерева ветвления в е-оптимальном алгоритме имеет место полиномиальная оценка, а трудоемкость решения линейной оценочной задачи в каждой вершине дерева также имеет полиномиальную оценку. [8]
Как уже многократно отмечалось, трудоемкость алгоритма определяется числом решенных оценочных задач. В описанном алгоритме решение оценочной задачи сводится к процедуре приведения матрицы расстояний. Экономная ее реализация может существенно сократить время решения задачи. [9]
Легко видеть, что кратчайший путь из ( 0, 0) в ( т, Р) как раз и дает решение оценочной задачи. [10]
Эта задача также трудна, как и исходная, в случае, если множество X произвольно. Под непрерывной здесь понимается задача, в которой дискретное множество X заменено, например, его выпуклой оболочкой. Умея вычислять оценку задачи (8.58), оптимальное ее решение можно получить, используя эту оценку в стандартной схеме метода ветвей и границ. При решении оценочной задачи (8.60) использование традиционных методов выпуклого и линейного программирования оказывается неэффективным. Это связано с тем, что (8.60) является задачей максимизации недифференцируемой выпуклой функции с астрономическим, в большинстве случаев, числом граней. [11]