Метод плетей и границ в квадратичной задаче о назначениях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Санкт-Петербургский государственный университет

На правах рукописи

Мартюшев Алексей Владимирович

МЕТОД ПЛЕТЕЙ И ГРАНИЦ В КВАДРАТИЧНОЙ ЗАДАЧЕ О НАЗНАЧЕНИЯХ

специальность 01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2005 г.

Работа выполнена на кафедре исследования операций математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: кандидат физико-математических наук,

доцент Давыдова Инна Михайловна

Официальные оппоненты: доктор физико-математических наук,

профессор Сушков Юрий Акимович

кандидат физико-математических наук, доцент Новиков Федор Александрович

Ведущая организация: Санкт-Петербургский

экономико-математический институт РАН

^

Защита состоится «»... .................2005с. в....//......ча-

сов на заседании диссертационного совета Д 212.232.29 по зА;—е дис-совтнаШйсеични0кяисверт8цийнн«1й1яо?етагД21|и23Й1а9 шовяшатеяисх еертэций ©агсйисЬаниб^ченойстепенФ'ЯйкторагфийвкремввФматичезеих

С диссертацией можно ознакомиться в научной библиотеке Санкт-Петербургского государственного университета по адресу: Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан • <¡/10» ......... 2005г.

Ученый секретарь

диссертационного совета Д 212.232.29 доктор физ.-мат. наук, профессор

В. М. Нежинский

Общая характеристика работы

Актуальность темы. В задачах дискретной оптимизации для поиска оптимального решения в заданном конечном множестве решений, как правило, используется метод неявного перебора. Суть его состоит в последовательном разбиении множества решений на подмножества и отсечении тех подмножеств, которые заведомо не содержат оптимального решения. Наиболее известной схемой, реализующей эту идею, является метод ветвей и границ. В нем разбиение множества решений определяется так называемым деревом частичных решений - поддеревом полного дерева решений. К одному множеству такого разбиения относятся все ветви полного дерева решений, являющиеся продолжениями ровно одной ветви в дереве частичных решений.

Однако, существуют задачи дискретной оптимизации, обладающие свойством многоэкстремальности, т. е. наличием большого числа решений, на которых целевая функция достигает значений, близких к оптимальному, причем эти решения являются продолжениями таких ветвей, которые отстоят "далеко" друг от друга в любом дереве частичных решений. В таких случаях метод ветвей и границ становится неэффективным. Поэтому оказывается актуальным создание "недревовидной" техники разбиения (или покрытия), более компактно чем любое дерево частичных решений представляющей все множество решений.

Примером многоэкстремальной задачи является NP-полная квадратичная задача о назначениях. Оптимальное назначение здесь в общем случае удается найти лишь тогда, когда параметр, определяющий задачу, принимает очень небольшие значения (до 20). Многие практические задачи такие как некоторые задачи транспортной логистики или задача проектирования микросхем сводятся к квадратичной задаче о назначениях. В связи с этим в настоящее время остается актуальным построение эффективных алгоритмов для таких задач, как квадратичная задача о назначениях.

Цель работы. Целью диссертационной работы является

- построение общей схемы метода плетей и границ метода поиска оптимума в задачах дискретной оптимизации;

- определение способов разбиения множества всех решений и способа оценивания функционала в рамках построенного метода для квадратичной задачи о назначениях;

- разработка нового алгоритма поиска оптимума в этой задаче.

Методы исследований. Формализация метода плетей и границ построена на основе интерпретации формул исчисления высказываний. При доказательстве теорем и обосновании способов разбиения множества решений и оценивания плетей использованы методы теории множеств, комбинаторики, теории графов. Проведены численные эксперименты на компьютере.

Научная новизна. Построена и обоснована общая схема метода нахождения оптимума в задачах дискретной оптимизации - метода плетей и границ. Формализовано правило подстановки, которое позволяет получать специальные наборы частичных решений плети. Доказана теорема о полноте набора плетей в задаче дискретной оптимизации, которая гарантирует, что набор плотей, построенный по правилу подстановки, покрывает все множество решений задачи.

