Исследование и решение минимаксных и минисуммных задач размещения на сетях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

ФИЛИМОНОВ Дмитрий Валерьевич

ИССЛЕДОВАНИЕ И РЕШЕНИЕ МИНИМАКСНЫХ И МИНИСУММНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ НА СЕТЯХ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск - 2004

Работа выполнена в Омском филиале Института математики имени С.Л. Соболева СО РАН

Научный руководитель:

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

Официальные оппоненты:

доктор физико-математических наук, профессор Стрекаловский Александр Сергеевич кандидат физико-математических наук, доцент Хамисов Олег Валерьевич

Ведущая организация:

Институт математики и механики Уральского отделения РАН

Защита состоится 17 декабря 2004 г. в 14.00 часов на заседании диссертационного совета Д 212.074.01 в Иркутском государственном университете по адресу: 644003, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (бульвар Гагарина, 24).

Автореферат разослан 15 ноября 2004 г.

Ученый секретарь диссертационного совета,

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

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

В настоящее время активно развиваются теория и методы решения задач размещения1, ведутся исследования их структуры и вычислительной сложности , выделяются полиномиально разрешимые случаи , предлагаются точные и приближенные алгоритмы их решения4. В последние годы для решения задач оптимизации широко разрабатываются методы локального поиска, а также подходы, основанные на аналогиях с природой5. Данные подходы являются перспективными и для задач размещения, которые, как правило, являются NP-трудными.

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

1 Колоколов А А , Леванова ТВ Алгоритмы декомпозиции и перебора L-классов для решения некоторых задай размещения // Вестник Омского ун та - Омск, 1996 - № 1 - С 21-23

2Забудский Г Г О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы - Новосибирск, 1990 - Вып 30 - С 35-45

3Панюков А В , Пельцвергер Б В Оптимальное размещение дерева в конечном множестве Ц Журнал вычислительной математики и математической физики - 1988 - Т 28 - С 618-620

4Стрекаловский А С , Васильева А М Поиск глобального решения в задаче размещения // Материалы международной конференции "Дискретный анализ и исследование операций" - Новоси бирск, 2000 - С 121

$Кочетов Ю АВероятностныеметодылокального поиска длязадачдискретной оптимизации // В сб лекций "Дискретная математика и приложения" - Москва, 2.001 - С 84-117

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

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

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

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

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

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

3. Доказано, что задача определения совместности ограничений на максимально допустимые расстояния в случае размещения объектов в вершинах, а также дискретная минимаксная задача оптимального размещения на произвольной сети являются NР-трудными.

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

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

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

Апробация работы. Результаты диссертации докладывались на XI Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999), Symposium on Operational Research (Магдебург, Германия, 1999), международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), научной молодежной конференции "Молодые ученые на рубеже третьего тысячелетия" (Омск, 2001), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002), International Conference on Operations Research (Клагенфурт, Австрия, 2002), 12-й Всероссийской конференции "Математическое программирование и приложения" (Екатерин-

бург, 2003), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международном семинаре "Discrete Optimization Methods in Production and Logistics" (Омск-Иркутск, 2004), а также на научном семинаре "Математическое моделирование и дискретная оптимизация" в Омском филиале Института математики СО РАН им. СЛ.Соболева.

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

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

Структура и объем работы. Диссертация изложена на 94 страницах и состоит из введения, трех глав, заключения и списка литературы (102 наименования). В каждой главе использована своя нумерация параграфов, утверждений, теорем и формул.

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

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

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

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

В п. 1.1 содержатся комбинаторная постановка непрерывных и дискретных вариантов минимаксных и минисуммных задач размещения объектов на сетях с ограничениями на максимальные расстояния.

Дана связная неориентированная сеть. Фиксированные объекты расположены в вершинах сети а новые объекты размеща-

ются в точках которые могут быть расположены как

в вершинах, так и на дугах. Расстояние d(x, у) между точками х и у в сети определяется как длина кратчайшего пути между ними. Обозначим через Wij и Vjt неотрицательные удельные стоимости связей . между фиксированным объектом i и размещаемым j, а также размещаемых объектов j и к между собой соответственно. Введем также следующие обозначения:

Минимаксная задача (необходимо найти размещение, минимизирующее стоимость максимальной связи) имеет вид:

max(ykfj°j<k vikd(xi> Wiid(v" min- (u)

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

k E kVjkd{xj,xk) + E E wijd(i>i,Xj) min. (1.2)

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

Рассматриваются также дискретные задачи, в которых объекты могут размещаться в конечном множестве точек. Пусть требуется разместить п новых объектов в вершинах сети Ь1У...,г)т. В одной вершине можно размещать произвольное количество новых объектов. Размещением объектов в дискретном варианте задачи назовем однозначное отображение п : J -» т.е. новый объект у размещается в вершину

Рис. 1.1. Примеры размещений.

Минимаксная задача в этом случае имеет вид:

шах(;к£п<к"^"»У)'"»(*))'¿^¿Ь"*(»)) пуп. (1-5)

амиь £ + Е Е пуп. (1.6)

Ограничения на максимальные расстояния между объектами в дискретной постановке:

Примеры размещений представлены на рис. 1.1 (в квадратах указаны номера новых объектов).

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

В статье6 получены необходимые и достаточные условия существования размещения, удовлетворяющего (1.3)-(1.4) (условия отделимости), а также процедура SLP, которая позволяет найти допустимое размещение на дереве.

Для решения задачи (1.1),(1.3)-(1.4) в статье7 предложен алгоритм бинарного поиска по ранжированным значениям целевой функции с использованием условий отделимости и процедуры SLP. Трудоемкость алгоритма равна 0(п(т + п)(т + nlogM)), где М - максимум среди числителей и знаменателей рациональных исходных данных.

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

В п.1.3 рассматривается дискретная минимаксная задача размещения на древовидной сети. Разработан полиномиальный алгоритм решения задачи (1.5),(1.7)-(1.8) на древовидной сети.

Найти допустимое размещение в вершинах дерева, удовлетворяю-

6 Francis R L , Lowe T J , Ratlifff D H Distance constraints for tree network multtfacthty location

problems // Oper Res - 1978 - X« 26(4) - P 570-595

7Erkut E , Francis R L , Tamir A Dtstance-constratned multtfacthty minimal location problems on tree network///Networks -1992 -№22 -P 37-54

щее (1.7)-(1.8) можно с помощью предлагаемого алгоритма SDLA [Sequential Discrete Location Algorithm). Доказывается

ТЕОРЕМА 1.1. Если существует допустимое размещение в вершинах сети, удовлетворяющее ограничениям (1.7)-(1.8), то SDLA находит такое решение, в противном случае алгоритм определяет, что допустимое решение отсутствует.

Задача (1.5),(1.7)-(1.8) решается следующим алгоритмом. Производится бинарный поиск оптимального значения целевой функции по ранжированным возможным значениям. Проверка существования и построение допустимого решения при фиксированном значении целевой функции производится алгоритмом SDLA. Трудоемкость алгоритма решения дискретной минимаксной задачи равна 0(т2пг1од(пт)).

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

Техника, аналогичная методу решения задачи на линии, применяется нами для решения задачи (1.2),(1.4) на дереве. Для этого вводится ориентация дуг от произвольно выбранной корневой вершины, которая учитывается алгоритмом решения задачи. Трудоемкость алгоритма решения задачи (1.2),(1.4) равна 0(max(m2n,mn3)).

Основные результаты первой главы опубликованы в [1-3,5-7,9,10, 13,14].

Вторая глава посвящена минимаксным и минисуммным задачам

8Picard J.C., Ratlifff D.H. A cut approach to the rectilinear distance facility location problem // Oper.Res. - 1978. - № 26(3). - P.422-433.

размещения объектов на произвольных сетях. В работе9 показана NP-трудность непрерывных задач размещения на произвольных сетях без ограничений на максимально допустимые расстояния. Кроме того, задача определения существования допустимого решения, удовлетворяющего (1.3)-(1.4) также является NP-трудной.

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

ТЕОРЕМА 2.1. Задача определения совместности ограничений на максимально допустимые расстояния (1.7)-(1.8) на произвольной сети является NP-трудной.

Доказательство проводится путем сведения NP-трудной задачи с ограничениями (1.3)-(1.4) к указанной в формулировке теоремы 2.1 задаче.

ТЕОРЕМА 2.2. Задача (1.5) на произвольной сети является NP-трудной.

Теорема доказывается сведением задачи, сформулированной в теореме 2.1, к задаче (1.5).

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

9Kolen A. Location problems on trees and tn rectilinear plane // Stitchting Mathematish Centrum. -Amsterdam, 1982.

l0Erkut E., Francis R.L., Lowe T.J., Tamir A. Equivalent mathematicalprogrammingformulations of monotontc tree network location problems // Oper.Res. - 1989. - № 37(3). - P.447-461.

тами, включают в себя операторы суммирования и/или максимизации, задача размещения эквивалентна задаче ЛП. Построены модели ЛП, эквивалентные задачам (1.1),(1.3)-(1.4) и (1.2)-(1.4) на древовидной сети. Эти модели используются для получения нижних оценок на значения целевой функции для задач на произвольной сети.

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

Дерево решений в алгоритме имеет следующий вид. Любому узлу на уровне ] взаимно-однозначно соответствует множество допустимых размещений таких, что для любого п £ тг^) = Л. Узел дерева решений имеет т потомков:

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

ЬМу = тах{^пмх^ «..^»(г), "»(*)),;тах, ^¿(г;;,^)), ™[тт тах(тахг-Г^(^(Г), г>4), тах и1к<1{ы, и5))]}.

Трудоемкость ее вычисления равна О(пт(п + т)).

Доказываются (теорема 2.3) необходимые условия существования размещения взаимосвязанных объектов с определенным значением це-

"Хамисов О.В. Поиск глобального минимума функций, имеющих выпуклые и вогнутые опор ные функции Ц Материалы XI Всероссийской конференции "Математическое программированы я приложения". - Екатеринбург, 1999. - С.272-273.

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

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

к E^fmini £ vrkd(v„[r),vs) + £ Wikd{vi, и,))].

В п.2.5 описаны результаты вычислительного эксперимента. Алгоритмы ветвей и границ сравнивались с пакетом ILOG OPL Studio, решающим квадратичные модели целочисленного программирования для минимаксной и минисуммной задач. Исходные данные генерировались случайным образом. Размерность решаемых задач (т,п) достигала (200,200) для минимаксной задачи и (40,40) для минисуммной задачи. Время решения задач с использованием пакета оказалось существенно больше, чем время работы алгоритмов ветвей и границ.

Результаты второй главы опубликованы в [3-5,8,12,15].

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

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

ных ограничении.

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

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

Определим для каждого нового объекта ] множество = {» : - совокупность номеров вершин, допустимых для его размещения. В качестве генотипа особи будем

рассматривать точку, принадлежащую декартову произведению множеств £>у, ] € ].

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

