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

• Автор: Забудский, Геннадий Григорьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 272 с. : ил.

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

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

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

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

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

расстояниями

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

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

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

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

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

Глава 3. Размещение на сетях
3.1 Решение минимаксной задачи Вебера на дереве
3.2 Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей
3.3 Алгоритмы решения задач Вебера на общих сетях
3.4 Полиномиальные алгоритмы для задач с взаимно однозначным размещением
3.5 Динамическое программирование для квадратичной задачи о назначении на дереве

З.б Свойства многогранника задачи о р-медиане
Глава 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].
Важным направлением исследований в рассматриваемой области является анализ и решение задач оптимального размещения объектов. Такие задачи необходимо решать при проектировании предприятий и робототехнологических комплексов, определении мест расположения пунктов обслуживания, автоматизированном конструировании электронных устройств и выполнении многих других работ.
Среди задач оптимального размещения можно выделить два класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения. Отличие состоит в том, что в задачах первого класса необходимо найти места расположения объектов, между которыми имеются некоторые связи (не обязательно между всеми). В задачах второго класса связи устанавливаются в результате их решения. Например, при размещении пунктов обслуживания к ним прикрепляются клиенты (устанавливаются связи). Классическими представителями первого класса являются задача Вебера и квадратичная задача о назначении. Разработкой этой проблематики занимались Ахмедов И.С., Демиденко В.А., Жак С.Б., Зинченко А.Б, Иорграфа. При этом выделяются жёсткие дуги (см. п. 1.1), наличие которых позволяет уменьшить размерность задачи. Далее определяется верхняя оценка Д° значения целевой функции (1.1) с помощью эвристических процедур и их вероятностных комбинаций. Затем применяется гибридный алгоритм, использующий схему ДП для неориентированного графа [145]. Рассматриваются только перспективные частичные размещения, для которых нижние оценки функции (1.1) меньше Л°.
Опишем алгоритмы нахождения двухполюсных ориентированных подграфов и корневых поддеревьев в графе Г.
Алгоритм 1.2. поиска двухполюсных ориентированных подграфов
Шаг 1. Для каждой вершины г,- Є РД Є J формируем список вершин, непосредственно следующих за У{, с условиями
и (уі) = {Ьі Є V І (у;,т/) Є Е,(1+(У]) = <1-{уі) = 1}.
Переход на шаг 2.
Шаг 2. Для всех і Є 7 и каждой € Ь(уі) запоминаем в списке ■^(т«,) вершину, полустепень захода или исхода которой больше 1 и находящейся на простом пути р(уш,уи), исходящем из вершины ^{Уги) = {Уи є V СІ+(уи) > 1 ИЛИ й~{уи) > 1,« Є р{Уіи,Уи)}- ПереХОД На шаг 3.
Шаг 3. Если не существует уі и V/, принадлежащих различным цепям таким, что Ьї(уі) = Ь2(г>у), то Стоп. Иначе, пусть Ь2(у{) = £2(^2) = Уі,-,^2{Ук) = Уі, тогда, У!,у2 Ук образуют двухполюсный ориентированный граф со стоком и существует у8 Є V, такая, что (Пз,^), (ув,Уі2) (у$,Уір) Є Е, р > 2, у5 является источником в двухполюсном ориентированном графе. Получаем граф Г і, в котором выделены источник и сток, соединённые непересекающимися простыми цепями. Переход на шаг 4.
Шаг 4. Решаем задачу размещения для графа Гі алгоритмом 1