Метод плетей и границ применен для квадратичной задачи о назначениях. Для этой задачи получены:

- методы формирования плетей, которые "легко" оцениваются;

- способы оценивания плетей;

- способы формирования полного набора плетей;

- алгоритм нахождения оптимального назначения, параметрами которого являются интерпретируемые невыполнимые формулы.

Кроме того, в результате численных экспериментов выбраны формулы, использование которых в алгоритме дает наибольшую эффективность по времени.

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

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

Апробация работы. Полученные результаты обсуждались на семинарах кафедры исследования операций и докладывались на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск. 2004).

Публикации. Основные результаты диссертации опубликованы в работах [1-2].

Структура и объем работы. Диссертация объемом 101 страница

состоит из введения, четырех глав, разбитых на параграфы, заключения и списка литературы, содержащего 57 наименований.

Содержание диссертации

Во введении обосновывается актуальность выбранной темы исследования, дается обзор литературы, формулируются основные цели и задачи работы и приводится краткое содержание диссертции.

В первой главе даются основные определения, описываются предложенные ранее структуры, используемые в методе плетей и границ. В § 1 определяется задача дискретной оптимизации. Под задачей дискретной оптимизации в самом общем виде понимается следующая задача. Дано конечное множество Q, задан функционал f : Q R. Требуется найти такой элемент а* £ Q, который минимизирует функционал /. Далее множество Q рассматривается в виде

прямого произведения заданных конечных множеств, т. е.

<? = ]][*''

где М - конечное множество индексов, и i £ М, - попарно -непересекающиеся конечные множества.

При таком представлении Q и заданном функционале общая задача дискретной оптимизации переписывается в виде

(1)

Множество Q = Пгел/ называется множеством решений. Любой вектор q = q[M] £ Q называется решением задачи (1), а решение q*, для которого

f(q*)=mm{f(q),q€Q}.

называется оптимальным решением.. Задача дискретной оптимизации решена, если найдено хотя бы одно оптимальное решение q* и определено значение функционала

Определение 1. Пусть фиксировано множехт,во I С М. Вектор <?[/] £ называется частичным решением, арешение д[М],для

которогод[/] = <5[/], расширением частичного решения 5[1].

Определение 2. Множество всех расширений частичного решения 5 называется регионом 5 и обозначается й(<5)

Определение 3. Регион Л(6) частичного решения 8 называется закрытым, если либо а)известио, чт,о в нем нет, оптимального решения, либо б)в нем определено некоторое локальное оптимальное решение, то есть такое решение дд, для которого /(<?д) = тт{/(д), q £ Л}. Частичное решение назовем закрытым, если закрыт его регион.