1) Вероятностный оператор. Потомок формируется следующим образом: каждый его ген с вероятностью

полагается равным гену , и с вероятностью где

5Ь 9ч - родительские особи, $ Е Л Ф(<?) - значение целевой функции

^Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. - 2000. - Т. 7,» 1. - С.47-60.

на соответствующем генотипу размещении.

2) Оператор последовательного размещения. Присваиваем каждому гену потомка gi,j = 1,...,п значение соответствующего родительского гена, для которого минимизируется связь с фиксированными и ранее размещенными объектами. При использовании определенного порядка присвоения значений генам оператор будет детерминированным, можно также использовать случайный порядок.

Оператор мутации с вероятностью pmui изменяет каждый j-й ген потомка на выбранный с равномерным распределением номер вершины из множества Dj. В качестве критерия остановки алгоритма используется ограничение по максимальному числу итераций

П.3.3 посвящен алгоритмам поиска с запретами. Рассматривается общая схема алгоритма поиска с запретами (Tabu Search)'3, который в процессе работы переходит от одного локального минимума задачи к другому. Данный алгоритм отличается от локального спуска тем, что в нем в процессе поиска разрешается переход в очередное решение с ухудшением значения целевой функции. Для того, чтобы избежать зацикливания, в алгоритме используется список запретов, с помощью которого запрещаются пройденные ранее решения. Предлагается несколько реализаций алгоритма поиска с запретами для решения задач (1.5),(1.8) и (1.6),(1.8).

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

Результаты третьей главы опубликованы в [11,12].

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

13Laguna M., Glover F. Bandwing Packing: A Tabu Search Approach // Managment Science. - 1993. - Vol. 39, № 4. - P. 492-500.

Список литературы

[1] Забудский Г.Г., Филимонов Д.В. Алгоритм решенья минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Омский науч. вест. - 1999. - Вып. 9. - С.37-40.

[2] Забудский Г.Г., Филимонов Д.В. Алгоритмы решения задач размещения на деревьях с ограничениями на максимальные расстояния // Материалы международной конференции "Дискретный анализ и исследование операций". - Новосибирск, 2000. - С. 165.

[3] Забудский Г.Г., Филимонов Д.В. О минимаксной и минисуммной задачах размещения на сетях // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения".

- Иркутск, 2001. - Т. 1. - С.150-155.

[4] Забудский Г.Г., Филимонов Д.В. Решение дискретной минимаксной задачи размещения на сети // Изв. вузов. Математика. -2004. - № 5. - С.ЗЗ-Зб.

[5] Забудский Г.Г., Филимонов Д.В. Решение дискретныхминимакс-ных и минисуммных задач размещения на сетях Ц Материалы Российской конференции "Дискретный анализ и исследование операций". - Новосибирск, 2002. - С.210.

[6] Забудский Г.Г., Филимонов Д.В. Решение минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния II Материалы XI Всероссийской конференции "Математическое программирование и приложения". - Екатеринбург, 1999.

- С. 114.

[7] Филимонов Д.В. Алгоритм размещения объектов на дереве с минимаксным критерием и максимальными расстояниями // Мате-

риалы научной молодежной конференции "Молодые ученые на рубеже третьего тысячелетия". - Омск, 2001. - С. 84.

[8] Филимонов Д.В. О способах построения нижних оценок для задач размещения взаимосвязанных объектов на сетях // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2003. - С. 111.

[9] Филимонов Д.В. Решение дискретной минимаксной задачиразме-щения на древовидной сети // Материалы ежегодного научного семинара аспирантов и студентов-выпускников "Под знаком

- Омск, 2003. - С.58-61.

[10] Филимонов Д.В. Решение минисуммной задачи размещения на линии с ограничениями на максимальные расстояния // Материалы Российской конференции "Дискретный анализ и исследование операций". - Новосибирск, 2004. - С. 170.

[11] Филимонов Д.В. Эвристические алгоритмы решения минимаксных и минисуммных задач размещения на сетях // Препринт. -Омск: Омск, госуниверситет, 2003. - 15 с.

[12] Филимонов Д.В., Забудский Г.Г. Некоторые алгоритмы размещения взаимосвязанных объектов на сетях // Материалы 12-й Всероссийской конференции "Математическое программирование и приложения". - Екатеринбург, 2003. - С.235.

[13] Zabudsky G.G., Filimonov D.V. An algorithm for minimax location problem on tree with maximal distances // Proc. of the Second International Workshop "Discrete Optimization Methods in Production and Logistics" (DOM2004). - Omsk-Irkutsk, 2004. - P.81-85.

[14] Zabudsky G.G., Filimonov D.V. An algorithm for the location problem on tree with maximal distances // Symp. on Operational Research (SOR99). - Magdeburg, 1999. - R115.

[15] Zabudsky G.G., Filimonov D.V. Solving discrete minimax location problem on networks // International Conference on Operations Research. - Klagenfurt, 2002. - P.153.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать 11.11.2004. Формат 60x84/16. Бумага офсетная. Отпечатано на ризографе. Усл. печ. л. 1,25. Уч.-изд. л. 1,12. Тираж 100 экз. Заказ № 358.

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира, д.32, к.П

тел.: (3812) 65-47-31 Лицензия ПЛД №58-47 от 21.04.1997.

»23344

Введение

Глава 1. Полиномиальные алгоритмы решения задач на деревьях с ограничениями на максимальные расстояния.

1.1 Постановка задач.

1.2 Алгоритмы решения непрерывной минимаксной задачи.

1.3 Решение дискретной минимаксной задачи.

