Cтраница 3
Решение задач дискретной оптимизации связано с трудностями принципиального характера. Полный перебор точек допустимого множества, как правило, неосуществим из-за слишком большого объема вычислительной работы. [31]
Центральным алгоритмом в описываемом подходе является алгоритм кластеризации - разбиения множества точек на непересекающиеся подмножества близких точек. Задача кластеризации - это задача дискретной оптимизации, для ее решения применяются стандартные подходы: построение начального разбиения и его улучшение. [32]
Многие из методов решения задач дискретной оптимизации основаны на идее перебора вариантов, качество алгоритма оценивается числом точек х, для которых вычислялись значения f ( x) или значения некоторых других функций. Выше было отмечено, что объем вычислительной работы резко возрастает с ростом числа переменных. Поэтому перебор большого числа вариантов принципиально невозможен ни при каком быстродействии ЭВМ, хотя рост быстродействия ЭВМ позволяет решать задачи, решение которых на ЭВМ с более низким быстродействием не представлялось возможным. [33]
Далее в этой главе приводятся определения, некоторые полезные идеи и теоремы и дается краткое изложение материала, касающегося рассматриваемых здесь вопросов для непрерывного случая, когда можно использовать методы математического анализа. В конце главы приводятся примеры задач дискретной оптимизации. [34]
Задачи геометрического проектирования, как правило, имеют большую размерность. Вместе с тем эффективность точных методов решения задач дискретной оптимизации существенно зависит от размерности, причем с ее возрастанием резко увеличивается объем вычислений, необходимых для отыскания точного решения. Обычно он настолько велик, что точно решить задачу за реальное время не возможно. Поэтому возникает необходимость в выборе эффективных приближенных методов дискретной оптимизации. В настоящее время разработано большое число приближенных методов, например [5, 22, 33, 43, 44, 151, 155, 160,161] и др., успешно применяемых при решении различных практических задач, в том числе задач геометрического проектирования. Ниже описан метод вектора спада согласно работам [114, 115] и его применение иллюстрируется к задачам разбиения и покрытия. [35]
Рассмотрим примеры двух задач дискретной оптимизации: задачу о ранце и задачу о коммивояжере. Эти задачи часто рассматриваются как тестовые при разработке алгоритмов решения задач дискретной оптимизации. [36]
Задачи дискретной оптимизации - это задачи нахождения экстремума функции, заданной на дискретном ( чаще всего - конечном) множестве точек. Если область определения функции состоит из конечного числа точек, то задачу дискретной оптимизации всегда, в принципе, можно решить перебором всего этого множества. Однако на практике это множество хоть и конечно, но может быть очень велико, так что методы перебора не эффективны. Рассмотрим несколько общих подходов к решению задач дискретной оптимизации. [37]
В настоящей главе приводится обзор современного состояния целочисленного программирования. Здесь излагаются идеи основных методов ( точных ( § 2) и приближенных ( § 3)) решения задач дискретной оптимизации. В § 4, 5 изложено состояние вопроса о вычислительной сложности задач целочисленного программирования. [38]
В последнее время в нашей стране создан целый ряд автоматизированных систем, в том числе систем, предназначенных для автоматизированного решения с помощью ЭВМ многих задач проектирования вычислительных средств, размещения промышленных предприятий, проектирования сложных инженерных сооружений, автоматизированной обработки данных в реальном масштабе времени, характеризующих быстропротекающие процессы различной природы. Получены интересные результаты в области разработки и исследования новых математических моделей ряда важных процессов, создания эффективных математических методов решения задач, возникающих при построении всевозможных автоматизированных систем, в частности, задач дискретной оптимизации в различных постановках, и их современного программного обеспечения. В этом интенсивно развивающемся научном направлении важные результаты получены различными коллективами ученых под руководством академиков В. М. Глушкова, А. А. Дородницына, чл. [39]
В задачах регулярного математического программирования значительная часть методов основана на следующем исходном положении: если точки ж1 Е G и х2 Е G близки, то значения / ( ж1) и / ( ж2) также близки. В задачах дискретной оптимизации это положение не имеет места. Если в этом классе задач удается ввести естественным образом понятие окрестности, то близкие точки из этой окрестности могут сколь угодно значительно отличаться по значениям функции. В некоторых задачах дискретной оптимизации не удается естественным образом ввести понятие окрестности, оно вводится с помощью искусственных построений. [40]
Алгоритмы локальной оптимизации связаны с понятием окрестности. В регулярных задачах математического программирования это понятие вводится естественным образом и является основным при разработке алгоритмов и исследовании их сходимости. Во многих задачах дискретной оптимизации понятие окрестности не удается ввести естественным образом, в этом состоит одна из принципиальных трудностей, возникающих при решении задач этого типа. [41]
В действительности схемы сетей намного сложнее, чем на рис. 4.17. В ряде узлов имеются КУ разных типов. При отказе от допущений 1) - 4) задача оптимизации становится нелинейной и сильно усложняется из-за учета напряжений и нелинейности стоимости КУ. В наиболее общем виде эта задача дискретной оптимизации, так как мощность компенсирующих устройств, например БК, меняется дискретно, а не непрерывно. [42]
В нашем случае переборный путь состоит в перечислении всех 2 подмножеств V, отборе из них / / ( G) и. Объем перебора растет при этом очень быстро - экспоненциально - с ростом числа вершин гиперграфов. Существуют различные эвристические приемы сокращения перо-бора в задачах дискретной оптимизации, фигурирующие обычно под шифром метода ветвей и границ. [43]
Задачи дискретной оптимизации - это задачи нахождения экстремума функции, заданной на дискретном ( чаще всего - конечном) множестве точек. Если область определения функции состоит из конечного числа точек, то задачу дискретной оптимизации всегда, в принципе, можно решить перебором всего этого множества. Однако на практике это множество хоть и конечно, но может быть очень велико, так что методы перебора не эффективны. Рассмотрим несколько общих подходов к решению задач дискретной оптимизации. [44]
Возникает задача вычислительной оценки с предварительным исключением абсурдных и неконкурентоспособных вариантов. В основу их положен принцип представления процесса решения в виде многоступенчатой структуры. Каждая ступень связана с проверкой наличия тех или иных свойств у подмножества вариантов, по которым либо непосредственно сокращается исходное множество, либо подготавливается возможность такого сокращения в будущем. Одним из правил отсева бесперспективных вариантов является принцип монотонной рекурсивности, применяемый для решения задач дискретной оптимизации при пошаговом конструировании вариантов. [45]