Определение 4. Произвольный конечный набор частичных решений называется блоком. Регион блока б = {¿1, <$2> • • • > определяется как объединение регионов частичных решений, входящих в блок, т.е.

Блок назовем закрытым, если закрыт, его регион.

Определение 5. Блок называется полным, если его регион совпадает с множеством решений Q. (В эт,ом случае набор регионов частичных решений, входящих в блок, образует покрытие множества Ц.)

Если некоторый блок оказывается полным и закрытым, то задача (1) решена - оптимальное решение определится как минимум из всех локальных оптимальных решений. Полнота блока гарантирует, что это будет оптимальное решение во всем множестве решений Q.

В §2 и §3 изложено формальной описание замкнутых диаграмм, введенных в работах Г. В. Давыдова и И. М. Давыдовой. Приведем ключевые определения.

Определение 6. Пусть SPS2 два конечных непустых семейства непустых конечных подмножеств некоторого конечного множества -алфавита А. Пара И — (¿^^г) называется диаграммой.

Если возникает необходимость выписать диаграмму явно, то будем записывать каждое множество семейств S¡, S2 в виде столбца.

Определение 7. Конечное множество, имеющее непустое пересечение с каждым множеством семейства S1 (соответственно S2), называется путем в S1 (соответственно S2). Путь, любое собственное подмножество которого не является путем, будем называть минимальным путем.

Определение 8. Диаграмма называется замкнутой, если каждый путь в семействе Б\ содержит некоторое множество семейства 5г-

Определение 9. Замкнутая диаграмма (¿х^) называется минимально замкнутой, если удаление хотя бы одного мноокества из 5г нарушает ее замкнутость.

Замкнутые диаграммы являются интерпретацией невыполнимых формул исчисления высказываний и позволяют строить так называемые недревовидные наборы частичных решений: для того, чтобы представить каждый элемент этого покрытия в виде объединения множеств, соответствующих ветвям в дереве частичных решений, требуется построить дерево, в котором ветвей больше, чем элементов в недревовидном покрытии.

В §4 показана связь замкнутых диаграмм с задачей дискретной оптимизации. При этом и частичное решение 6, и решение q рассматриваются как множества компонент соответствующих векторов ¿[7] и Этот

переход оправдан тем, что множества . определяющие задачу

дискретнрой оптимизации, попарно не пересекаются. Верна следующая теорема:

Теорема 1. Пусть 5х = {Д | г Е М} - семейство множеств, определяющих задачу (1). Тогда

1. Если 5г блок, то 8г полный блок -;=>• (б1! |5г) замкнутая диаграмма.

2. Если (5х|5г) - минимально замкнутая диаграмма, то ¿2 - полный блок.

В главе 2 на основании замкнутых диаграмм предложена и обоснована технология, которая позволяет строить плети - наборы частичных решений, полученные путем комбинирования замкнутых диаграмм.

В §1 даны определения плети (набора плетей), региона плети (набора плетей), его закрытости и полноты.

Под плетью будем понимать произвольный конечный набор блоков

задачи (1).

Для определения региона плети Ь рассмотрим прямое произведение блоков П(£) = ГЬ'е{1 .V} Ф плети Каждому элементу 5 = (¿х,..., <5дг) е П(£) сопоставим множество — и^б,-.

Определение 10. Произведением плету L = {G,, г € {1 N}} tin зовем (семейство мНоЖертв: П} и будем обозначать S(L)

Определение 11. Множес тво ,s(<5), 5 £ П(£), называется непротиворечивым, если \Bt П s(<5)| < 1 для каждого г € М, в противном случае оно называется противоречивым

Определение 12. Блок S*(L) называется очищенным произведением плети L, если он поручен из произведения плети S(L) удаленьем противоречивы! множеств и такиг множеств£ S(L), что существует si € S(L), для которого S\ С ч

Определение 13. Регионом плети L называется регион очищенного

de /

произведения плети, те R{t) = R(S*(L))

Определим понятие региона для конечною набора плстой Н Каж дой плети X £ Я соответствует очищенное произведение плети S"(L) Определим блок D(H) — Ute/z

Определение 14. Регионом побора плетей Нявляется регион блока

def

D(H), т с Я(Н) =' R{D(H))

Закрытость и потно га плети (набора плетей) определяются через закрытость и пошоту ее (его) региона соответственно

В §2 сформулировано правило подстановги, которое позволяет по лучать наборы плетей путем подстановки одних замкнутых диаграмм в другие

Правило подстановки. Пусть (Sj\Dj), j £ {1 п}, диаграммы, каждое семейство Dj является блоком в (1) и предегавимо в виде

т е задано покрытие семей-

ства D3

1 Сопоставим каждому семейству Dp, г Е I3, j £ {1 п}, уникальное имя a[D}l)

2 Образуем множество имен Х3 — {a(Dj,), г £ Ij} и диаграмму это где X = {Xi, произвольное семейство множеств имен

3 Каждому множеству

сопоставим семейство

Далее диаграмму (Х|У) будем называть шаблоном и будем говорить, что набор семейств {Ь(у), у 6 У} получен подстановкой диаграмм 1 € {1..п} в шаблон (Х|У). Диаграммы ] 6 {1..гг}