1.4 Минисуммная задача размещения.

Глава 2. Алгоритмы ветвей и границ решения задач размещения на произвольных сетях. 2.1 Сложность минимаксных и минисуммных задач

2.2 Эквивалентная задача математического программирования.

2.3 Дискретная минимаксная задача размещения . '

2.4 Решение минисуммной задачи размещения

2.5 Вычислительный эксперимент.

Глава 3. Эвристические алгоритмы решения задач размещения на произвольных сетях.

3.1 Алгоритмы последовательного одиночного размещения

3.2 Генетические алгоритмы.

3.3 Алгоритмы поиска с запретами.

3.4 Вычислительный эксперимент.

Значительное число работ в области исследования операций посвящено решению проблем планировки и расположения объектов. Задачи размещения имеют обширную сферу практического применения, поскольку область, в которой производится размещение, может иметь различную структуру, и термин "объект" может трактоваться достаточно широко. Такие задачи возникают при размещении различных пунктов обслуживания, например, больниц, магазинов, пожарных депо, формировании генеральных планов предприятий [5,17], проектировании печатных плат [1,6], конструировании летательных аппаратов [49] и выполнении других работ.

Следует отметить, что изучение задач размещения объектов началось в 17 веке, когда Ферма сформулировал задачу, известную ныне как задача Вебера [27,82,98]: даны три точки на плоскости, требуется найти четвертую точку, такую, что сумма расстояний от нее до трех фиксированных точек минимальна. Задача была решена геометрически Торичелли в 1640 году. В 1750 году Симпсон обобщил задачу в направлении учета произвольных весов связей между объектами. В 1909 году Вебер использовал подобную модель для определения оптимального размещения фабрики при известных точках расположения ресурсов и потребителей продукта.

Среди задач размещения можно выделить два больших класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения (задачи размещения предприятий). К первому классу относятся задачи с заранее заданной структурой связей между объектами: задача Вебера [27,45,54,82,94,98], квадратичная задача о назначениях [70,88] и т.п. В задачах из второго класса отсутствуют связи между размещаемыми объектами-"поставщиками" и производится распределение фиксированных объектов-"клиентов" между ними: задачи о р-медиане [38,40,70,84] и р-центре [40,67,70,83], простейшая задача размещения [2,3,7,9,70,77,80,89,91] и др.

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

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

Формулировка каждой задачи содержит основные показатели, которые могут быть использованы для классификации задач (область размещения, форма объектов и др.). Область, в которой размещаются объекты, может быть различной: линия [14,16,63,95,99], плоскость [1, 41, 42, 54, 64, 70, 82, 96, 98], пространство [18, 71], граф или сеть [15,75, 76,83,84,94] и т.д. Объекты могут быть как точечными

54,64,70,82-84,94,96,98], так и протяженными, например, прямоугольными [41-43]. Рассматриваются дискретные и непрерывные задачи размещения. В дискретных задачах для размещения задано конечное число мест, в непрерывных - множество, в котором могут быть расположены объекты, не является дискретным, и определена метрика для измерения расстояний между объектами.

Дискретные задачи оптимального размещения часто бывает удобно описывать с помощью моделей целочисленного программирования. Условие целочисленности позволяет учесть, например, наличие альтернатив при размещении объектов и другие особенности задачи. Для задач целочисленного программирования разработано большое количество методов решения: ветвей и границ, отсечения, множителей Jla-гранжа, декомпозиции [8,36,39,46-48,78,79], а также метод регулярных разбиений [29-35] и др.

В последние годы для решения задач оптимизации активно разрабатываются алгоритмы локальной оптимизации, а также подходы, основанные на аналогиях с природой (генетические алгоритмы, имитация отжига, алгоритмы муравьиной колонии и др.) [4,12,13,37,65,72,73, 85,90,92,97].

