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

• Филимонов, Дмитрий Валерьевич
• кандидат физико-математических наук
• 2004

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

Введение

Глава 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. Разработаны эвристические алгоритмы: последовательного одиночного размещения, генетический алгоритм и поиск с запретами для решения указанных выше задач. Предложенные алгоритмы реализованы, проведено их экспериментальное сравнение, которое показало эффективность разработанных алгоритмов.

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Филимонов, Дмитрий Валерьевич, 2004 год

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.