будем называть подставляемыми. Если (Х|У) - замкнутая диаграмма, то шаблон (Х|У) будем называть замкнутым.

Определение 15. Пусть набор плетей {Ь(у), у £ У} получен подстановкой диаграмм (5;|Д,), ] £ {1..тг} в шаблон (Х\У). Множество 7Т называется путем в наборе плетей {Ь(у), у € У}, если существует такой путь р в семействе У, что тг — где жг> - путь в семействе Б.

Определение 16. Набор плетей, полученный подстановкой диаграмм (5,1.0,), ] £ {1..п} в шаблон ^Х!У), называется замкнутым, если лю-бойпутьвэтомнаборесодержитнекотороемножествоиз семейства

Получим условие замкнтости набора плетей.

Лемма 1. Если (5;€ {1..п} замкнутыедиаграммы, и (X|У) замкнутый шаблон, то набор плетей.Н — Щу), у £ У)полученный подстановкой диаграмм 3 £ {1..п} в шаблон (Х/У), замкнут.

В §3 доказана теорема о полноте набора плетей в задаче дискретной оптимизации и ид ее основании представлен общий метод плетей и границ.

Теорема 2. Пусть В = {В^ ] 6 М} семейство множеств, определяющих задачу дискретной оптимизации (1), $ ЕМ блоки в этой задаче; и пусть набор плетей II = {Ь{у)> У € У} получен подстановкой диаграмм (Б|03), ] 6 М, в шаблон {Х\У).

Тогда, если(В\Б] £ М, - замкнутые диаграммы и (Х\У) - замкнутый шаблон, то набор плетей Н полон в данной задаче.

Из теоремы 2 следует, что полные наборы плетей мы можем порождать, используя различные замкнутые диаграммы в качестве шаблонов и подставляемых диаграмм правила подстановки. Сами же замкнутые диаграммы мы можем получать из известных классов невыполнимых формул, например, формул Цейтина и Хорна, как это сделано для квадратичной задачи о назначениях.

На основании полученных результатов обший метод плетей и границ записывается следующим образом.

Начальные установки: положим

Стандартный шаг:

• Получаем полный набор плетей Н подстановкой замкнутых диаграмм вида

полные блоки, в некоторый замкнутый

шаблон.

Если все плети в наборе Н закрыты, то метод заканчивает работу, выбирая оптимальное решение среди всех локально оптимальных.

Для каждой незакрытой плети Ь € Н делаем следующее:

1. Полагаем где каждое

В[ = (дП В{), где Я(Ь) - регион плети Ь.

2. Переходим к •.

В главе 3 определяется квадратичная задача о назначениях в виде (1), предлагаются шаблоны и подставляемые диаграммы для правила подстановки, вводятся способы оценивания плетей, методы получения закрытых плетей.

В §1 представлена постановка задачи. Определим множество индексов М = {1..п} и множества — {{у}, j € М}, г £ М. Пусть V, С - целочисленные неотрицательные матрицы размера Введем функционал

Квадратичная задача о назначениях состоит в минимизации функционала И на множестве — ХТ1ед/ Д', Т.е.

В §2 предложены замкнутые диаграммы, являющиеся интерпретациями известных невыполнимых формул Хорна и Цейтина и получившие

название Хорновских и Цейтиновских диаграмм соответственно, которые используются в качестве шаблонов правила подстановки при нахождение оптимума в квадратичной задаче о назначениях методом плетей и границ.

Будем использовать следующие Хорновские диаграммы размера п:

и Цейтиновские диаграммы, соответствующие заряженному графу, представленному на рис.1

Рис. 1. Заряженный граф для получения формулы Цейтина, используемой при построении Цейтиновской диаграммы. Здесь а = [п/2].

* дуга, помеченная п, есть только при четном п. При нечетном п граф отличается от изображенного только отсутствием этой дуги.

В качестве подставляемых диаграмм использовались диаграммы е М, где каждое ДГ = {{Ь}| Ь £ В;}, г £ М. Было получено, что эти диаграммы также являются Цейтиновскими диаграммами.

В §3 определены условия закрытости плети в квадратичной задаче о назначениях, предложен метод оценивания блоков и плетей, базирующийся на решении линейной задачи о назначениях. Для всей задачи и частичного решения предложенная нижняя оценка совпадает с известной оценкой Гилмора-Лоулера.

Определение 17. Плеть называется допустимой, если в ее регионе существует такое решение q0, чт,о Р^) < со. В противном случае плеть называется недопустимой.

Выявлено, что плеть L в квадратичной задаче о назначениях закрыта, если либо а) для L известен локальный оптимум, либо б) L недопустимая плеть, либо в) нижняя оценка для L больше рекорда наименьшего из известных на данный момент значений функционала F.

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

