Введение к работе
Актуальность темы. В задачах дискретной оптимизации для поиска оптимального решения в заданном конечном множестве решений, как правило, используется метод неявного перебора. Суть его состоит в последовательном разбиении множества решений на подмножества и отсечении тех подмножеств, которые заведомо не содержат оптимального решения. Наиболее известной схемой, реализующей эту идею, является метод ветвей и границ. В нем разбиение множества решений определяется так называемым деревом частичных решений - поддеревом полного дерева решений. К одному множеству такого разбиения относятся все ветви полного дерева решений, являющиеся продолжениями ровно одной ветви в дереве частичных решений.
Однако, существуют задачи дискретной оптимизации, обладающие свойством многоэкстремальности, т. е. наличием большого числа решений, на которых целевая функция достигает значений, близких к оптимальному, причем эти решения являются продолжениями таких ветвей, которые отстоят "далеко" друг от друга в любом дереве частичных решений. В таких случаях метод ветвей и границ становится неэффективным. Поэтому оказывается актуальным создание "недревовидной" техники разбиения (или покрытия), более компактно чем любое дерево частичных решений представляющей все множество решений.
Примером многоэкстремальной задачи является NP-полная квадратичная задача о назначениях. Оптимальное назначение здесь в общем случае удается найти лишь тогда, когда параметр, определяющий задачу, принимает очень неболыпие значения (до 20). Многие практические задачи такие как некоторые задачи транспортной логистики или задача проектирования микросхем сводятся к квадратичной задаче о назначениях. В связи с этим в настоящее время остается актуальным построение эффективных алгоритмов для таких задач, как квадратичная задача о назначениях.
Цель работы. Целью диссертационной работы является
построение общей схемы метода плетей и границ метода поиска оптимума в задачах дискретной оптимизации;
определение способов разбиения множества всех решений и способа оценивания функционала в рамках построенного метода для квадратичной задачи о назначениях;
разработка нового алгоритма поиска оптимума в этой задаче.
Методы исследований. Формализация метода плетей и границ построена на основе интерпретации формул исчисления высказываний. При доказательстве теорем и обосновании способов разбиения множества решений и оценивания плетей использованы методы теории множеств, комбинаторики, теории графов. Проведены численные эксперименты на компьютере.
Научная новизна. Построена и обоснована общая схема метода нахождения оптимума в задачах дискретной оптимизации - метода плетей и границ. Формализовано правило подстановки, которое позволяет получать специальные наборы частичных решений плети. Доказана теорема о полноте набора плетей в задаче дискретной оптимизации, которая гарантирует, что набор плотей, построенный по правилу подстановки, покрывает все множество решений задачи.
Метод плетей и границ применен для квадратичной задачи о назначениях. Для этой задачи получены:
методы формирования плетей, которые "легко" оцениваются;
способы оценивания плетей;
способы формирования полного набора плетей;
алгоритм нахождения оптимального назначения, параметрами которого являются интерпретируемые невыполнимые формулы.
Кроме того, в результате численных экспериментов выбраны формулы, использование которых в алгоритме дает наибольшую эффективность по времени.
Теоретическая и практическая ценность. Построенная схема метода плетей и границ может бьпь использована для любых задач дискретной оптимизации. При этом достаточно, используя семантику задачи, определить способ оценивания и адекватные данной задаче формулы, на основании которых последовательно строятся покрытия множества решений. При этом появляется стимул к поиску новых "недревовидных" формул, называемых в логике "тяжелые" тавтологии.
Предложенная алгоритмическая реализация метода может быть использована при составлении компьютерных программ для нахождения оптимального решения в некоторых задачах транспортной логистики, задачах проектирования микросхем, задачах расположения отделений в клинике и подразделений на предприятии, т. к. все эти задачи формулируются как квадратичная задача о назначениях.
Апробация работы. Полученные результаты обсуждались на семинарах кафедры исследования операций и докладывались на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск. 2004).
Публикации. Основные результаты диссертации опубликованы в работах [1-2].
Структура и объем работы. Диссертация объемом 101 страница состоит из введения, четырех глав, разбитых на параграфы, заключения и списка литературы, содержащего 57 наименований.
