Geum.ru
   Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]

Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях

Автореферат кандидатской диссертации

 

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

ЛАГЗДИН Артем Юрьевич

ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

РЕШЕНИЯ КВАДРАТИЧНОЙ ЗАДАЧИ О

НАЗНАЧЕНИЯХ НА СЕТЯХ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат

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

Омск - 2012


Работа выполнена в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН

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

профессор Забудский Геннадий Григорьевич

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

профессор Попков Владимир Константинович,

кандидат физико-математических наук Борисовский Павел Александрович

Ведущая организация:а Иркутский государственный университет

Защита состоится 01 марта 2012 г. в 1б45 часов на заседании диссертационного совета ДМ 212.179.07 при Омском государственном университете им. Ф.М. Достоевского по адресу: 644099 г. Омск, ул. Певцова, д. 13.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского по адресу: 644077 г. Омск, проспект Мира, д. 55-А.

Автореферат разослан "______ " _______________ а2012 г.

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

диссертационного совет (/&м*я*бСеменов A.M.

2


ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

По признаку наличия фиксированных связей между объектами в задачах размещения можно выделить два класса - размещение взаимосвязанных объектов и размещение-распределение. В задачах первого класса требуется найти позиции для расположения объектов с заранее заданными связями между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера. Они рассматривались в работах Ахмедова И.С, Демиденко В.М., Забудского Г.Г., Иорданского М.А., Метельского И.И., Панюкова А.В., Сергеева СИ., Сигала И.Х., Трубина В.А., Burkard R.E., Qela Е., Finke С и других. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача о р-медиане, задача о р-центре, задача размещения с предпочтениями клиентов. Значительный вклад в развитие этого направления внесли Берес-нев В.Л., Гимади Э.Х., Колоколов А.А., Кочетов Ю.А., Кристофидес И. и другие.

Актуальными в настоящее время является исследование задач оптимизации на сетях и различных дискретных структурах. Данному направлению, в частности, посвящены работы Ерзина А.И., Кристофидеса И., Кузьмина О.В., Попкова В.К. В диссертации изучается дискретная задача размещения взаимосвязанных объектов - квадратичная задача о назначениях (КЗН), сформулированная в терминах теории графов. Она А^Р-трудна в общей постановке.

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

Точные методы решения КЗН (например, алгоритмы ветвей и границ) слабо применимы на практике. В задачах с числом объектов более 20

не гарантировано нахождение точного решения за приемлемое время. Для

3


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

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

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

С учетом поставленной цели решались следующие задачи:

  1. сформулировать задачу оптимального размещения взаимосвязанного технологического оборудования нефтехимического предприятия в виде модели КЗН;
  2. разработать полиномиальные алгоритмы решения КЗН для специальных структур связей между объектами и сетей, на которых производится размещение;
  3. построить эффективные алгоритмы решения задачи для общих структур связей между объектами;
  4. создать программное обеспечение и провести экспериментальное исследование предложенных алгоритмов, в том числе, с применением известных программных продуктов.

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

Научная новизна. Разработаны новые полиномиальные алгоритмы решения КЗН с минисуммным и минимаксным критериями на древовидных сетях для специальных структур связей между объектами. Предложены параллельный алгоритм динамического программирования и алгоритм поиска

4


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

Основные результаты диссертации заключаются в следующем.

  1. Проведено исследование КЗН с минисуммным критерием в теоретико-графовой постановке, которая является математической моделью размещения взаимосвязанного технологического оборудования. Структура связей представляет собой граф, позиции для размещения - узлы сети. Построены полиномиальные алгоритмы решения задачи на древовидной сети для случаев, когда структура связей представляет собой цепь или цикл с равными весами ребер.
  2. Разработан полиномиальный алгоритм решения КЗН с минимаксным критерием для размещения объектов со структурой связей в виде цепи на древовидной сети в случае ребер одинакового веса.
  3. Предложен параллельный алгоритм динамического программирования решения КЗН с минисуммным критерием для графа связей общей структуры с произвольными весами ребер на древовидной сети с равными

весами.

  1. Разработан алгоритм поиска приближенного решения КЗН с минисуммным критерием для графа связей и сети общего вида с произвольными весами ребер.
  2. Создан программный комплекс с реализацией предложенных параллельного алгоритма динамического программирования и алгоритма поиска приближенного решения. Проведено экспериментальное исследование эффективности параллельного алгоритма в зависимости от характеристик сети и конфигурации ЭВМ. Выполнено сравнение его работы с результатами решения задачи программным пакетом IBM ILOG CPLEX. Проведен вычислительный эксперимент по анализу работы алгоритма поиска приближенного решения.

Практическая ценность. Полученные в диссертации результаты представляют ценность в области развития методов математического моделирования и дискретного программирования. Предложенные алгоритмы применимы для решения прикладных задач, в частности, при разработке систем автоматизированного проектирования. Программный комплекс может быть использован в научных исследованиях в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН, Омском государственном университете им. Ф.М. Досто-


евского, Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН.

Апробация работы. Результаты диссертации докладывались на IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (г. Омск, 2009), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (г. Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Республика Алтай, 2010), Международной конференции "Operations Research 2010" (г. Мюнхен, Германия, 2010), 8 Международной конференции "Интеллектуализация обработки информации ИОИ-2010" (г. Пафос, Республика Кипр, 2010), XIV Всероссийской конференции "Математическое программирование и приложения" (г. Екатеринбург, 2011), XXXV Региональной научно-практической студенческой конференции "Молодежь третьего тысячелетия" (г. Омск, 2011), Международной конференции "Operations Research 2011" (г. Цюрих, Швейцария, 2011), Международной конференции "Optimization and Applications OPTIMA-2011" (г. Петровац, Черногория, 2011), а также на научных семинарах в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН (2009-2011).

Публикации. Основные результаты работы опубликованы в 11 научных работах [1-11], две из них - в изданиях из списка ВАК.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В п. 1.1 рассматриваются различные постановки КЗН. Впервые данная задача была сформулирована Купмансом Т. и Бекманном М. в 1957 году как математическая модель для дискретной задачи размещения предприятий. Необходимо разместить?! предприятий (объектов) вп позиций по одному в каждую таким образом, чтобы минимизировать суммарную стоимость связей, которая пропорциональна удельным стоимостям связей между предпри-

6


ятиями умноженным на расстояния между позициями. В некоторых случаях дополнительно учитывается стоимость размещения предприятий в указанные позиции. Задачу можно сформулировать с помощью трех матриц: А = (а^), где dik- стоимость связи между объектами г и к; В = (bji), bji- расстояние между позициями jи /; С = (с^), с^ - стоимость размещения объекта г в позицию j, где г, J, & = 1,... ,п. Пусть 7Г - это подстановка на множестве {1,...,п}, тогда целевая функция КЗН в постановке Купманса-Бекманна имеет вид

п пп

(52*52aikb+52С{<^-**zsnmin,

i=\а k=\i=l

где Sn- множество всех подстановок на множестве {1,... , п}.

Заметим, что в каждой позиции должен быть размещен только один объект. Задача с заданными матрицами А, В, С обозначается как QAP(A, В, С). Если линейное слагаемое (матрица С) отсутствует, задача обозначается QAP(A, В). На практике элементы матрицы В часто удовлетворяют неравенству треугольника bji+ bir> bjrдля различных j,l,r= 1,... ,n. В этом случае задача называется метрической КЗН.

Если минимизируется максимальная стоимость связей, то задача называется КЗН с минимаксным критерием (минимаксная КЗН) и обозначается QBAP(A, В) при отсутствии матрицы С. Ее целевая функция имеет вид

_ maxаа ЩкК(^{к) Ч>TveSn min .

г,к=1,...,п

Постановки КЗН в терминах теории графов формулируются следующим образом1. Дан граф связей G= (V^,E^) и граф расстояний М = (Vd, Ed). Множество V? = \у : = 1,.. . , п} соответствует объектам, а множество Vаа = {г> : i= 1,... , п} - позициям, в которые объекты размещаются.

Ребро {Vi,Vj}а к Е?, кСЛИ Существует СВЯЗЬ Между объектами fj И Vj, w(Vi,Vj)

- это вес ребра {vi,Vj} к Е?. Через p(ir(vi),ir(vj)) обозначим кратчайшее расстояние между позициями ir(vi) и 7t(vj). Целевая функция КЗН в терминах теории графов имеет вид

{Vi,Vj}eEf

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

Fmax{7T) =аа maxа w{Vi, Vj)p(Tl(Vi) , Tl{Vj)) ~^^eSn ШП . {vi,Vj}eEf

^arahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and case studies. - Heidelberg: Physica-Verlag, 2009. - 543 p.

7


Для удобства изложения обозначим граф связей между объектами через G= (N, Е), где N = {1,.. . , п} - множество пронумерованных некоторым образом вершин V? и Е = Е?, а М = (V,U), где V= {1,...,п} = {г,..., vn}, U= Ed. Далее граф расстояний М с весами на ребрах будем называть сетью, его вершины - узлами. Не уменьшая общности можно считать, что если в графе веса всех ребер равны, он является невзвешенным (полагаем все веса равными 1). Задача размещения графа Gна сети М с критериями Fили Fmaxв дальнейшем обозначается тройкой (G, М, F) или (G, М, Fmax) соответственно.

В п. 1.2 описываются некоторые практические задачи, математической моделью которых является КЗН. Приводятся известные задачи оптимизации, являющиеся частными случаями КЗН, в том числе, задача коммивояжера.

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

В п. 1.3 приводится обзор известных методов решения КЗН в различных постановках.

Основные методы нахождения точного решения TVP-трудных задач применялись и для решения КЗН. Это алгоритмы ветвей и границ (основная используемая граница - граница Гилмора-Лоулера), отсечений, декомпозиции. Данные подходы оказались слабо применимыми на практике. Оптимальное решение тестовых примеров КЗН за приемлемое время было найдено только для числа объектов не более 20. В середине 1990-х годов разработка параллельных алгоритмов на суперкомпьютерах позволила увеличить размерность решаемых задач до 25. В дальнейшем, применение распределенных вычислений увеличило размерность до 30.

8


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

Основное внимание в исследованиях КЗН в терминах теории графов уделяется разработке эффективных алгоритмов для специальных структур связей между объектами и сетей. Известны полиномиальные алгоритмы размещения изоморфных графов специальной структуры, эффективные алгоритмы размещения деревьев на цепи, алгоритм локальной оптимизации и другие (Забудский Г.Г., Иорданский М.А., Кристофидес Н., Метельский Н.Н., Rendl F.). Предложен алгоритм динамического программирования решения задачи размещения произвольного взвешенного графа на невзвешенном дереве для минисуммного критерия (Забудский Г.Г.). Для решения специальных случаев КЗН на сетях известны приближенные алгоритмы с оценками (Сви-риденко М.И., Hassin R.).

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

В п. 2.1 изучаются задачи с минисуммным критерием размещения невзвешенных цепи и цикла на взвешенной древовидной сети. Даны произвольная древовидная сеть Т = (V, U) с заданными весами ребер и невзвешен-ная цепь Ch= (N, Е). Рассматривается задача размещения (Ch,T, F). Идея алгоритма Amsрешения данной задачи состоит в построении маршрута, проходящего по всем узлам сети Т как минимум один раз, и минимального по суммарному весу входящих в него ребер. Для этого в сети выделяется главная цепь (цепь, соединяющая висячие узлы) максимальной длины, и применяется разработанный алгоритм размещения вершин Chв узлы Т.

Сформулирована и доказана

Теорема 2.1. Алгоритм Amsнаходит оптимальное решение задачи (CVi,T,F).

Трудоемкость алгоритма Ата не превосходит 0(п^) операций.

Аналогично задаче (Ch,T,F), рассматривается задача размещения невзвешенного цикла Су на взвешенном дереве Т - задача (Cy,T,F). Для построения оптимального решения указанной задачи цикл "разрезается" по произвольному ребру, и полученная цепь размещается в соответствии с приведенным ранее алгоритмом с выбором произвольной главной цепи в сети Т. Трудоемкость решения задачи (Cy,T,F) не превосходит О(п) операций.

9


В п. 2.2 приводится разработанный полиномиальный алгоритм Атт решения задачи с минимаксным критерием размещения невзвешенной цепи на невзвешенной древовидной сети. Даны невзвешенная цепь Ch= (TV, Е) иа невзвешеннаяа древовиднаяа сеть Таа =аа (V, U).аа Рассматриваетсяа задача

yLy Д, 1 , гmax) Х

В сети Т выделяется цепь Со = (Vo, Щ), Vo= (&т,..., fcp), соединяющая некоторые узлы к\ и kPjкоторая называется главной. Каждому узлу kiк Vo сопоставляется поддерево Ti= (Vi,Ui). Множество ViСОСТОИТ ИЗ kiи всех тех узлов дерева Т, которые соединены с кг цепями, не содержащими ребер из Uq. Множество Uiобразовано ребрами таких цепей.

В алгоритме Ашш рассматриваются все возможные представления сети Т с выделенными главными цепями и осуществляется поиск в поддеревьях Tiсетей вида Gi и G2, которые имеют структуру, представленную на рис. 1.


Рис. 1: Сети вида G\ и G2.

Если алгоритмом Ашш найдено представление дерева Т, не являющегося цепью, без сетей вида Gi и G2, то с его помощью будет получено оптимальное решение тг* исходной задачи со значением целевой функции Fmaxi'K*) =2. Если во всех рассмотренных представлениях дерева Т имеется сеть вида G\ или G^iто оптимальное значение Fmax(7r*) = 3. Если Т -это цепь, то Fmax{^) = 1.

В диссертации доказана

Теорема 2.2. Алгоритм, Атт находит, оптимальное решение задачи

yLy Д, 1 , Гщах) Х

Трудоемкость алгоритма Атт не превосходит 0(n4logn).

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

дереве. Проведены численные эксперименты для различных структур древо-

10


видных сетей и конфигураций ЭВМ. Приводятся результаты сравнения эффективности предложенного алгоритма с решением задачи с использованием программного пакета IBM ILOG CPLEX. Сделаны выводы о целесообразности и перспективности применения указанного алгоритма. Предложен алгоритм поиска приближенного решения КЗН размещения графа общей структуры на произвольной сети. Алгоритм реализован на ЭВМ, проведен вычислительный эксперимент по оценке его эффективности.

В п. 3.1 рассматривается задача (G, М, F), где G= (N, Е) - взвешенный граф произвольной структуры, а М = (У, U) - невзвешенная древовидная сеть. Представлен параллельный алгоритм динамического программирования (ДП) решения данной задачи.

Идея алгоритма заключается в следующем. В древовидной сети М в качестве корня выбирается центр (если их два, то произвольный). Предполагается, что нумерация вершин сети М является сплошной и в любом поддереве номер корня больше номера любого узла этого поддерева. Для удобства обозначений вводится подстановка ф = 7Г . Через d(s) обозначается степень узла sк V.

Состояние в процессе ДП определяется как подмножество вершин Т = {ii,. .. ,is} графа G, размещенных в первые sузлов сети М. Начальное состояние Т = 0 - ни одна вершина не размещена. Конечное состояние Т = {1,...,п} - размещены все вершины. Переход из одного состояния в другое рассматривается как последовательный перебор узлов дерева М в соответствии с их нумерацией. Обозначим через Ф(5') множество вершин графа G, размещенных в множество узлов Sсети М. Пусть Т = Ф(5) U Ф(5,2) U ... U Ф(5^), где Si,... , Sp- множества узлов дерева М, которые индуцируют в М несвязные поддеревья, U^=1Si = S.

На прямом ходе параллельного алгоритма ДП главный поток определяет множество узлов сети М, смежных с корнем, и передает данные узлы и соответствующие им поддеревья подчиненным потокам. Каждый подчиненный поток применяет прямой ход алгоритма ДП к "своему" поддереву и вычисляет значения функции Беллмана по формулам (1)-(3). После завершения работы подчиненных потоков главный поток вычисляет значение функции f(V), которое является оптимальным значением целевой функции F(n*).

На обратном ходе главный поток определяет вершину графа G, размещенную в корень дерева М, после чего каждому из подчиненных потоков передает множество вершин, размещенных в соответствующие потокам поддеревья, и значения функции /. Потоки последовательно обрабатывают узлы поддеревьев, двигаясь от узла с наибольшим номером к наименьшему, и определяют вершины графа G, размещенные в данные узлы. Свободные на очередном шаге алгоритма потоки используются при вычислениях значений функции / (на прямом ходе) и определении вершин, размещенных в узлы сети (на обратном).

Для вычисления значений функции / на очередном шаге алгоритма (размещение в узел sк V) необходимо хранить все возможные в данном случае блоки из узлов дерева М. Это или сочетания без повторений (в случае d{s) < 2), или наборы сочетаний, которые назовем сочетаниями по блокам (при d{s) > 3). Пусть в узле sобъединяются р ветвей (блоков), пронумерованных 1, 2,... ,р, количество узлов в ветвях равно &i, &2,... ,кр соответственно. Тогда сочетанием из п элементов по блокам 1,...,р назовем набор из различных элементов вида (а}, а\, Х Х Х, а\ ; af,... , а| ; ...; ар,... , арк ; ар+1), где а\,...,а,а,...,а12,...,а,...,аркр,ае~1к {1, ..., п}, причем а\ < а\ <...< alki] а\ < ...< а|2; ...;<<...< аркр.

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

