Модели и методы оптимального размещения взаимосвязанных объектов на дискретных множествах тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Забудский, Геннадий Григорьевич

• Забудский, Геннадий Григорьевич
• доктор физико-математических наук
• 2006

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

Введение

Глава 1. Задачи оптимального линейного упорядочения

1.1 Полиномиальные алгоритмы для специальных ориентированных графов

1.2 Гибридный алгоритм для произвольного ориентированного графа.

1.3 Полиномиальный алгоритм для двухполюсного неориентированного графа.

Глава 2. Размещение на линии с минимально допустимыми расстояниями.

2.1 Постановки задач и их свойства.

2.2 Фиксированный порядок расположения объектов

2.3 Модели целочисленного линейного программирования

2.4 Анализ L-структуры многогранных множеств

2.5 Алгоритмы решения.

Глава 3. Размещение на сетях.

3.1 Решение минимаксной задачи Вебера на дереве

3.2 Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей.

3.3 Алгоритмы решения задач Вебера на общих сетях

3.4 Полиномиальные алгоритмы для задач с взаимно однозначным размещением.

3.5 Динамическое программирование для квадратичной задачи о назначении на дереве

3.6 Свойства многогранника задачи о р-медиане

Глава 4. Размещение на плоскости и дискретных множествах.

4.1 Модели целочисленного программирования для задач на плоскости с запрещенными зонами.

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

4.3 Размещение объекта с учетом запрещенной зоны и евклидовой метрикой.

4.4 Построение оценок суммарной стоимости связей

Глава 5. Решение прикладных задач.

5.1 Построение моделей.

5.2 Модель оптимального размещения модулей швейного производства.

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

Введение диссертации (часть автореферата) на тему «Модели и методы оптимального размещения взаимосвязанных объектов на дискретных множествах»

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

В настоящее время существенные успехи достигнуты в изучении структуры, сложности и устойчивости задач оптимизации, разработке методов их решения, программной реализации алгоритмов [3,4,11,16, 18,21,22,57,60,66,68,71,77,78,83,85,86,96,99,102,103,112].

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

Среди задач оптимального размещения можно выделить два класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения. Отличие состоит в том, что в задачах первого класса необходимо найти места расположения объектов, между которыми имеются некоторые связи (не обязательно между всеми). В задачах второго класса связи устанавливаются в результате их решения. Например, при размещении пунктов обслуживания к ним прикрепляются клиенты (устанавливаются связи). Классическими представителями первого класса являются задача Вебера и квадратичная задача о назначении. Разработкой этой проблематики занимались Ахмедов И.С., Демиденко В.А., Жак С.В., Зинченко А.Б, Иорданский М.А., Панюков А.В., Сергеев С.И., Сигал И.Х., Стоян Ю.Г., Трубин В.А., Яковлев С.В., Adolfson D., Beckmann M.J., Burcard R.E., Francis R.L., Koopmans T.C., Tamir A., Wesolowsky G.O. и другие [б, 24, 55, 80, 95,101,105,114,117,118,126,138,152]. Наиболее известные задачи второго класса: простейшая задача размещения, задачи о р-медиане и о р-центре. Заметный вклад в их исследование внесли Агеев А.А., Бахтин А.Е., Береснев В.Л., Гимади Э.Х., Глебов Н.И., Дементьев В.Т., Емеличев В.А., Ильев В.П., Колоколов А.А., Кочетов Ю.А., Леванова Т.В., Хачатуров В.P., Hakimi S.L., Kariv О., Krarup J., Pruzan P.M. [2,9,11,18,54,64,66,110,134,139] и ряд других авторов.

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

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

