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

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

ШАНГПН Роман Эдуардович

РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ГРАФА

Специальность: 05.13.17 - теоретические основы информатики

9 СЕН 2015

Автореферат

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

Челябинск - 2015

005562024

Работа выполнена на кафедре экономико-математических методов и статистики ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

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

профессор Панюков Анатолий Васильевич, ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

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

профессор Кипнис Михаил Мордковнч, ФГБОУ ВПО «Челябинский государственный педагогический университет»

кандидат физико-математических наук, доцент Пролубников Александр Вячеславович, ФГБОУ ВПО «Омский государственный университет им. Ф. М. Достоевского»

Ведущая организация: Федеральное государственное бюджетное

учреждение науки «Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук»

Защита состоится 14 октября 2015 г. в 12:00 часов на заседании диссертационного совета Д 212.298.18 при ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет) по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета и на сайте:

http:. susu.ru ru/dissertation /d-21229818/shangin-roman-eduardovicli

Автореферат разослан « » 2015 г.

Ученый секретарь диссертационного совета к.ф.-м.н.

п( , п

У l'jiiuti^P М- Л. Цымблер

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

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

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

Степень разработанности темы. Класс задач размещения интересен как с практической, так и с теоретической точки зрения, о чем свидетельствует большое количество работ, посвященных данным задачам. Среди них в первую очередь стоит отметить работы Забудского Г.Г., Кочетова Ю.А., Пашокова A.B., Еремеева A.B., Береснева В.Д., Гпмади Э.Х., Дементьева В.Т.. Гермепера Ю.Б.. Шамардина Ю.В.. Колоколоиа A.A., Агеева A.A., Антипина A.C., Хамисова О.В., и др. На сегодняшний день область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования новых постановок задач, развиваются точные и приближенные методы их решения, выделяются полиномиально разрешимые случаи.

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

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

1. Исследовать свойства дискретной задачи Вебера в графовой постановке.

2. Найти новые подклассы задачи, разрешимые за полиномиальное время.

3. Найти новые подклассы задачи, разрешимые с гарантированной оценкой точности за полиномиальное время.

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

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

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

1. Доказано, что ДЗВ полиномиально разрешима при фиксированном к, когда размещаемый граф представляет собой /¿-дерево либо /с-цепь. Разработаны новые эффективные алгоритмы точного решения ДЗВ на данных классах графов.

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

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

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

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

практических задач, так и в рамках преподавания курсов «Исследование операции» и «Теория принятия решении».

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

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

Апробация результатов исследования. Все результаты диссертации прошли апробацию на следующих мероприятиях:

— Всероссийская конференция по математическим методам и статистике,

Москва, 2011.

— Всероссийская конференция «Статистика. Моделирование. Оптимизация»,

Челябинск, 2011.

— V Всероссийская конференция «Проблемы оптимизации и экономические

приложения», Омск, 2012.

— XIII Всероссийская конференция молодых ученых по математическому

моделированию и информационным технологиям, Новосибирск. 2012.

— XIV Всероссийский Симпозиум по прикладной и промышленной матема-

тике, Сочи-Вардане. 2012.

— Международная конференция «Дискретная оптимизация и исследование

операций», Новосибирск, 2013.

— Международная конференция «Информационные технологии интеллекту-

альной поддержки принятия решений». Уфа. 2013.

— XII Всероссийская конференция «Компьютерная безопасность и крипто-

графия», Томск, 2013.

— Международная конференция «The 15tli International Workshop on

Computer Science and Information Technologies», Уфа, 2013.

— II Международная конференция «Высокопроизводительные вычисления -

математические модели и алгоритмы». Калининград, 2013.

- XIII Всероссийская конференция «Компьютерная безопасность и кршио

графия», Томск, 2014.

- Международная конференция «The Second International Conférence on

Information Technology and Quantitative Management», Москва, 2014.

- XII Всероссийское совещание по проблемам управления, Москва, 2014.

- XVI Международная школа-семинар «Методы оптимизации и их приложе-

ния», Пркутск-Ольхон, 2014.

- XV Всероссийская конференция «Математическое программирование и

приложения», Екатеринбург, 2015.

Публикации. Основные результаты диссертации опубликованы в 6 научных статьях [1-6] в журналах, входящих в перечень ВАК, в 10 статьях [7-16] в различных журналах, сборниках и материалах конференций. Общее число публикаций — 16. Зарегистрирована программа для ЭВМ [17]. Во всех работах [1-16] научному руководителю А. В. Панюкову принадлежит постановка задачи и общее руководство, Р. Э. Шангнну - все полученные результаты.

Объем и структура диссертации. Диссертация состоит из введения, обзора литературы, четырех глав, заключения и списка литературы (141 наименование). Объем диссертации - 116 страниц.

2 Краткое содержание работы

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

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

Постановка ДЗВ следующая. Пусть G - простой взвешенный связный граф, V(G) - множество вершин графа G, соответствующее размещаемым объектам. E{G) - множество ребер графа G, определяющее связи между размещаемыми объектами. Пусть Р - конечное множество позиций, предназначенных для размещения вершин графа G. В дальнейшем будем полагать |V| = |Р| = п, что не ограничивает общности изложения. Размещением вершин графа G будем называть отображение 7Г : l7(G) —» Р,

g

полагая, что вершина i 6 размещается в позицию тт(г') ё Р, причем

в одну позицию возможно разместить несколько вершин. Множество всех отображении множества вершин К((7) в множество позиций Р обозначим

Заданными являются: вес ребра w(i,j) > 0 для [i,j] G E(G): [расстояние d{t, и) > 0 между позициями t, и G Р. определенное в некоторой метрике; стоимость размещения b(i, t) > 0 вершины г G V(G) в позиции / G Р; стоимость связи с([г, j],t,u) между вершинами i,j G V(G), размещенными в позициях t,u G Р. причем полагаем с([г, j], t, и) = w(i,j) ■ d(t, и). Необходимо разместить вершины графа G в позициях Р таким образом, чтобы суммарная стоимость размещения вершин и ребер графа G была минимальной:

F(G,n)= Y, c(M,7r(¿),7r(j))+ Е bM(0)-nnin. (1)

Такая задача размещения графа G на множестве Р с критерием F в дальнейшем будет обозначаться тройкой {G.P.F).

Известно, что задача {G.P,F} является NP-трудной (Salmi S., Gonzalez T., 1976). В зарубежной литературе она носит названия quadratic semi-assignment problem и task assignment problem. Для подклассов задачи, когда размещаемый граф является деревом (Bokhari S. H., 1981) и последовательно-параллельным графом (Malucelli F., 199G) известны точные полиномиальные алгоритмы. Также случай, когда |Р| = 2, разрешим за полиномиальное время (Stone H. S., 1977). Предложены эффективные алгоритмы для вычисления нижней границы оптимума задачи [Malucelli F., PretolaniD.. 1995|. Для ДЗВ в общем виде, впрочем, так же как и для квадратичной задачи о назначениях в общей постановке, доказана ее неаппрокспмнруемость (Salmi S.. Gonzalez T., 1976). Несмотря на это, для частного случая, когда

где а = const, найдена полиномиальная приближенная схема (Fernandez de la Vega \Y., Lamari M.. 2003).

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

Во второй главе предлагаются точные полиномиальные алгоритмы решения ДЗВ для графов специального вида. Для полноты изложения, приведем известные определения fr-дерева (RoseD. Л., 1973) и его частного случая - fr-пепи (Takahaslii A., Ueno S., 1995).

через И = {тг : V{G) -> Р}.

[;,j]e£(C)

Определение 1. Граф называется к-деревом, e&iu его построение возможно осуществить рекурсивно по правилам: клика размера к + 1 есть к-дерево; к-дерево с i + 1 вершинами получается из к-дерева с г вершинами добавлением в него новой вершины j и к ребер так. что вершина j стала смежной со всеми вершинами некоторой к-клики (клики размера к). Определение 2. Граф С называется к-цепью, если выполняются уааовия: С - полный граф, когда число вершин С равно k+ I; С - к-дерево, имеющее ровно две вершины степени к, когда число вершин С больше k+ 1.

В п. 2.1 рассматривается задача {T,P,F}, где Т есть /¿-дерево. Предлагается точный алгоритм Ат решения данной задачи, основанный на технике динамического программирования (ДП) но дереву декомпозиции.

Идея алгоритма Ат заключается в следующем. Строится дерево декомпозиции Т = {M.,W), с множеством узлов ЛЛ = К U S, где К есть множество (/¿+1)-клик графа Т, множество S = {XnZ : X, Z £ К, \XCiZ\ = к}, и множеством ребер W = {[А',У] : X £ К, Y £ S, \Х П Y\ = к}. Узел А' £ К будем называть «узлом-кликой», а узел X £ S - «узлом-сепараторомВыбирается узел А'у £ A4 в качестве корня дерева Т. Узлы дерева Т нумеруются в порядке убывания, где корневой узел имеет номер N = \М\. Пусть Dj - множество узлов, являющихся прямыми потомками узла Xj. Пусть Т/ - подграф /е-дерева Т, индуцированный множеством вершин Xj U (Ujc/5 Xj), где Di - множество всех потомков узла А"-,.

Пусть П(А',-) = {я-; : А',- —> Р}. Будем писать, что тгМ ttj, если для размещений тг, и ttj справедливо |7г,-Птт^-| = к. Обозначим Т(г, тг;) - граф Ti, в котором размещение вершин его клики А',- в множестве Р равно 7Г; £ П(А'г).

На прямом ходе работа алгоритма A-j- разбивается на Аг шагов. Пусть П(А',-) множество состояний процесса ДП на этапе г. На каждом шаге i = 1,2,..., N для всех состояний тг,- 6 П(А',-) рекуррентно вычисляется оптимальная стоимость размещения графа Т(г,тг^) но функции Беллмана /¿(тг,), имеющей следующую специфику: если АГ,- - узел-клика, то

/,-(тг,-) = В(тг,)+С(тг,) + Y, Е (B(vj)+C(nj))-, (2)

jSD.-.zjXTV, jSD.iTTjix«,

если X; - узе.т-сепаратор, то

/,(min Шъ)} ~ (В(тгг) + С(тг,-)) • (| Д-| - 1), (3)

где B(-j) - стоимость размещения тт; вершин клики X, и С(7Гг) - стоимость размещения ребер подграфа, индуцированного кликой Xj, когда размещение вершин А',- равно 7Г,-. Для каждого состояния тг,- определяется множество Д/(тг,-): если X, - узел-клика, то Л/(тг,-) = {тгj : j £ Dt, ~j txi тг,}; если Xi - узел-сепаратор, то Л/(-г) = {тг] : j £ Dh тг* = argтт^щл-;):*^ fj(*j)}-

На обратном ходе алгоритм At, двигаясь от последнего шага N к шагу 1, используя хранимые в памяти значения множеств AI, рекуррентно формирует оптимальное размещение вершин /¿-дерева Т. Доказана

Теорема 2.1. Алгоритм Aj за вре.ня 0(тгк+3) находит тонное решение задачи {T,P,F), где Т есть к-дерево. Оценка требуемой алгоритмом оперативной памяти равна 0(пк~3).

Используя теорему 2.1 удалось установить полиномиальную разрешимость более широкого класса графов, чем класс /¿-деревьев. Сформулирована и доказана

Теорема 2.2. Дискретная задача Вебера полиномиально разрешима за время 0(nk+i) на классе графов, для которых параметр древовидной ширины (treewidth) фиксирован и равен к.

Параметр древовидной ширины хорошо известен в современной теории графов и был предложен в работе (Robertson N., Seymour P.D., 1986).

В п. 2.2 рассматривается задача (С, Р, F), где С есть /с-цепь. Предлагается точный алгоритм Ас решения задачи (С, Р, F), основанный на динамическом программировании.

Идея алгоритма Ас заключается в следующем. На множестве V(C) : \V(C)\ = п вершин к-цепп С задается нумерация, согласно определению 2. В дальнейшем каждую вершину будем отождествлять с присвоенным номером. Пусть К{ — клика размера к с множеством вершин {¿+1, г+2,..., i+k} С V(С) и П(А'г) = {тг, : Ki —> Р} - множество всех отображений вершин клики Л"; в Р, где 7Г; = {TTi(j) : j € А',-}. Обозначим С(г, 7Гг) - подграф графа С, индуцированный вершинами {1,2,..., г + к}, в котором размещение вершин его клики К{ в множестве Р равно тг,- G П(А';). Множество состояний процесса ДП на шаге г будем полагать равным П(А';).

На прямом ходе алгоритма процесс решения задачи разбивается на п — к шагов. На каждом шаге i = 1,2, ...,п — к для всех состояний 7г; е П(А,) рекуррентно вычисляется оптимальная стоимость размещения графа С(г, 7гг) в множестве Р по уравнению Беллмана

Л(тг) = Ь[1+к,щ{г+к))+^2 c([i+k,j],Tri(i+k),iri{j))+

j€K,

+ min {c([i + A-,i]!7ri(i + fr),7rI-_1(0) + /i-i(7rl-_i)}, (4)

тг^еЩЛ',-,)

где выполняется тгг_1 П тг, = к — 1. Определяется функция AI, ставящая в соответствие каждому состоянию тг,- € П(А',) состояние ttJ_1 G n(A',_i), при котором достигается минимум последнего слагаемого в формуле 4, то есть

Л/(7гг) = arg min {с([г + к, г], 7г,-(г + к), (г)) + /¿-1(^-1)} ,

где П 7Г,- = А; — 1.

На последнем шаге п — к алгоритм находит оптимум задачи.

На обратном ходе алгоритм, двигаясь от последнего шага п — к к шагу 1, используя хранимые в памяти значения функции М, рекуррентно формирует оптимальное размещение вершин графа С. Сформулирована и доказана

Теорема 2.3. Алгоритм Ас за время 0(пк+2) находит точное решение задачи (C,P,F), где С есть к-цепь. Оценка требуемой алгоритмом оперативной памяти равна 0(пк).

Отметим, что, благодаря учету специфики задачи, алгоритм Ас имеет существенно лучшие оценки трудоемкости и требуемой памяти, чем более общий алгоритм Aj. Используя теорему 2.3, удалось установить полиномиальную разрешимость исследуемой задачи на классе графов с фиксированным параметром ленточной ширины (bandwidth) графа. Сформулирована и доказана

Теорема 2.4. Дискретная задача Вебера полиномиально разрешима за время 0(пк+2) на классе графов, для которых параметр ленточной ширины фиксирован и равен к.

Параметр ленточной ширины хорошо известен в современной теории графов и был предложен в работе (Chung F. R. К., Seymour P. D., 1989).

В п. 2.3 рассматривается задача (S, Р, F), где S - простой цикл. Предложен алгоритм As поиска точного решения задачи (S,P,F), основанный на ДП, частично использующий идею точного алгоритма для к-цепи. Алгоритм имеет трудоемкость 0(тг4) и оценку требуемой памяти О(п). Стоит заметить, что алгоритм As, благодаря учету специфики задачи, требует существенно меньше памяти, чем известный алгоритм Ф. Малучелли для последовательно-параллельного графа (Malucelli F., 1996), которому необходимо 0{пА) памяти для вычисления оптимального решения.

Третья глава посвящена алгоритмам с оценками точности решения задачи ДЗВ. Рассмотрим задачу (G. Р, F). где G - простой взвешенный граф. Обозначим Я - суграф (остовной подграф) графа G, то есть V(H) = V(G) и Е(Н) С E(G). Обозначим Д(Я, ж) = F(G, ж) - F(H, ж) - стоимость размещения ребер графа G, не вошедших в суграф Я, когда размещение их концевых вершин равно жн-

В п. 3.1 сформулирована и доказана

Теорема 3.1. Если Я - суграф графа G и жн - оптимальное размещение Н в Р, то стоимость решения ж я задачи {G. Р, F) превосходит стоимость оптимального решения же, задачи (G, Р, F) не более чем в г раз, где

, , А(Я.тгя) ...

е = 1 + Т777-г. (5)

F(H, жн)

Инымн словами, оценка £ определяется отношением стоимости размещения ребер графа G, не вошедших в суграф Н, когда размещение их концевых вершин принадлежит тгя, к стоимости оптимального размещения вершин и ребер такого суграфа.

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

Л(Г,тгн) = T,[ij]eE(G)\E(H)w(iJ) • d(nH(i),na(j))

F{T,wH) T,ieV(G)b(^7TH{i)) + J2[ij]eE(H) ■ d(nH(i),wH(j))'

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

Приведем краткое описание приближенного алгоритма АРХ решения задачи (G,P,F). На шаге 1 находится остовное дерево Т максимального веса в графе G, например, с помощью алгоритма Краскала (Kruskal J. В., 1956). На шаге 2 вычисляется оптимальное размещение ят вершин дерева Т в множестве Р, например, с помощью известного алгоритма (Panyukov А. V., PelzwergerВ., 1991). На шаге 3 размещение 7г<з вершин графа G полагается равным itT и оценка точности решения ttq исходной задачи вычисляется по формуле (5).

Доказано, что вычислительная сложность алгоритма АРХ равна 0(п3). Поскольку значение е становится известным только после проведения вычислений алгоритма, то величина г является апостериорной оценкой относительной погрешности алгоритма АРХ. Очевидно, что е ф const и зависит от входных данных индивидуальной задачи. Сформулирована и доказана

Теорема 3.2. Для всех шсдивидуальных задач (G, Р, F} с функциями b, w, d такими, что имеет место неравенство

Y, w(UJ)< Е (7)

[ij}€E(G) ieV(G) 6

алгоритм АРХ является 2-приблилсенным алгоритмом.

Рассмотрим задачу (S,P,F), где S - простой цикл с п вершинами. Сформулированы и доказаны

тах{с/(£, и)}

Теорема 3.3. Для задачи (S,P,F) алгоритм Арх за вре.мя 0(п3) находит приближенное решение, стоимость которого не более чем в 2 раза превосходит оптимум.

Теорема 3.4. Алгоритм АРХ решения задачи (S, Р, F) является асимптотически точным.

В п. 3.2 предложена метаэвристпка APXGA с апостериорной оценкой точности решения задачи (G,P,F), сочетающая в себе идеи алгоритма Арх поиска приближенного решения и генетического алгоритма. Алгоритм АРХ использовался в метаэвристике для вычисления начальной популяции особей и для приближенного решения задачи оптимального кроссинговера.

Принцип работы алгоритма ApxGA следующий. Обозначим пу : Пj с П -популяция особей на итерации j, где особь тг £ П,- есть некоторое допустимое решение задачи и N = |П7-|. На начальной итерации случайным образом генерируются N остовных деревьев в графе G. Алгоритмом АРХ для каждого построенного дерева Т вычисляется особь тг € По и оценка точности еж решения тг. Вычисляется величина LB нижней границы по формуле

L^maxj^l.

л-еПо t с^. J

На каждой итерации j = 1,2,... выбираются две особи тг' и тт" из популяции П,--1 методом турнирной селекции. На фазе скрещивания строится новая особь тг по выбранным родительским решениям следующим образом. Случайным образом генерируется остовное дерево Т'. Определяется множество позиций размещения Р' = тг' U тг". В соответствии с алгоритмом АРХ, используя дерево Г', вычисляется приближенное решение тг задачи (G,P',F). Далее к новой особи тг применяются процедуры мутации и улучшения алгоритмом наискорейшего локального спуска. После этого решение тг включается в популяцию Пг_1. Новая популяция П, формируется по формуле

П,- = П;_1 \ {тг'} : тг' = arg шах {F(G, тг)}.

Если условие останова выполнено, то алгоритм ApxGA возвращает наилучшее найденное решение тг* и его относительную оценку погрешности s* = (F{G, тт*)- LB)/LB. Время работы алгоритма ApxGA равно 0(n3 (N + /)), где I - число итераций генетического алгоритма.

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

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

IBM ILOG CPLEX. Было выявлено, что применение алгоритмов Ас и Aj для решения ДЗВ перспективно при сравнительно малых значениях величины параметра к (от 1 до 3), причем, чем меньше величина к и чем больше количество вершин размещаемого графа, тем предложенные алгоритмы более эффективны по сравнению с алгоритмом ветвей и границ, реализованном в пакете IBM ILOG CPLEX.

В п. 4.2 приведены результаты анализа эффективности приближенных алгоритмов, предложенных в главе 3, как в сравнении с коммерческим пакетом IBM ILOG CPLEX, так и в сравнении с известной метаэвристикой поиска с чередующимися окрестностями, предложенной В. Филиповичем и Д. Кратика (Kratica J., Filipovich V., 2010). Выявлены параметры задачи, влияющие на величину оценки точности предложенных приближеных алгоритмов. Найдены подклассы задачи, на которых использование приближенного алгоритма Арх перспективно. Обнаружено, что предложенная метаэвристика ApxGA позволяет получать приближенные решения, близкие к оптимальным, и существенно превосходит известную метаэвристику В. Филиповича и Д. Кратика в точности вычисляемого решения, при сравнимом времени счета.

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

Основные результаты, выносимые на защиту

1. Сформулирована и доказана теорема о том, что дискретная задача Вебера полиномиально разрешима при фиксированном к на классе к-деревьев. Предложен алгоритм поиска точного решения, основанный на технике динамического программирования по дереву декомпозиции, имеющий оценку времени счета 0(nfc+3) и оценку требуемой оперативной памяти 0(пк+л), где п - число вершин графа [2, 6, 12, 1С].

2. Сформулирована и доказана теорема о том, что дискретная задача Вебера полиномиально разрешима при фиксированном к на классе к-цепей. Предложен алгоритм поиска точного решения, основанный на технике динамического программирования, имеющий оценку времени счета 0(пк+2) и оценку требуемой оперативной памяти 0(пк), где п -число вершин графа [1, 7, 8, 9, 11].

3. Предложен алгоритм поиска приближенного решения дискретной задачи Вебера в случае произвольного размещаемого графа, имеющий трудоемкость 0(п3). Доказана его апостериорная опенка точности

и выявлены параметры задачи, влияющие на величину данной оценки. Найдены подклассы задачи, на которых алгоритм является 2-приближенным и асимптотически точным [3, 4, 10, 13, 14, 15].

4. Для дискретной задачи Вебера с произвольным размещаемым графом предложена метаэвристика. позволяющая вычислять апостериорную оценку погрешности найденного решения. Метаэвристика находит приближенные решения, близкие к оптимальным, и превосходит в точности решения наилучшую из известных метаэвристик, при сравнимом времени счета [5, 10, 14, 15].

Публикации в изданиях, входящих в перечень ВАК

1. Шангин Р.Э. Детерминированный алгоритм решения задачи Вебера для n-последовательносвязной цепи /7 Дискретный анализ и исследование операций. 2013. Т. 20, № 5. С. 84-96.

2. Панюков A.B., Шангин Р.Э. Точный алгоритм решения дискретной задачи Вебера для к-дерева //' Дискретный анализ и исследование операций. 2014. Т. 21, № 3. С. 64-75.

3. Шангин Р.Э. Точный и эвристический алгоритмы решения дискретной задачи Вебера для простого цикла Вестник Новосибирского государственного университета. Серия: математика, механика, информатика 2014. Т. 14, № 2. С. 98-107.

4. Шангин Р.Э. Алгоритм точного решения дискретной задачи Вебера для простого цикла // Прикладная дискретная математика. 2013. № 4, С. 96-102.

5. Шангин Р.Э. Исследование эффективности приближенных алгоритмов решения одного частного случая задачи Вебера // «Экономика, статистика и информатика. Вестник УМО». 2012. № 1. С.163-169.

6. Шангин Р.Э. Точный алгоритм для решения одного частного случая задачи Вебера в дискретной постановке /7 Прикладная дискретная математика. 2013. У'- 6. С. 136-137.

Публикации по теме диссертации в других изданиях

7. Шангин Р.Э. Сравнение эффективности приближенных алгоритмов решения одного частного случая задачи размещения // «Статистика. Моделирование. Оптимизация»: Материалы Всероссийской конференции (Челябинск. 26 ноября - 2 декабря. 2011). Челябинск: Издательство ЮУрГУ. 2011. С. 336-338.

8. Шангин Р.Э. Разработка и анализ алгоритмов для задачи Вебера // «Проблемы оптимизации и экономические приложения»: Материалы V Всероссийской конференции (Омск, 2-6 июля, 2012 ). Омск: Издательство ОмГУ. 2012. С. 222.

9. Шангин Р.Э. Об одном алгоритме точного решения задачи Вебера для п-последователыюсвязноп цепи /7 «Актуальные задачи математического моделирования и информационных технологий»: Труды международной научно-практической конференции, (Сочи, 25-29 мая, 2013). Сочи: Издательство СГУ. 2013. С. 242-251.

10. Шангин Р.Э. Приближенные алгоритмы решения задачи размещения специального вида /7 Труды Всероссийской олимпиады по математическим методам и статистике: Сборник трудов участников (Москва, 15-17 ноября, 2011). Москва: Издательство МЭСИ. 2011. С. 120-125.

11. Шангин Р.Э. Об одном алгоритме точного решения задачи Вебера для n-последовательноевязной цепи </ «Информационные технологии интеллектуальной поддержки принятия решений»: Труды международной конференции (Уфа, 10-15 апреля, 2013). Уфа: Издательство УГАТУ. 2013. С. 76-81.

12. Шангин Р.Э. Алгоритм точного решения дискретной задачи Вебера для k-дерева // «Высокопроизводительные вычисления - математические модели и алгоритмы»: Труды II Международной конференции (Калининград, 13-17 ноября, 2013). Калининград: Издательство Балтийского федерального университета им. И. Канта. 2013. С. 113-116.

13. Шангин Р.Э. Точный алгоритм решения дискретной задачи Вебера для простого цикла /7 45-ая Международная школа-конференция, посвященная 75-летию В.И. Бердышева: Труды Международной школы-конференции (Екатеринбург, 23-26 февраля, 2014). Екатеринбург: Издательство ИММ УрО РАН. 2014. С. 189-192.

14. Шангин Р.Э., Панюков A.B. Алгоритм с оценкой для решения дискретной задачи Вебера /, «Математическое программирование и приложения»: Труды XV Всероссийской конференции (Екатеринбург, 26 марта, 2015). Екатеринбург: Издательство ИММ УрО РАН. 2015. С. 167-168.

15. Шангин Р.Э., Панюков A.B. Алгоритмы с оценками для решения одной нелинейной задачи о назначениях // Материалы VI Международной конференции «Проблемы оптимизации и экономические приложения» (Омск, 28 июня - 4 июля, 2015). Омск: Из-во ОмГУ. 2015. С. 245.

16. Shangin R.E. Exact algorithm for solving discrete Weber problem for a k-tree /' The 15th International Workshop on Computer Science and Information Technologies: Proceedings (Ufa. -1-8 May. 2013). Ufa: USATU. 2013. P. 282284.

Программа для ЭВМ

17. Шангин Р.Э. Программа нахождения оптимального размещения объектов торгового предприятия на местности / ' Свидетельство о государственной регистрации программы для ЭВМ JV8 2014611222 от 28 января 2014 г., правообладатель: ФГБОУ ВПО «ЮУрГУ».

Издательский центр Южно-Уральского государственного университета

Подписано в печать 09.07.2015. Формат 60x84 1/16. Печать цифровая. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 382/449.

Отпечатано в типографии Издательского центра ЮУрГУ. 454080, г. Челябинск, пр. им. В.И. Ленина, 76.