В §5 предложены способы формирования закрытых плетей.

Один из способов - получать недопустимые плети, - базируется на переформулировке классической теоремы Холла о различных представителях в виде критерия недопустимости плетей.

Второй способ получение плетей с известным локальным оптимумом. Этот способ построен на решении оценочной задачи. Задавая специальное разбиение блоков в подставляемых диаграммах и используя определенные шаблоны, мы можем получать плети с известным локальным оптимумом, а также недопустимые плети.

Предложена модификация последнего способа, связанная с решением дополнительной линейной задачи о назначениях, но не на минимум, как в оценочной задаче, а на максимум. Эксперименты показали, что несмотря на дополнительные затраты, такое оценивание часто дает повышение эффективности.

В главе 4 предлагается алгоритмическая реализация метода плетей и границ в квадратичной задаче о назначениях. Проводится анализ параметров алгоритма, приводятся результаты численных экспериментов.

В §1 изложена общая схема алгоритма.

Алгоритм начинает свою работу с вычисления нижней оценки для всей задачи. Вместе с оценкой мы получаем некоторый рекорд для квадратичной задачи о назначениях.

После этого начинается циклический процесс, итерацию которого можно записать так:

• Получение полного набора плетей для задачи. Построение этого набора, осуществляется таким образом, что некоторые из плетей являются заведомо закрытыми.

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

В §2 четвертой главы описаны результаты численных экспериментов, которые были проведены с целью проверки корректности и выявления наилучших значений параметров алгоритма.

Эксперименты позволили сделать следующие выводы.

1. Ключевую роль в алгоритме, как и в методе ветвей и границ, играет способ построения нижней оценки.

2. Существуют шаблоны, применение которых значительно сокращает перебор: алгоритм работает наиболее эффективно при комбинировании Цейтиновских и Хорновских диаграмм в качестве шаблонов правила подстановки, а также при использовании только Хорнов-ских диаграмм.

3. Во всех примерах, взятых из электронных библиотек (см. таблицу 1), алгоритмом были получены глобальные оптимумы, что позволяет сделать вывод о корректности предложенной реализации.

Таблица 1. Решение задач из электронных библиотек (http://www.seas.upenn.edu/qaplib/). Name наименование задачи в библиотеке (число в наименовании - это размер задачи), Opt оптимальное решение, Perm перестановка, на которой достигается минимум, Time - время работы программы на компьютере Pentium 4, 3 GHz, RAM 256Mb в секундах.

Name Opt Perm Time

chrl2b 9742 3,8,6,7,1,10,2.12,9,4,5,11 2.3

chrl5a 9896 14,8,13,9,1,10,11,3,15,2,6,5,4,7,12 1800

chrl8a 11098 9,18,1,4,8,3,12,11,15,7,10,6,2,14,17,16,13,5 36120

ПраЗОЬ 476581 1, 2, ...,30 0

]ipa40b 476581 1, 2, ...,40 0

lipa60b 2520135 1, 2, ...,60 0

scrl5 51140 5,8,7,6,12,10,2,4,15,14,3,9,11,13,1 25200