Рассмотрим обобщенную задачу Вебера [27,44,54,81,98]. Математически задача формулируется следующим образом. Задано т фиксированных объектов, размещенных в точках vl,.,vm метрического пространства. Требуется разместить п новых объектов в этом же пространстве. Паре новых объектов (j, к) ставится в соответствие удельная стоимость связи vjk, l<j<k<n,db паре фиксированного и нового объектов (г, j) - стоимость W{j, 1 < г < ш, 1 < j < п. Пусть d(x,y) - расстояние между точками х и у метрического пространства. Необходимо найти набор X = (ж1,.,хп) точек для размещения новых объектов, чтобы суммарная стоимость связей была минимальной:

Vjkd(xj,xk)+ J2 Y1 Wijd{v\xj) min. l<j<k<n 1 <i<m 1 <j<n X

Отметим, что в указанной задаче нет ограничений на взаимное расположение объектов. В качестве метрического пространства может рассматриваться, например, плоскость с Евклидовой [82] или прямоугольной [54,64,96] метриками. В случае прямоугольной метрики обычным приемом является разбиение задачи на две однотипные независимые подзадачи по координатам. Каждая из них представляет собой одномерную задачу Вебера. Для решения последней используются потоковые алгоритмы: нахождения максимального потока [54], потока минимальной стоимости [64] или минимального разреза [96].

В работе [52] рассматривался вариант задачи Вебера на плоскости, в которой заданы не только точки "притяжения" для размещаемых объектов, но также точки "отталкивания". Такая задача является невыпуклой, для ее решения применялся метод, основанный на необходимых и достаточных условиях глобального экстремума.

Следуя классификации задач размещения, данной в [66], мы будем называть задачу минимизации суммарной стоимости связей между объектами минисуммной задачей. В рамках данной работы основное внимание мы будем уделять минисуммным задачам с ограничениями на максимальные расстояния между объектами.

Сформулированная ранее задача Вебера относится к непрерывным задачам. Рассматриваются также варианты задачи, в которых для объектов заданы возможные места установки (дискретная постановка). Обозначим через a(j) номер места размещения j-го нового объекта. Пусть d(i,j) - расстояние между местами г и j размещения объектов. Задача состоит в определении вектора размещений a = (a(l),., a(n)), минимизирующего суммарную стоимость связей между объектами:

Е vjkd(a(j),a(k))+ £ £ u>ijd(i,a(j))min. l<j<k<n 1 <i<m 1 <j<n

Такие задачи называются также задачами размещения с квадратичной целевой функцией [27].

Задача Вебера исследовалась в работах А.В. Панюкова [41-43,94]. В работе [44] показано, что задача Вебера в общем случае является iVP-трудной [10].

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

Задачи размещения часто сводятся к минимизации взвешенной суммы расстояний, как это было выше, или минимизации максимального взвешенного расстояния между объектами [27]. К последнему типу задач относится минимаксная задача размещения. Эти задачи рассматривались на плоскости с прямоугольной метрикой [68] и на древовидной сети [69,75,76]. Для каждой пары объектов могут быть заданы максимальные расстояния [68,69,75].

Критерием оптимального размещения новых объектов может быть минимум суммы взвешенных расстояний от фиксированного объекта до ближайшего размещенного объекта. Такая задача называется задачей о р-медиане [40,70,84]. Обозначим искомое множество размещения новых объектов через Хр = {х\,.,хр}. Пусть расстояние между фиксированным объектом в точке Vi, 1 < i < т и размещаемыми объектами определяется выражением d(vi,Xp) = min d(vi,Xj). i <j<p

Обозначим через w(vi) вес соответствующего фиксированного объекта. Тогда задачу о р-медиане можно сформулировать следующим образом: найти множество точек Хр (^-медиану), минимизирующее функционал

J2 w(vi)d(vi,Xp).

1 <i<m

Если в качестве критерия размещения выбирается минимум максимального взвешенного расстояния от фиксированного объекта до ближайшего нового объекта, то такая задача называется задачей о р-центре [40,67,70,83]. Множество точек Хр называется р-центром, если функционал max w(vi)d(vi,Xp) l<i<m на этом множестве достигает минимума.

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

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

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

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

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

Для проверки совместности ограничений на максимальные расстояния в статье [76] вводятся условия отделимости. Указанные условия являются критерием существования размещения на древовидной сети, удовлетворяющего ограничениям на максимальные расстояния. С их помощью построен алгоритм решения минимаксной задачи размещения на древовидной сети без ограничений на максимальные расстояния. В статье [75] эти идеи получили дальнейшее развитие, построено несколько полиномиальных алгоритмов для получения оптимального решения задачи на древовидной сети, основанных на бинарном поиске по упорядоченным значениям целевой функции.

Нами предлагается алгоритм, в котором используются идеи из статьи [75]. В нем при бинарном поиске производится проверка не одного значения целевой функции, а некоторого интервала значений, границы которого вычисляются с применением теории двойственности в линейном программировании (ЛП) [53]. Это позволяет находить оптимальное размещение в случае, когда оптимальное значение целевой функции попадает в указанный интервал.

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

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

Во второй главе изучаются минимаксные и минисуммные задачи размещения объектов на произвольных сетях. Постановкам этих задач на плоскости и деревьях посвящено значительное количество публикаций, для их решения предлагаются полиномиальные алгоритмы [45,54,64,75,76,96]. В случае произвольной сети ситуация иная, указанные задачи являются iVP-трудными. Поэтому здесь основное внимание уделяется алгоритмам ветвей и границ, в которых при построении оценок используется теория, разработанная для задач на древовидных сетях.

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

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

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

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

Предлагаются алгоритмы последовательного одиночного размещения [1,5,6,50], подобные методы часто применяются на практике. Согласно идее метода, объекты упорядочиваются в соответствии с некоторым критерием, а затем последовательно размещаются наилучшим образом с соблюдением заданных ограничений.

Описывается общая схема генетического алгоритма [13,37,73,97], который относится к широкому классу эволюционных стратегии, основанных на принципе моделирования процесса биологической эволюции. Предлагается несколько вариантов генетического алгоритма для решения минимаксных и минисуммных задач размещения.

Широко применяются и хорошо зарекомендовали себя для решения задач оптимизации различные методы локального поиска [37,67]. Приводится описание общей схемы алгоритма поиска с запретами [37,90]. Предлагаются варианты реализации этого алгоритма для решения минимаксных и минисуммных задач размещения.

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

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

Основные результаты работы опубликованы в работах [19-24,55-60, 100-102] и докладывались на XI Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999), Symposium on Operations Research (Магдебург, Германия, 1999), международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), научной молодежной конференции "Молодые ученые на рубеже третьего тысячелетия" (Омск, 2001), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002), International Conference on Operations Research (Клагенфурт, Австрия, 2002), 12-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международном семинаре "Discrete Optimization Methods in Production and Logistics" (Омск-Иркутск, 2004), a также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" в Омском филиале Института математики им. C.JI. Соболева СО РАН. щ Автор благодарит научного руководителя Колоколова А.А., а также

Забудского Г.Г. за полезные советы, внимание и поддержку при выполнении данной работы.

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

