Комбинаторная оптимизационная задача

Cтраница 1

Комбинаторные оптимизационные задачи, как правило, являются задачами большой размерности. Под размерностью понимаем размерность того комбинаторного пространства, в котором определена задача. Естественно, что количество ограничительных условий также влияет на время решения задачи: может увеличивать или уменьшать время счета. [1]

Комбинаторная оптимизационная задача состоит в отыскании среди конечного множества альтернатив одной, которой отвечает экстремальное значение принятой целевой функции. В самой простой модификации задачи обработки деталей конечное множество альтернатив включает ( n) h допустимых последовательностей обработки п деталей на k станках. [2]

Классическим примером комбинаторной оптимизационной задачи служит задача коммивояжера. Как показывает практика, наиболее эффективными в применении к ней являются алгоритмы, учитывающие ее комбинаторные свойства. Состоит она, как известно, в следующем. [3]

Приведены результаты исследований, касающиеся вопросов формализации комбинаторных оптимизационных задач и методов их решения, а также разработки и использования пакетов программ, ориентированных на решение задач из данной области. Представление комбинаторных оптимизационных задач как задач математического программирования в определенных комбинаторных пространствах позволило систематически изложить ряд новых методов, не охваченных известной монографической литературой. Рассмотрены также схемы основных известных методов, освещенных в литературе и достаточно хорошо зарекомендовавших себя на практике. [4]

Эти задачи составления расписаний попадают в категорию больших комбинаторных оптимизационных задач, многие из которых являются ЛГР-полными и считаются традиционно трудноразрешимыми. Главное внимание в этой главе было уделено получению при заданном количестве вычислительных ресурсов наиболее полезной информации, необходимой для осуществления упорядочения заданий либо в виде оптимального расписания ( когда это возможно), либо в виде расписания с обеспечением заданной точности относительно оптимального. [5]

Так же, как и идеальная, она является комбинаторной оптимизационной задачей. [6]

Таким образом, в настоящей книге речь идет об алгоритмах решения комбинаторных оптимизационных задач и их практическом применении с использованием ЭВМ. Рассматриваются алгоритмы как точные, так и приближенные. Точными алгоритмами на определенном множестве задач называем те алгоритмы, которые дают теоретическую гарантию получения глобального решения оптимизационной задачи из этого множества. Подмножеством приближенных алгоритмов являются алгоритмы, дающие локальное решение задачи. Основным понятием в таких алгоритмах служит понятие окрестности. [7]

Учитывая это, в предметной области пакетов целесообразно выделять из класса комбинаторных оптимизационных задач ряд подклассов, оптимизационный функционал которых определяется на одном из подпространств X. Это позволит при решении задач подкласса отсекать ряд заведомо недопустимых вариантов и тем самым значительно сократить вычислительную работу. [8]

Генетические алгоритмы входят в инструментарий DM & KDD как мощное средство решения комбинаторных и оптимизационных задач. В задачах извлечения знаний применение генетических алгоритмов сопряжено со сложностью оценки статистической значимости полученных решений и с трудностями построения критериев отбора удачных решений. Представителем пакетов из этой категории является GeneHunter фирмы Ward Systems Group. [9]

Мы можем разбить вычггслительные методы, предназначенные для составления расписаний ( или решения других комбинаторных оптимизационных задач), на классы в соответствии с тем, предназначены ли они для определения оптимального решения или только приближенного решения. [10]

В главе 8 содержатся основные данные о пакетах семейства ВЕКТОР, ориентированных на решение комбинаторных оптимизационных задач. Изложение иллюстрировано результатами численных экспериментов, проведенных посредством применения одного из пакетов данного семейства. Глава 9 содержит краткий обзор пакетов программ решения различных классов оптимизационных задач, которые разработаны в последние годы в Институте кибернетики АН УССР и в других организациях страны, тесно сотрудничающих с ним. [11]

Предварительное изучение и апробация МВС показали, что он достаточно универсален, дает хорошие численные результаты и успешно может быть применен как для решения задач размещения, так и для других типов комбинаторных оптимизационных задач. [12]

Понятие комбинаторной оптимизационной задачи разъясняется в первой главе. Здесь отметим только, что оно не противоречит ни интуитивному представлению, ни используемым в литературе понятиям. Существенной особенностью излагаемого материала является то, что он носит практический уклон и интерпретирован описанными в работе пакетами прикладных программ. [14]

Метагенетический оптимизационный процесс. [15]

Страницы: 1 2