12


без повторений для вычисления значений функции /. Для ускорения этой операции был разработан алгоритм поиска индекса сочетания.

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

Пусть р - максимальная степень узлов сети М. Сформулирована и доказана

Теорема 3.2. Трудоемкость решения задачи (G, М, F) алгоритмом ДП не превосходит 0{ni{p+ 1)2п). Требуемое количество памяти -0(п(р + 1)п).

В п. 3.2 приводятся результаты численного эксперимента по оценке эффективности параллельного алгоритма ДП. Варьируется структура древовидной сети - рассматриваются деревья различного диаметра при равном количестве узлов, от дерева с наибольшим диаметром - цепи, до дерева минимального диаметра - звезды. Алгоритм ДП реализован на языке СИЧЬ с использованием библиотеки ОрепМР, предназначенной для программирования многопоточных приложений на многопроцессорных системах с общей памятью. Для оценки его эффективности использовался программный пакет IBM ILOG CPLEX Optimization Studio 12.2 (решение КЗН алгоритмом ветвей и границ с ограничением по времени работы).

Время решения задачи с использованием параллельного алгоритма на процессоре с г ядрами сокращается с уменьшением диаметра дерева по сравнению с временем решения последовательным алгоритмом на этой же конфигурации ЭВМ (почти в г раз на звезде). На деревьях большого диаметра эффективность применения параллельного алгоритма при г > 2 по сравнению с г = 2 не столь значительна.

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

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