drel5 306 6,8,1,9,11,3,4,15,5,12,10,13,14,2,7 900

drel8 332 15.2,8,18,16,3,9,12,4,5,14,6,17,7,10,1,11,13 5520

clre21 356 21,14,16,4,3,11,19,17,6,5, 8,18,10,2.15,13,1,12.9,20,7 324120

Работы автора по теме диссертации

1. Мартюшев А. В. Алгоритм решения квадратичной задачи о назначениях методом плетей и границ. Вестник молодых ученых, серия "Прикладная математика и механика", №1, 2004, стр. 64-71

2. Мартюшев А. В. Алгоритм решения квадратичной задачи о назначениях методом плетей и границ. Российская конференция "Дискретный анализ и исследование операций": материалы конференции (Новосибирск, 28 июня - 2 июля 2004). - Новосибирск: издательство Института математики, 2004. - 230 с, стр. 168

Подписано в печать 29.04.2005 г. Формат бумаги 60X84 1/16.

Бумага офсетная. Печать ризографическая. Объем 1 усл. п. л. Тираж 100 экз. Заказ 3571.

Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ

с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский

пр., 26.

í• i'Í^Í»«'.! « ;

I ЛЙА

t Jfxt&vVtíAÜ i

V /

03 И ЮН 2005

Основные результаты диссертационной работы были доложены на Всероссийской конференции "Дискретный анализ и исследование операций", проходившей в Новосибирске летом 2004 года, и опубликованы в [44, 56].

Заключение.

Диссертационная работа посвящена развитию методов поиска оптимума в ИР-трудных задачах дискретной оптимизации. Этот поиск, как правило, осуществляется посредством методов неявного перебора. В традиционном методе ветвей и границ разбиение множества ф всех решений исследуемой задачи определяется деревом частичных решений - поддеревом полного дерева, и к одному множеству такого разбиения относятся все элементы множества ф, являющиеся ветвями полного дерева решений и продолжениями ровно одной ветви в дереве частичных решений. *

Предложенная в работе технология (метод плетей и границ) является обобщением метода ветвей и границ. Она позволяет, во-первых, строить так называемые недревовидные покрытия: для того, чтобы представить каждый элемент этого покрытия в виде объединения множеств, соответствующих ветвям в дереве частичных решений, требуется построить дерево, в котором ветвей больше, чем элементов в недревовидном покрытии.

Во-вторых, строится такое покрытие, в котором удается оценить сразу не одно частичное решение, как в методе ветвей и границ, а целый специально сконструированный набор частичных решений - плеть.

Основой для формализации метода плетей и границ служат следующие результаты.

1. В работе сформулировано и обосновано правило подстановки, которое позволяет получать наборы плетей, используя замкнутые диаграммы, являющиеся интерпретациями невыполнимых логических формул.

2. Сформулирована и доказана теорема о полноте набора плетей в задаче дискретной оптимизации, которая гарантирует, что набор плетей, построенный по правилу подстановки, покрывает все множество решений задачи.

3. Описан метод плетей и границ в общем виде.

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

В отличие от метода ветвей и границ параметрами в методе плетей и границ являются не только выбор способа оценивания и тактики ветвления, но и способ формирования недревовидных покрытий. Для квадратичной задачи о назначениях найдены реализации соответствующих параметров, а именно:

1. Предложены способы формирования полного набора плетей на основе специальных невыполнимых логических формул (Цейтина, Хорна, пт-циклов). Получены и обоснованы методы построения плетей с известным локальным оптимумом.

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

Представлена алгоритмическая реализация метода плетей и границ для квадратичной задачи о назначениях. Проведены численные эксперименты с целью проверки корректности и выявления наилучших значений параметров алгоритма. Результаты экспериментов позволяют сделать следующие выводы:

• Ключевую роль в представленной реализации играет построение нижней оценки.

• Существуют замкнутые шаблоны, применение которых значительно сокращает перебор.

