Метод плетей и границ в квадратичной задаче о назначениях

• Автор: Мартюшев, Алексей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 100 с.

Введение.
В диссертационной работе на основе интерпретации логических формул разработана реализация метода неявного перебора для поиска оптимума в задачах дискретной оптимизации. Получены новые теоретические результаты и предложен алгоритм поиска оптимума в известной ИР-полной квадратичной задаче о назначениях. Проведены вычислительные эксперименты, в ходе которых удалось решить задачи больших размеров, а также выявить те значения параметров алгоритма, при которых достигается наибольшая эффективность.
Под дискретной задачей в самом общем виде мы будем понимать следующую задачу.
Дано конечное множество С£. Требуется найти такой элемент а* £ С,?, который удовлетворяет определенным условиям.
Примером таких условий может служить минимизация некоторого функционала /, заданного на <3- В этом случае мы говорим о задаче дискретной оптимизации.
Мощность множества С}, как правило, зависит от некоторого параметра решаемой задачи. Если мощность растет экспоненциально с ростом этого параметра, то полный перебор всех элементов множества С} (что, очевидно, позволит найти элемент а*) неэффективен. В таких случаях предлагается использовать так называемый метод неявного перебора [1]. Суть его состоит в отсечении подмножеств множества С}, которые заведомо не содержат элемента а*.
Нестрого метод неявного перебора можно описать следующим образом.
Строится покрытие множества <3 конечными множествами. После этого

каждое множество Р покрытия анализируется. Этот анализ может дать три следующих результата:
1. В множестве Р нет элементов, удовлетворяющих поставленным условиям. В этом случае мы переходим к анализу следующего множества покрытия.
2. В множестве Р нашлись элементы, подозрительные на то, чтобы удовлетворять поставленным условиям. В этом случае мы запоминаем все подозрительные элементы и переходим к анализу следующего множества.
3. Анализ множества Р не дал ответ на вопрос о наличии элемента а*. В этом случае строится покрытие множества Р, и каждый элемент вновь построенного покрытие опять анализируется.
Когда не осталось ни одного множества для анализа, просматриваются все подозрительные элементы и выбирается среди них элемент а*.
Наиболее известной схемой, реализующей идеи метода неявного перебора, является метод ветвей и границ. Чаще всего этот метод используется для решения задач дискретной оптимизации, т.е. таких задач, в которых условие, которому должен удовлетворять элемент а*, - минимизация функционала, заданного на (. В ходе анализа множества Р в методе ветвей и границ ключевым моментом является оценивание (а именно, вычисление нижней оценки) функционала на этом множестве.
Покрытие (а точнее, разбиение) множества в этом методе определяется так называемым деревом’ частичных(решений - поддеревом полного дерева решений. К одному множеству такого разбиения относятся все элементы мно-

А = {71,,75}
/ 1 ї 1 2 З 2 2 2 3 1 у З З
Построим дерево Ковальского, разветвив пустой блок (очевидно полный) в корне по блоку А, а затем по соответствующим П[ в каждой из полученных вершин.
Заметим, что если все частичные решения в блоке А закрыты, а никакое частичное решение, являющееся их собственным подмножеством незакрыто, то мы, используя дерево Ковальского, решили бы задачу (1.1) за 5 просмотров. В то время, как при последовательном построении дерева частичных решений в методе ветвей и границ, нам потребовалось бы анализировать 10 частичных решений.
Таким образом, мы получили обобщение метода ветвей и границ, в котором оценивание производится также как и раньше, а ветвление осуществляется более общими методами, которые могут учитывать специфику задачи и начальных данных.
Используя дерево Ковальского, мы можем строить так называемые ''недревовидные"полные блоки - блоки, порожденные недревовидными минимально замкнутыми диаграммами. Применение дерева Ковальского по сравнению с ветвлением в традиционном методе ветвей и границ тем выгоднее, чем более "недревовиднее"и "закрытее"такие блоки.
В следующей главе мы покажем, как можно строить наборы блоков, названные плетьми, на которых базируется предлагаемый метод решения зада-