13


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

В п. 3.3 излагается алгоритм поиска приближенного решения КЗН на произвольных сетях. Рассматривается задача (G,M,F), где G= (N,E) -взвешенный граф, М = (V, U) - взвешенная сеть. Идея алгоритма состоит в построении qсетей Mi= (Vi,Ui) таких, что ViС V, \Vi\ < к для некоторого к к {2,..., п} и всех i= 1,..., q, множества V{ и V^+i, г = 1,..., qЧ 1, пересекаются и КЗН размерности к разрешима за приемлемое время. В экспериментах варьируется начальное размещение графа на сети. Последовательно решаются КЗН на сетях Mj, г = 1,...,д, с учетом линейного слагаемого, представляющего собой сумму стоимостей связей вершин, размещенных bV^, с вершинами, размещенными в V \Vi. В итоге получаем приближенное решение исходной задачи. Проведен вычислительный эксперимент по оценке эффективности работы предложенного алгоритма. Выполнено сравнение с результатами решения КЗН известными эвристическими алгоритмами: муравьиной колонии и имитации отжига.

В заключении приводятся основные результаты диссертации.

Опубликованные работы по теме диссертации

В рецензируемых журналах из списка ВАК

[1] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на сетях // Журнал вычислительной математики и математической физики. - 2010. - Т. 50, № 11. -С. 2052-2059.

[2] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискретный анализ и исследование операций. - 2011. - Т. 18, № 4. - С. 48-64.

В других изданиях

[3] Забудский Г.Г., Лагздин А.Ю. Алгоритм решения квадратичной задачи о назначениях с минимаксным критерием на дереве // Материалы VII Международной научно-технической конференции "Динамика систем, механизмов и машин". - Омск: ОмГТУ, 2009. - Т. 3. - С. 23-27.

[4] Забудский Г.Г., Лагздин А.Ю. Анализ эффективности параллельного алгоритма динамического программирования для квадратичной задачи о назначениях на дереве // Тезисы докладов XIV Всероссийской конференции "Математическое программирование и приложения". Информационный бюллетень Ассоциации математического программирования. -

Екатеринбург, 2011. - № 12. - С. 176.

14


[5] Забудский Г.Г., Лагздин А.Ю. Параллельный алгоритм динамического программирования решения квадратичной задачи о назначениях на дереве IIМатериалы Российской конференции "Дискретная оптимизация и исследование операций". - Новосибирск, 2010. - С. 161.

[6] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичных задач о назначениях на деревьях // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2009. - С. 126.

[7] Забудский Г.Г., Лагздин А.Ю. Эффективные алгоритмы решения специальных случаев квадратичной задачи о назначениях на сетях jjДоклады 8 Международной конференции " Интеллектуализация обработки информации ИОИ-2010". - М: МАКС Пресс, 2010. - С. 255-257.

[8] Лагздин А. Экспериментальное сравнение алгоритмов динамического программирования решения квадратичной задачи о назначениях на дереве IIМолодежь третьего тысячелетия: XXXV Региональная научно-практическая студенческая конференция: сборник статей секции "Физико-математические науки". - Омск: Изд-во ОмГУ, 2011. -С. 20-23.

[9] Lagzdin A., Zabudsky G. Polynomial algorithms for some cases of quadratic assignment problem // Abstracts of International conference "Operations Research 2010". - Munich, 2010. - P. 118-119.

[10] Lagzdin A., Zabudsky G. Some algorithms for the quadratic assignment problems on networks // Abstracts of International conference "Operations Research 2011". - Zurich: IFOR, 2011. - P. 26.

[11] Zabudsky G., Lagzdin A. Polynomial algorithms for some quadratic assignment problems in terms of graphs // Abstracts of II International conference "Optimization and Applications" (OPTIMA-2011). - M.: В - PAH, 2011. - P. 220-223.

15

     Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]