• Алгоритм позволяет решать квадратичные задачи о назначениях размера до 20. *

Предложенный метод плетей и границ может быть использован для любых задач дискретной оптимизации. При этом достаточно, используя семантику задачи, определить способ оценивания.

Алгоритмическая реализация метода может быть использована при составлении компьютерных программ для нахождения оптимального решения в конкретных задачах о назначениях, например, проектировании клиник и бизнес-центров, расположении клавиш на панели управления некоторого устройства и других.

1. Романовский И. В. Дискретный анализ. СПб.: Невский Диалект; БХВ -Петербург, 2003. 320 с.:ил.

2. Давыдов Г. В., Давыдова И. М. Метод плетей и границ. Исследование операций и статистическое моделирование. Издательство Санкт-Петербургского Университета. 1994. Вып. 6. с.14-30

3. Давыдов Г. В. Синтез метода резолюций с обратным методом. Записки научных семинаров ЛОМИ 20(1971), с. 24-35.

4. Давыдов Г. В., Давыдова И. М. Двойственные алгоритмы в дискретной оптимизации. Вопросы кибернетики. 1987. Вып. 131. с.90-117.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.

6. Sahni S.,Gonzalez Т. P-complete Approximation Problems. Journal of the ACM 23, 1976, 555-565.

7. Koopmans Т. C., Beckmann M. Assignment Problems and the Location of Economic Activities. Econometrica, vol.25, No. 1, 1957, pp.53-768| Clay Mathematics Institute. Millennium Problems.http://www.claymath.org/millennium/PvsNP/

8. Burkard R., Pardalos P., Pitsoulis L.,Cela E. The Quadratic Assignment Problem. Optimirung und Kontrolle, Nr. 126, 1998.

9. Cela E. The quadratic assignment problem: special cases and relatives. PhD thesis, Graz University of Technology, Graz, Austria, 1995.

10. Burkard R., Cela E. Linear Assignment Problems and Extensions. Optimirung und Kontrolle, Nr.127, 1998.

11. Elshafei A. N. Hospital Layout as a Quadratic Assignment Problem. Operations Research Quarterly 28, 1977, 167-179.

12. Maniezzo V., Colorni A. The Ant System Applied to the Quadratic Assignment Problem. Tech. Rep. IRIDIA/94-28, Universite Libre de Bruxelles, Belgium, 1994.

13. Burkard R. E., Offerman J. Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme. Z. Operations Research 21, 1977, B121-B123.

14. Eiselt H. A.,Laporte G. A Combinatorial Optimization Problem Arising in Dartboard Design. The Journal of the Operational Research Society 42,1991, 113-118.

15. Commander C. W., Pardalos P. M. A Survey of the Quadratic Assignment Problem, with Applications. Submitted to The Morehead Electronic Journal of Applicable Mathematics, 2003.

16. Carlson R. C., Nemhauser G. L. Scheduling to minimize cost. Operations Research 14, 1966, 52-58.

17. Brixius N. W., Anstreicher K. M. The Steinberg wiring problem. Working Paper, The University of Iowa, October 2001.

18. Geoffrion A. M., Graves G. W. Scheduling Parallel Production Lines with Changeover Costs: Practical Applications of a Quadratic Assignment/LP Approach. Operations Research 24, 1976, 595-610.

19. Edwards C. S. The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem. Proceedings of the 77 -th Combinatorial Programming Conference(CP77), 1977, 55-86.

20. Edwards C. S. A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem. Mathematical Programming Study 13, 1980, 35-52.

21. Lawler E. L. The Quadratic Assignment Problem. Management Science 9, 1963, 586-599.

22. Gilmore P. C. Optimal and Suboptimalf Algorithms for the Quadratic Assignment Problem. SIAM Journal on Applied Mathematics 10, 1962, SOS-SIS.

23. Hadley S. W., Rendí F., Wolkowicz H. A New Lower Bound via Projection for the Quadratic Assignment Problem. Mathematics of Operations Research 17, 1993, 727-739.