1. Предложены достаточные условия оптимальности решения для непрерывной минимаксной задачи на древовидной сети с ограничениями на максимальные расстояния. Построен полиномиальный алгоритм решения дискретного варианта задачи.

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

3. Доказано, что задача определения совместности ограничений на максимальные расстояния в случае размещения объектов в вершинах сети, а также дискретная минимаксная задача оптимального размещения на произвольной сети являются ./VP-трудными.

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

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

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

Заключение

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

1. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем // М.: Радио и связь. 1985. -200 с.

2. Агеев А.А. Графы, матрицы и простейшая задача размещения // Управляемые системы. Новосибирск, 1989. - Вып. 29. - С.3-10.

3. Агеев А.А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений // Материалы конференции. Новосибирск, 1998. - С.4-10.

4. Александров Д.А., Кочетов Ю.А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Материалы конференции. Новосибирск, 1998. - С.106.

5. Ахмедов И.С., Сигал И.Х. Задача компоновки схемы генплана промпредприятий и некоторые подходы к ее решению // ВЦ АН СССР. М., 1983. - № 270. - 57 с.

6. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. // Львов: Вища школа. Изд-во Львовского ун-та, 1981. 168 с.

7. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации // Новосибирск, 1978. 333 с.

8. Гимади Э.Х. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Управляемые системы. Новосибирск, 1987. - Вып. 27. - С.12-27.

9. Гончаров Е.Н., Кочетов Ю.А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения // Труды XI междунар. Байкальской школы-семинара "Методы по-тимизации и их приложения". Иркутск, 1998. - С.121-124.

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи // М.: Мир, 1982. 416 с.

11. Долгий А.Б., Еремеев А.В., Колоколов А.А., Сигаев B.C. Оптимизация размещения буферных устройств в автоматических линиях // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения". Иркутск, 2001. - Т. 1. - С.150-155.

12. Еремеев А.В. Генетический алгоритм для задачи о минимальном покрытии // Материалы конф. Новосибирск, 1998. - С.21-24.

13. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. 2000. - Т. 7, N 1. -С.47-60.

14. Забудский Г.Г. Задачи оптимального размещения объектов на линии с минимально допустимыми расстояниями. // Препринт АН СССР. Новосибирск, 1990. - 32 с.

15. Забудский Г.Г. О некоторых задачах размещения на графах // Труды XI Междунар. Байкальской школы-семинара. Иркутск, 1998. - С.135-138.

16. Забудский Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. Новосибирск, 1990. - Вып.30. - С.35-45.

17. Забудский Г.Г., Колмычевская Н.В., Леванова Т.В. Оптимизация размещения технологического оборудования на генплане // Тез. симп. "Системы программного обеспечения решения задач оптимального планирования". М., 1988. - С.148.

18. Забудский Г.Г., Нежинский И.В. Решение задачи размещения в евклидовом пространстве с запрещенной областью // Вестн. Омского ун-та. 1999. - JY* 2. - С.17-19.

19. Забудский Г.Г., Филимонов Д.В. Алгоритм решения минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Омский науч. вест. 1999. - Вып. 9. - С.37-40.

20. Забудский Г.Г., Филимонов Д.В. Алгоритмы решения задач размещения на деревьях с ограничениями на максимальные расстояния / / Материалы международной конференции "Дискретный анализ и исследование операций". Новосибирск, 2000. - С.165.

21. Забудский Г.Г., Филимонов Д.В. О минимаксной и минисуммной задачах размещения на сетях // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения". Иркутск, 2001. - Т. 1. - С.150-155.

22. Забудский Г.Г., Филимонов Д.В. Решение дискретной минимаксной задачи размещения на сети // Изв. вузов. Математика. -2004. № 5. - С.ЗЗ-Зб.

23. Забудский Г.Г., Филимонов Д.В. Решение дискретных минимаксных и минисуммных задач размещения на сетях // Материалы российской конференции "Дискретный анализ и исследование операций". Новосибирск, 2002. - С.210.

24. Забудский Г.Г., Филимонов Д.В. Решение минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Материалы XI Всероссийской конференции "Математическое программирование и приложения". Екатеринбург, 1999. - С.114.

25. Иванова С.Д., Филимонов Д.В. Алгоритмы для решения задачи о вершинном р-центре на сетях // Молодежь III тысячелетия: Региональная научная студенческая конференция. Тез. докл. -Омск, 2001. С.12-13.

26. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супер модулярной функции // Дискретный анализ и исследование операций. Сер. 1. 1998. - Т. 5, № 4. - С.45-60.

27. Исследование операций // В 2-х томах. Пер. с англ. Под редакцией Моудера Дж., Элмаграби С. М.: Мир, 1981. - 677 с.

28. Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // ДАН СССР. 1974 - Т. 215, № 1. - С.49-52.

29. Колоколов А.А. Выпуклые множества с альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры: Межвуз. сб. научн. труд. ОмГУ. Омск, 1987.- С.144-150.

30. Колоколов А.А. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. - 75 с.

31. Колоколов А.А. Применение регулярных разбиений в целочисленном программировании // Изв. вузов. Математика. 1993. - № 12.- С.11-30.

32. Колоколов А.А. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемые системы. Новосибирск, 1981. - Вып. 21. - С.18-25.

33. Колоколов А.А. Регулярные разбиения в целочисленном программировании // В сб. научн. тр. "Методы решения и анализа задач дискретной оптимизации". Под ред. А.А.Колоколова. Омск, 1992. - С.67-93.

34. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исслед. операций. Новосибирск, 1994. - Т. 1, № 2. - С.18-39.

35. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения II Вестник Омского ун-та. Омск, 1996. - JV2 1.- С.21-23.

36. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование // М.: Наука, 1969. 386 с.

37. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // В сб. лекций "Дискретная математика и приложения". Москва, 2001. - С.84-117.

38. Леванова Т.В. Двойственный жадный алгоритм для задачи о р-медиане и ее обобщений // Препринт 98-4. Омск: Омский госуниверситет, 1998. - 13 с.

39. Леванова Т.В. Исследование декомпозиционных алгоритмов для решения некоторых задач размещения // Тез. докл. конф. "Математическое программирование и приложения". Екатеринбург, 1997. - С.144-145.

40. Майника Э. Алгоритмы оптимизации на сетях и графах // Пер. с англ. М.: Мир, 1981. - 323 с.

41. Панюков А.В. Алгоритмы локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети // Изв. АН СССР, Техн. киб-ка. 1981. - № 6. - С.180-184.

42. Панюков А.В. Алгоритмы размещения прямоугольных объектов // Матер. Всес. конф. "Декомпозиция и координация в сложных системах". Челябинск. - 1987. - С.80-89.

43. Панюков А.В. Декомпозиция задачи размещения прямоугольных объектов // Декомпозиция и координация в сложных системах. Тез. докл. Всес. конф. Челябинск, 1986. - С.53-58.

44. Панюков А.В. Квазицелочисленностъ релаксационного многогранника задачи Вебера // Методы оптимизации и их приложения. Труды XI международной Байкальской школы-семинара. -Иркутск, 1998. С.171-174.

45. Панюков А.В., Пельцвергер Б.В. Оптимальное размещение дерева в конечном множестве // Журнал вычислительной математики и математической физики. 1988. - Т. 28. - С.618-620.

46. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность // Пер. с англ. М.: Мир, 1985. - 512 с.

47. Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности // Труды XI международной Байкальской школы-семинара. Иркутск, 1998. - С.175-178.

48. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации // Киев: Наукова думка, 1988. -472 с.

49. Стоян Ю.Г., Кулиш Е.Н. Автоматизация проектирования компоновки оборудования летательных аппаратов. М.: Машиностроение. - 1984. - 192 с.

50. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: На-укова думка, 1986. - 268 с.

51. Стрекаловский А.С., Васильев И.Л. Об одном подходе к решению квадратичной задачи о назначениях // Материалы XI Всероссийской конференции "Математическое программирование и приложения". Екатеринбург, 1999. - С.253-254.

52. Стрекаловский А.С., Васильева A.M. Поиск глобального решения в задаче размещения // Материалы международной конференции "Дискретный анализ и исследование операций". Новосибирск, 2000. - С.121.

53. Таха X. Введение в исследование операций М.: Издат. дом "Вильяме", 2001. - 912 с.

54. Трубин В.А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой j j Кибернетика. 1978. - № 6. - С.67-70.

55. Филимонов Д.В. Алгоритм размещения объектов на дереве с минимаксным критерием и максимальными расстояниями // Материалы научной молодежной конференции "Молодые ученые на рубеже третьего тысячелетия". Омск, 2001. - С.84.

56. Филимонов Д.В. О способах построения нижних оценок для задач размещения взаимосвязанных объектов на сетях // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2003. - С.111.

57. Филимонов Д.В. Решение дискретной минимаксной задачи размещения на древовидной сети // Материалы ежегодного научного семинара аспирантов и студентов-выпускников "Под знаком £". Омск, 2003. - С.58-61.

58. Филимонов Д.В. Решение минисуммной задачи размещения на линии с ограничениями на максимальные расстояния // Материалы Российской конференции "Дискретный анализ и исследование операций". Новосибирск, 2004. - С.170.

59. Филимонов Д.В. Эвристические алгоритмы решения минимаксных и минисуммных задач размещения на сетях // Препринт. -Омск: Омск, госуниверситет, 2003. 15 с.

60. Филимонов Д.В., Забудский Г.Г. Некоторые алгоритмы размещения взаимосвязанных объектов на сетях // Материалы 12-й Всероссийской конференции "Математическое программирование и приложения". Екатеринбург, 2003. - С.235.

61. Форд JI.P., Фалкерсон Д.Р. Потоки в сетях // М.: Мир, 1966.

62. Хамисов О.В. Поиск глобального минимума функций, имеющих выпуклые и вогнутые опорные функции // Материалы XI Всероссийской конференции "Математическое программирование и приложения". Екатеринбург, 1999. - С.272-273.

63. Adolfson D., Ни Т.С. Optimal Linear Ordering// SIAM Jornal on Applied Mathematics. 1973. - V. 25, № 3. - P.403-423.

64. Cabot V., Francis R.L., Stary M.A. A network flow solution to a rectilinear distance facility location problem // AIIE Trans. 2. 1970.- P.132-141.

65. Cerny V. A thermodinamical approach to the traveling salesman problem: an efficient simulated algorithm // J. of Optimization Theory an Applic. 1985. - № 45. - P.41-55.

66. Chhajed D., Francis R.L., Lowe T.J. Contributions of operation research to location analysis. Invited review // Location Science. 1993.- Vol. 1, № 4. P.263-287.

67. Daskin M. A new approach to solving the vertex p-center problem to optimality: algorithm and computational results // Communications of the Operational Research Society of Japan. 2000. - № 45(9). -P.428-436.

68. Dearing P.M., Francis R.L. A network flow solution to a multifacility minimax location problem involving rectilinear distances // Transportation Science. 1974. - Vol. 8 - P. 126-141.