Отметим, что многие известные оптимизационные задачи можно рассматривать как варианты задачи Вебера. На плоскости задано т точек Pi,i G / = {l,.,m} и требуется разместить на ней п новых точек Xj,j G J = {l,.,n}. Каждой паре точек (Pi,Xj) ставится в соответствие число wij > 0, i G /, j G «/, а каждой паре (Xj,Xk) -число ujk > 0, j < k,j,k G J. Числа W{j и Ujk можно интерпретировать как величины потоков, циркулирующих между парами точек (Р;, Xj) и (Xj, Хк) соответственно. Для измерения расстояний между точками используется некоторая метрика р(■, ■). Необходимо найти размещение точек Xj,j G J таким образом, чтобы достигался минимум функции

Е Е ЩР(Рг, Xj) + £ Е Ujkp(Xj,Xk). iei jeJ jeJ,j<n keJ,k>j

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

Если известны возможные места установки объектов, т.е. рассматривается дискретная постановка задачи, причем на каждом месте может быть не более одного объекта и отсутствуют размещенные объекты, то задача размещения становится квадратичной задачей о назначении в виде Купманса-Бэкмана [138]. При условии Ujk = 0 для j < k,j,k G J задача Вебера преобразуется в линейную задачу о назначениях.

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

Понятие "объект" трактуется достаточно широко. При проектировании генеральных планов предприятий объекты - это здания и сооружения [6,24,51]; при создании робототехнологических комплексов - единицы технологического оборудования [79]. Если проектируется печатная плата, то объектами являются элементы печатного монтажа, например, микросхемы [1,7]. При расположении пунктов обслуживания объекты - это станции скорой или технической помощи, магазины, склады и т.д.

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

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

В зависимости от поставленных целей рассматриваются различные критерии оценки качества получаемых размещений. Например, для нефтехимических предприятий стоимость трубопроводных связей может составлять около 25 процентов от общих капитальных затрат на строительство. Поэтому при размещении оборудования такого предприятия на заданной строительной площадке можно минимизировать суммарную стоимость трубопроводных связей [6,80]. Достаточно часто используются критерии минимума площади, занимаемой размещенными объектами [6], и минимума наиболее дорогой по стоимости (максимальной) связи [132]. При проектировании печатных плат критерии размещения направлены, в основном, на облегчение выполнения последующей трассировки. Это может быть, например, минимум числа пересечений проводников [1, 7]. В последнее время изучаются задачи размещения, в которых расстояние от размещаемого объекта до ближайшего фиксированного должно быть максимально возможным. Такие задачи возникают, например, при размещении опасных (вредных) производств, либо, наоборот, требующих экологической чистоты [136].

Одной из основных характеристик рассматриваемых задач размещения является структура области, в которой производится размещение, например, она может быть непрерывной или дискретной. Размерность непрерывной области может быть различной: одномерной -линия [119,142], двумерной - плоскость и т.д [5,80,132]. Существенное значение для анализа и разработки методов решения таких задач имеет метрика, в которой измеряются расстояния между объектами. Причем в одной модели могут использоваться различные метрики. Например, минимально допустимые расстояния между объектами измеряются в евклидовой метрике, а длина связей - в прямоугольной метрике. В дискретных моделях указывается конечное число мест (позиций) для установки объектов [14,55,58,82,117,125]. Это могут быть, например, произвольные точки с заданными расстояниями между ними, либо точки, находящиеся на некоторой сети.

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

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

Методы решения задач оптимального размещения определяются характеристиками используемой модели. Как правило, такие задачи являются Л^Р-трудными, но для отдельных классов задач известны полиномиальные алгоритмы.

Задача размещения взаимосвязанных объектов в целые точки на линии (не более чем по одному в каждую) с критерием минимума суммарной стоимости связей (задача оптимального линейного упорядочения) iVP-трудна, если структура связей между объектами представлена с помощью произвольного реберно-взвешенного графа. Вершины такого графа соответствуют объектам, а ребра - связям между ними. Эта задача полиномиально разрешима, когда указанная структура является корневым деревом [114]. Для задачи оптимальной нумерации вершин графа, которая является частным случаем задачи оптимального линейного упорядочения (одинаковые веса ребер), известен полиномиальный алгоритм для неориентированного дерева [14] и частных случаев дерева, например, звезд и т.д. [55,56].

Алгоритмы решения задачи размещения разногабаритных объектов на линии (одномерная задача размещения) описаны в работах [145,150].

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

Задачам оптимального размещения взаимосвязанных объектов на сетях посвящены работы [122,126-128]. Много внимания уделяется рассмотрению задач на древовидных сетях. Задачи Вебера с минимаксным критерием (минимум максимальной связи) и критерием минимума суммарной стоимости связей с ограничениями на максимально допустимые расстояния между объектами сводятся к задачам линейного программирования (ЛП) [126]. Для минимаксной задачи с учетом ее специфики предложены более эффективные алгоритмы [127].

Много внимания уделяется методам решения задач размещения на плоскости. Задачи Вебера на плоскости с прямоугольной метрикой с критерием минимума суммарной стоимости связей и минимаксным критерием сведены к решению задач ЛП [5,80,105,131,132,143,146]. Для размещения прямоугольных объектов предложены алгоритмы локальной оптимизации [80], ветвей и границ [98], декомпозиции Бен-дерса [23]. Алгоритм ветвей и границ для задачи размещения точечных объектов (опасных производств) с критерием максимума минимальных расстояний до фиксированных объектов описан в [115], а в [136] приведены алгоритмы решения задач с указанным критерием, учитывающие геометрию прямоугольников. Комбинаторные алгоритмы для решения задач размещения, в которых учитываются барьеры при прокладке связей между объектами, предложены в [130]. Разработаны также эвристические алгоритмы для различных постановок задач размещения на плоскости [1,6,89,101].

В случае взаимно однозначного размещения объектов на дискретном множестве позиций описаны модели комбинаторного типа и целочисленного программирования (ЦП). Для решения таких задач разработаны алгоритмы ветвей и границ, динамического программирования, эвристические алгоритмы, выделены полиномиально разрешимые варианты для специальных матриц расстояний между позициями и связей между объектами [93,102,104,117,123,125,138,141].

Для решения задач второго класса (размещения-распределения), например, простейшей задачи размещения и задачи о р-медиане, часто используются модели ЦП. В [11,64,66] предложены алгоритмы: ветвей и границ, в частности, с использованием релаксации Лагранжа; перебора L-классов; эвристические и другие. При решении задачи о р-центре, в основном, применяются комбинаторные модели.

Из приведенного выше обзора следует, что разнообразие постановок задач размещения взаимосвязанных объектов и методов их решения весьма велико. Вместе с тем, не было достаточно глубокого и цельного исследования указанного класса задач на основе моделей и методов комбинаторной оптимизации. Слабо были изучены квадратичные задачи о назначении на сетях и на произвольных множествах с ограничениями на допустимые расстояния между объектами; задачи Вебера на плоскости и сетях с различными ограничениями, например, запрещенными зонами. Кроме того, недостаточно внимания уделялось разработке моделей ЦП для рассматриваемого класса задач, которые позволяют применять для их исследования и решения аппарат целочисленной оптимизации, в том числе, метод регулярных разбиений, предложенный Колоколовым А.А. [25,50,61-64].

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

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

Разработанные алгоритмы реализованы на ЭВМ, проведены экспериментальные исследования. Полученные результаты используются в научно-исследовательской работе Омского филиала Института математики СО РАН, в учебном процессе в Омском государственном университете и Омском государственном институте сервиса. Построенная модель оптимального размещения технологического оборудования швейного производства применяется в САПР в ООО "Авангард - 2" г. Кургана.

Дадим краткое изложение основных результатов диссертации.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Забудский, Геннадий Григорьевич

Заключение

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

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

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

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Забудский, Геннадий Григорьевич, 2006 год

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

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

3. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. - 248 с.

4. Антипин А.С. Равновесное программирование: методы градиентного типа, // Автоматика и телемеханика. 1997. - № 8.- С. 125-137.

5. Аоки М. Введение в методы оптимизации. М. : Наука, 1977. -344 с.

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

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

8. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Физматлит, 2004. - 240 с.

9. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. - 160 с.

10. Береснев B.JI., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. - 333 с.

11. И. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

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

13. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики.- М.:Наука, 1975. Вып. 31. - С. 35-43.

14. Гольдберг М.К., Клипнер И.А. Алгоритм минимальной нумерации вершин дерева // Сообщение АН ГрССР, 1976. Т. 81, № 3. - С. 553-556.

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

16. Девятерикова М.В., Колоколов А.А., Анализ устойчивости некоторых алгоритмов дискретной оптимизации j j Автоматика и телемеханика. 2004. - № 3 - С. 48-54.

17. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. -432 с.

18. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. - 344 с.

19. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации // Изв. АН СССР Сер. Техн. кибернетика. 1982. - № 6. - С. 25-45.

20. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001. - 180 с.

21. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. - 191 с.

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

23. Жак С.В., Зинченко А.Б. Решение некоторых задач геометрического размещения модифицированным методом ветвей и границ // Математическое обеспечение АСУП: Тез.докл. 2-го Всес.сем., М.: ИЛУ, 1975. С. 27-28.

24. Жак С.В., Зинченко А.Б. Комбинаторные методы решения задачи размещения помещений в производственном здании // Автоматизация архитектурно-строительного проектирования. -Ростов на Дону, 1979. С. 87-92.

25. Заблоцкая О.А., Колоколов А.А. Вполне регулярные отсечения в булевом программировании // Управляемые системы. 1983. -Вып. 23. - С. 55-63.

26. Заблоцкая О.А., Колоколов А.А. Об одном классе двойственных дробных процессов отсечения булевого программирования // Принятие оптимальных решений в экономических системах.- Горький, 1984. С. 34-41.

27. Забудский Г.Г. Об оценках стоимости связывающей сети в некоторых задачах размещения // Дискретная оптимизация и анализ сложных систем Новосибирск: ВЦ СО АН СССР, 1989. -С. 10-25.

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

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

30. Забудский Г.Г. Задачи оптимального размещения взаимосвязанных объектов на линии // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ. - 1992. - С. 5-24.

31. Забудский Г.Г. Алгоритм решения одной задачи оптимального линейного упорядочения // Известия вузов. Математика. 1997. - № 12. - С. 73-78.

32. Забудский Г.Г. Некоторые свойства многогранника задачи о р-медиане// Вестник Омского ун-та: Изд-во ОмГУ, 1997. № 4.-С. 11-13.

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

34. Забудский Г.Г. О задаче линейного упорядочения параллельно-последовательных графов// Дискретный анализ и исследование операций. 2000. - № 1- С. 61-64.

35. Забудский Г.Г. Алгоритм решения минимаксной задачи размещения объекта на плоскости с запрещенными зонами // Автоматика и телемеханика. 2004. - № 4 - С. 93-100.

36. Забудский Г.Г. О сложности задачи размещения на линии с ограничениями на минимальные расстояния // Известия вузов. Математика. 2005. - № 12. - С. 11-14.

37. Забудский Г.Г. О минимаксной и минисуммной задачах размещения на плоскости с запрещенными областями // Тр. XIII межд. Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. - С. 455-460.

38. Забудский Г.Г. О задаче размещения объектов на линии с ограничениями на минимально допустимые расстояния // Омский научный вестник. 2005. - Вып. 3.(32) - С. 85-88.

39. За1будский Г.Г. Вычисление нижних оценок стоимости сети в задачах размещения с ограничениями на расстояния // Журнал вычислительной математики и математической физики. 2006.- Т. 46, № 2. С. 216-221.

40. Забудский Г.Г. Оптимальное размещение взаимосвязанных объектов на древовидных сетях с ограничениями на расстояния // Журнал вычислительной математики и математической физики.- 2006. Т. 46, № 3. - С. 395-400.

41. Забудский Г.Г., Бикбавов Д.Ф. Алгоритм нумерации вершин графа специального вида // Вестник Омского ун-та:Изд-во ОмГУ, 2002. № 2. - С. 14-16.

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

43. Забудский Г.Г., Легких С.А. Математическая модель оптимизации размещения гибких модулей технологического оборудованания // Сб. "Прикладная математика и информационные технологии". Омск: Изд-во ОмГТУ, 2005. - С. 20-28.

44. Забудский Г.Г., Мотовилов В.А. Гибридный алгоритм размещения ориентированного графа на линии // Вестник Омского ун-та:Изд-во ОмГУ, 2000. № 2. - С. 19-21.

45. Забудский Г.Г., Мотовилов В.А. Оптимальное размещение объектов на дереве с помощью динамического программирования // Тр. XII Байкальской междунар. конференции "Методы оптимизации и их приложения". Иркутск, 2001. - Т. 1. - С. 144-149.

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

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

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

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

50. Заикина Г.М., Колоколов А.А. Экспериментальные исследования в целочисленном программировании с применением Ь-разбиения II Дискретная оптимизация и анализ сложных систем.- Новосибирск, 1989. С. 26-55.

51. Зинченко А.Б. Локальный алгоритм для задачи компоновки // Автоматизация архитектурно-строительного проектирования промышленных предприятий. Ростов на Дону: Рост, инж.-строит. ин-т, 1986. - С. 135-141.

52. Зуев Ю.А. Комбинаторно-вероятностные и геометрические методы в пороговой логике // Дискретная математика. 1991. -Т. 3, 2. - С. 47-57 с.

53. Зуховицкий С. И., Авдеева А. И. Линейное и выпуклое программирование. М.: Наука, 1967. - 460 с.

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

55. Иорданский М.А. Задачи размещения графов 2 // Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во ГГУ, 1982. - С. 26-60.

56. Иорданский М.А. Минимальные плоские размещения деревьев // Методы дискретного анализа в решении экстремальных задач. -Новосибирск: Изд-во ИМ СО АН СССР, 1979. Вып. 33. - С.3-30.

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

58. Каледина Н.Б. Кулага А.С. Банк алгоритмов размещения графов и гиперграфов // Тез.докл. 4-го всес.сов. "Методы и программы решения оптимизационных задач на графах и сетях". -Новосибирск, 1989. Ч. 1. - С. 80-81.

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

60. Ковалев М.М. Матроиды в дискретной оптимизации. Минск: Изд-во БГУ, 1987. - 222 с.

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

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

63. Колоколов А.А., Девятерикова М.В. Анализ устойчивости L-разбиения в конечномерном пространстве // Дискретный анализ и исследование операций. Сер.2. 2000. - Т.6, № 2 - С. 47-53.

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

65. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

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

67. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.

68. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. Новосибирск: Наука, 2000. - 297 с.

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

70. Легких С.А., Забудский Г.Г., Нагорная З.Е. Автоматизация проектирования планов производственных участков и цехов швейных предприятий // Естественные и технические науки. -М.: Изд-во Спутник+, 2005. № 4. - С. 261-266.

71. Леонтьев В.К. Устойчивость в линейных дискретных задачах // Пробл. кибернетики. М.: Наука, 1979. - Вып. 35. - С. 169-184.

72. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика. 2004. - № 2. - С. 43-54.

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

74. Меламед И.П., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика 1989. - № 3. -С. 3-33.

75. Меткин Н.П., Лапин М.С., Клейменов С.А., Критский В.М. Гибкие производственные системы М.: Изд-во стандартов, 1989. - 312 с.

76. Минаков И.П., Рафалович И.И., Тамощук B.C. Использование ЭВМ при проектировании генеральных планов и объемно планировочных решений зданий промышленных предрриятий Л.: Стройиздат, 1982. - 111 с.

77. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986. - 264 с.

78. Мухачева Э.А., Мухачева А.С. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. - № 2. - С. 101-112.

79. Павловский В.Е., Прудковский С.Г. Исследованние и верификация моделей робототехнологических комплексов. / Препринт ИПМ АН СССР. М., 1986. - № 13. - 32 с.

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

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

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

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

84. Препарата Ф., Шеймос М. Вычислительная геометрия. М.: Мир, 1989. - 478 с.

85. Попков В.К. Математические модели связности. Ч. 3. Представление графов. Новосибирск: Изд-во ИВМиМГ СО РАН, 2002.- 170 с.

86. Попов Л.Д. Применение метода проекции для нахождения ап-проксимационных корней монотонных отображений // Известия вузов. Математика. 1995. - № 12. - С. 74-80.

87. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

88. Рубинштейн М.И. Об алгоритмах решения задачи о назначениях 11 Автоматика и телемеханика 1981.- № 7 - С. 145-154.

89. Рынков Л.А., Кузьмин Б.А., Эйдес А.А. Алгоритм размещения радиоэлементов разной формы // Приборы и системы управления.- 1979. № 2. - С. 1-3.

90. Сарванов В.И. О сложности минимизации линейной формы на множестве циклических подстановок // Докл. АН СССР, 1980.- Т.253, № 3. С. 533-535.

91. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. - 384 с.

92. Селютин В.А. Автоматизация проектирования топологии ВИС. М.: Радио и связь, 1983. - 112 с.

93. Сергеев С.И. Квадратичная задача назначения I // Автоматика и телемеханика. 1999. - № 8 - С. 127-147.

94. Сергеев С.И. Квадратичная задача назначения //// Автоматика и телемеханика. 1999. - № 9 - С. 137-143.

95. Сергеев С.И. Улучшенный алгоритм решения квадратичной задачи назначения // Автоматика и телемеханика. 2004. - № 12- С. 49-63.

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

97. Сигал И.Х., Иванова А.П. Введение в прикладное и дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2002. - 240 с.

98. Степанов В.П. Задача размещения модулей при проектировании печатных плат // Изв. АН СССР. Сер. Техн. кибернетика. -1979, № 2. - С. 212-216.

99. Срочко В.А. Численные метоы. Иркутск: Изд-во ИГУ. - 2003.- 168 с.

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

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

102. Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. - 356 с.

103. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний: одностадийные системы М.: Наука, 1984. - 384 с.

104. Теория и методы автоматизации проектирования вычислительных систем. М.: Мир, 1977. - 284 с.

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

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

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

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

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

110. Хачатуров В.Р. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. -М.: Наука, 2000. 360 с.

111. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. - 520 с.

112. Шевченко В.Н. Выпуклые многогранные конусы, системы сравнений и правильные отсечения в целочисленном программировании // Комбинаторные алгебраические методы в прикладной математике. Горький: Изд-во ГГУ, 1979. - С. 109-119.

113. ИЗ. Юдин Д.В., Голыптейн Е.Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1969. - 424 с.

114. Adolfson D., Ни T.C. Optimal linear ordering // SIAM Journal on Applied Mathematics. 1973. - Vol. 25. - № 3. - P. 403-423.

115. Brimberg J., Mehrez A. Multi-facility location using a maximin criterion and rectangular distances // Location Science. 1994 - Vol. 2, № 1. - P. 11-19.

116. Burcard R.E., Derigs U. Assignment and mathing problems solution methods with Fortrans programms // Lecture Notes Econ. and Math. Systems: Springer Berlin. Heildelberg New York. - 1980. - Vol. 184.- 148 p.

117. Burcard R.E., Stratmamm K. Numerical investigations on quadratic assignment problems // Nav.Res.Log.Quadratic Quart. 1978. -Vol.25, № 1.- P. 129-148.

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

119. Chan A.W., Francis R.L. Some layout problems on the line with in-terdistance constraints and costs // Oper. Res. 1979. - Vol. 27, JYJ 5.- P. 952-971.

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

121. DearingP.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.

122. Dearing P.M., Francis R.L., Lowe T.J. Convex location problems on tree networks // Oper. Res. 1976. - Vol. 24, № 4. - P. 628-642.

123. Discrete Location Theory / Ed. by Mirchamdani P.B., Francis R.L. -John Wiley k, Sons, Inc., 1990. 556 p.

124. Elshafei A.N. Hospital layout as a quadratic assignment problem // Oper. Res. Quar.- 1977.- Vol. 28, № l(ii). P. 167-179.

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

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

127. Francis R.L., Lowe T.J., RatlifFD.H. Distance constraints for network multifacility location problems // Oper. Res. 1978. - Vol. 26, № 4. - P. 570-595.

128. Gilmore P.C. Optimal and suboptimal algorithms for the quadratic assignment problem // J. SIAM. 1962. - Vol. 10, № 2. -P. 305-313.

129. Hamacher H.W., Klamroth K. Planar Weber location problems with barriers and block norms // Annals of Oper. Res. 2000. - № 96. -P. 191-208.

130. Ichimori T. A shortest path approach to a multifacility minimax location problem with rectilinear distances // Journal of the Operations Research Society of Japan. 1974. - Vol.8. - P. 126-141.

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

132. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica- 1984. Vol. 4, № 4. - P. 373-395.

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

134. Karp R.M., Held M. Finite-state processes and dynamic programming // SIAM J. Appl. Math. 1967. - Vol. 15, № 3. - P. 693-718.

135. Katz M.J., Kedem K., Segal M. Improved algorithms for the placing undesirable facilities // Computers &; Operations Research. 2002. - Vol. 29. - P. 1859-1872.

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

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

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

139. Kurn H.W. A note on Fermat's problem // Mathematical Programming 4 North-Holland Publishing Company, 1973. - P. 98-107.

140. Lawler E.L. The quadratic assignment problem // Management Science. 1963. - Vol. 9. - P. 586-599.

141. Love R.F., Wong J.Y. On solving one-dimensional space allocation problem with integer programming // INFOR. 1976. - Vol. 14, № 2. - P. 139-143.

142. Morris J.G. A linear programming approach to the solution of constrained multifacility minimax location problems where distances are rectangular // Oper. Res. Quar., 1973. Vol. 24. - P. 419-435.

143. Shiloach Y. A minimum linear arrangement algorithm for undirected trees // SIAM J. Comput. 1979. - Vol.8, № 1. - P. 15-32.

144. Picard J.C., Queranne M. On the one-dimensional space allocation problem // Oper. Res. 1981. - Vol. 29, № 2. - P. 371-391.

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

146. Reeves C.R. Genetic algorithms for the operations researcher // INFORMS Journal on Computing. 1997. - Vol. 9, № 3. - P. 231-250.

147. Sahni S., Gonzalez T. P-complete approximation problems// J. Assoc. Comput. Mach. 1976. - Vol. 23, № 3. - P. 555-565.

148. Shiloach Y. A minimum linear arrangement algorithm for undirected trees// SIAM J. Comput. 1979. - Vol. 8, № 3. - P. 15-32.

149. Simmons D.M. One-dimensional space allocation: an ordering algorithm // Oper. Res. 1969 - Vol.17. - P. 812-826.

150. Steinberg L. The backboard wiring problem: a placement algorithm // SIAM Rev. 1961. - Vol. 3, № 1. - P. 37-50.

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

152. Zabudsky G.G. Location of communication network in line // Proc. International Workshop DCCN'98. Moscow, 1998. - P. 70-75.

153. Zabudsky G.G. On the one-dimensional space allocation problem with minimal admissible distances // Proc. of the 3rd IFIP WG -7.6 Working Conference on Optimization-Based Computer Aided Modelling and Design. Prague, 1995. - P. 448-452.

154. Zabudsky G.G. Some results for the one-dimensional space allocation problem // Abstr. Symp. on Operations Research (SOR99). Jena, 1997. - P. 50.

155. 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.

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

157. 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" (DQM2004). Omsk-Irkutsk, 2004. - P. 81-85.