24. Anstreicher K. M., Brixius N. W., Linderoth J.,Goux J. -P. Solving Large Quadratic Assignment Problems on Computational Grids. Mathematical Programing, Series B 91, 2002, 563-588.

25. Nugent ,Vollman T. E., Ruml J. An experimental comparison of techniques for the assignment of facilities to locations. Operations Research, 1968: 150-173.

26. Armour G. C.,Buffa E. S. Heuristic Algorithm and Simulation Approach to Relative Location of Facilities. Management Science 9, 1963, 294-309.

27. Aarts E.,Lenstra J. K. Local Search in Combinatorial OptimizationJohn Wiley & Sons, 1997.

28. Glover F. Tabu Search Part 2. ORSA Journal on Computing2, no. 1, 1989, 4-32.

29. Glover F. Tabu Search Part 1. ORSA Journal on Computing 1, 1989 no. 3, 190-206.

30. Burkard R. E., Rendl F. A. Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems. European Journal of Operational Research 17, 1983, 169-174.

31. Cerny V. Thermodynamical Approach to the Traveling Salesman Problem: An Effcient Simulation Algorithm. Journal of Optimization Theory and Applications 45, 1985, 41-51.

32. Tate D., Smith A. A genetic approach to the quadratic assignment problem. Computers and Operations Reseach, vol. 22, no.l, 1995, 73-83.

33. Gambardella L. M., Taillard E., Dorigo M. Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, 50, 1999, 167-176.

34. Pitsoulis L. A Sparse GRASP for Solving the Quadratic Assignment Problem. M.Eng. thesis, The University of Florida, 1994.

35. Solving QAPLIB, a selected DPLP dataset, and other difficult instances with GATS, http://acrl.cs.unb.ca/research/gats/

36. QAPLIB Home Page, http://www.seas.upenn.edu/qaplib/ (Last update: 10 March 2005)

37. Haken A. Intractability of resolution. Theoretical Computer Science, 39, 1985, 297-308.

38. Цейтин F. С. О сложности вывода в исчислении высказываний. Записки научных семинаров ЛОМИ, 8, "Наука", Л., 1968, 234-259.

39. Kowalski R. A. Logic for Problem Solving. Elsevier-North Holland, 1979, 287 p.

40. Мартюшев А. В. Алгоритм решения квадратичной задачи о назначениях методом плетей и границ. Вестник молодых ученых, серия "Прикладная математика и механика", №1, 2004.

41. Robinson J. A. A machine-oriented logic based on resolution priciple. Journal of the ACM, pages 23-41, 1965.

42. Jonker R., Volgenant A. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 1987, 325-340.

43. Дистель R Теория графов. Пер. с англ. Новосибирск: Изд-во Ин-та математики, 2002. - 336 с.

44. Берж К. Теория графов и ее применения. Издательство Иностранной Литературы, Москва, 1962.

45. Berge С. Graphes et hypergraphes. Dunod(Paris, 1970).

46. Hooker J. Logic-based methods for optimization: combining optimization and constraint satisfaction. A Wiley-Interscience Publication, John Wiley Sz Sons, Inc. 2000.

47. Hopcroft J., Karp R. M. An n5/2 algorithm for maximum Matchings in bipartite graphs. SIAM J. Comput., 1973, 2, s. 225-231.

48. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск. Пер. с англ. М.: Мир, 1978.

49. Maus A. Sorting by generating the sorting permutation, and the effect of caching on sorting. Norsk informatikkonferanse, Oslo, 20-22 Nov, 2000.

50. Липский В. Комбинаторика для программистов. Пер. с польск.- М.: Мир, 1988. 213 с. ил.

51. Hall Ph. On representatives of subsets. J. London Math. Soc., 1935, 10, s. 26-30.

52. Eric Taillard home page. Quadratic assignment instances. http://ina.eivd.ch/collaborateurs/etd/problemes.dir/qap.dir/qap.html