69. Dearing P.M., Francis R.L., Lowe T.J. Convex location problems on tree networks // Oper. Res. 1976. - № 24(4).

70. Discrete Location Theory // Ed. by Mirchamdani P.B., Franscis R.L.- John Wiley & Sons, Inc., 1990.

71. Elzinga J., Hearn D., Randolph W.D. Minimax multifacility location problem with euclidean distances // Transportation Science. 1976.- Vol. 10, № 4.

72. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem // Proc. of Operations Research (OR'98). Springer Verlag, 1999. - P.175-181.

73. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the 1st International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. - P.297-303.

74. Erkut E., Francis R.L., Lowe T.J., Tamir A. Equivalent mathematical programming formulations of monotonic tree network location problems // Oper. Res. 1989. - № 37(3). - P.447-461.

75. Erkut E., Francis R.L., Tamir A. Distance-constrained multifacility minimax location problems on tree network j j Networks. 1992. -№ 22. - P.37-54.

76. Francis R.L., Lowe T.J., Ratliff D.H. Distance constraints for tree network multifacility location problems // Oper. Res. 1978. - № 26(4). - P.570-595.

77. Gimadi E.Kh. The asimptotical Performance of Approximation Solution for some Simple Plant Location Problems // Abstracts of Iter-national Conference on Operations Research, Zurich. 1998. - P.49.

78. Gomory R.E. All Integer Programming Algorithm// Industrial Sheduling. Ed. Muth J.F., Thompson G.l. Prentice-Hall, Englewoods Cliffs. 1963. - P. 193-206.

79. Gomory R.E. Outline of an Algorithm for integer Solution to Linear Programme// Bull. Amer. Math. Soc. 1958. - V. 65, № 5.- P.275-278.

80. Hochbaum D.S. Heurustics for the fixed cost median problem // Math. Progr. 1982. - № 22. - P. 148-162.

81. Jacobsen S.K. An algorithm for the minimax Weber problem // European J. Oper. Res. 1981. - № 6. - P.144-148.

82. Kacprzyk J., Stanczak W. A discrete approximation of the Weber problem with euclidean distance // Applicationes Mathematicae. -1984. XVIII. 2. - P.257-270.

83. Kariv O., Hakimi S.L. An algorithmic approach to network location problems. I: The p-centers // SIAM J. Appl. Math. 1979. - Vol. 37, № 3. - P.513-538.

84. Kariv O., Hakimi S.L. An algorithmic approach to network location problems. II: The p-medians // SIAM J. Appl. Math. 1979.- Vol. 37, № 3.

85. Kirkpatrik S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. - № 220. - P.671-680.

86. Kolen A. Location problems on trees and in rectilinear plane // Stitchting Mathematish Centrum. Amsterdam, 1982.

87. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On Hybrid L-class Enumeration and Genetic Algorithm for Set Covering Problem //15.th Conference of the International Federation of Operational Research Societies (IFORS'99): Abstr. Pekin, 1999. - P.117.

88. Koopmans T.C., Beckmann M.J. Assigment problems and the location of economic activites // Econometrica. 1957. - Vol. 25, № 1.- P.53-76.

89. Krarup J., Pruzan P.M. The simple plant location problem: survey and synthesis // European J. Oper. Res. 1983. - V. 12, № 1. -P. 36-81.

90. Laguna M., Glover F. Bandwing Packing: A Tabu Search Approach // Managment Science. 1993. - Vol. 39, № 4.- P.492-500.

91. Levanova T.V. Some decomposition algorithms for plant location problem // Symp. on Operations Research (SOR99). Magdeburg, 1999. - P.76.

92. Lundy M., Mees A. Convergence of an annealing algorithm // Math. Progr. 1986. - № 34. - P.lll-124.

93. Malhotra V.M., Kumar M.P., Maheshwari S.N. An 0(\V3\) Algorithm for Finding Maximum Flows in Networks // Inf. Proc. Letters. 1978.- V. 7, № 6. P.277-278.

94. Panyukov A.V., Pelzwerger B.V. Polinomial algorithns to finite Veber problem for a tree network // Journal of Computational and Applied Mathematics. 1991. - № 35. - P.291-296.

95. Picard J.C., Queranne M. On the One-Dimensional Space Allocation Problem // Oper. Res. 1981. - Vol. 29. - P.371-391.

96. Picard J.C., Ratliff D.H. A cut approach to the rectilinear distance facility location problem // Oper. Res. 1978. - № 26(3). - P.422-433.

97. Reeves C.R. Genetic Algorithms for the Operations Researcher // INFORMS Journal on Computing. 1997. - V. 9, № 3. - P.231-250.

98. Wesolowsky G.O. The Weber problem: history and perspectives // Location Science. 1993. - Vol. 1, № 1. - P.5-23.

99. Zabudsky G.G. Some Resalts for the One-Dimensional Space Allocation Problem // Symp. on Operations Research (SOR99). Jena, 1997. - P.50.

100. Zabudsky G.G., Filimonov D.V. An algorithm for minimax location problem on tree with maximal distances // Proc. of the Second International Workshop "Discrete Optimization Methods in Production and Logistics" (DOM2004). Omsk-Irkutsk, 2004. - P.81-85.

101. Zabudsky G.G., Filimonov D.V. An algorithm for the location problem on tree with maximal distances // Symp. on Operations Research (SOR99). Magdeburg, 1999. - P.115.

102. Zabudsky G.G., Filimonov D.V. Solving discrete minimax location problem on networks // International Conference on Operations Research. Klagenfurt, 2002. - P.153.