Содержание к диссертации
Введение
Глава 1. Задачи оптимального линейного упорядочения 32
1.1 Полиномиальные алгоритмы для специальных ориентированных графов 32
1.2 Гибридный алгоритм для произвольного ориентированного графа 49
1.3 Полиномиальный алгоритм для двухполюсного неориентированного графа 58
Глава 2. Размещение на линии с минимально допустимыми расстояниями 71
2.1 Постановки задач и их свойства 71
2.2 Фиксированный порядок расположения объектов . 79
2.3 Модели целочисленного линейного программирования 87
2.4 Анализ L-структуры многогранных множеств . 102
2.5 Алгоритмы решения 113
Глава 3. Размещение на сетях 127
3.1 Решение минимаксной задачи Вебера на дереве . 128
3.2 Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей 135
3.3 Алгоритмы решения задач Вебера на общих сетях . 142
3.4 Полиномиальные алгоритмы для задач с взаимно однозначным размещением 157
3.5 Динамическое программирование для квадратичной задачи о назначении на дереве 170
3.6 Свойства многогранника задачи о р-медиане . 174
Глава 4. Размещение на плоскости и дискретных множествах 180
4.1 Модели целочисленного программирования для задач на плоскости с запрещенными зонами 181
4.2 Размещение объекта с учетом запрещенных зон и прямоугольной метрикой 188
4.3 Размещение объекта с учетом запрещенной зоны и евклидовой метрикой 197
4.4 Построение оценок суммарной стоимости связей . 202
Глава 5. Решение прикладных задач 218
5.1 Построение моделей 218
5.2 Модель оптимального размещения модулей швейного производства . 227
5.3 Анализ оптимальности расположения нефтеперерабатывающего оборудования 234
Заключение 240
Список использованной литературы 242
Приложение 1 260
- Гибридный алгоритм для произвольного ориентированного графа
- Модели целочисленного линейного программирования
- Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей
- Размещение объекта с учетом запрещенных зон и прямоугольной метрикой
Введение к работе
Одним из интенсивно развивающихся направлений математической кибернетики является теория и методы решения задач оптимизации. Это связано с тем, что многие проблемы, возникающие в управлении, планировании, проектировании и других областях, достаточно хорошо описываются с помощью математических оптимизационных моделей. Применение таких моделей позволяет обосновать рекомендации при принятии решений и повысить их качество.
В настоящее время существенные успехи достигнуты в изучении структуры, сложности и устойчивости задач оптимизации, разработке методов их решения, программной реализации алгоритмов [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. и другие [6, 24, 55, 80, 95,101,105,114,117,118,126,138,152]. Наиболее известные задачи второго класса: простейшая задача размещения, задачи о р-медиане и о р-центре. Заметный вклад в их исследование внесли Агеев А.А., Бахтин А.Е., Береснев В.Л., Гимади Э.Х., Глебов Н.И., Дементьев В.Т., Емеличев В.А., Ильев В.П., Колоколов А.А., Кочетов Ю.А., Леванова Т.В., Хачатуров В.Р., 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 году Вебер использовал подобную модель для определения оптимального расположения фабрики при заданных точках размещения ресурсов. Однако, только с появлением и развитием математической кибернетики эти задачи стали предметом всестороннего и глубокого исследования.
В указанной задаче нет ограничений на взаимное расположение объектов, в частности, допускается их размещение в одной точке. Это условие существенно уменьшает трудоемкость решения задачи.
Если известны возможные места установки объектов, т.е. рассматривается дискретная постановка задачи, причем на каждом месте может быть не более одного объекта и отсутствуют размещенные объекты, то задача размещения становится квадратичной задачей о назначении в виде Купманса-Бэкмана [138]. При условии Ujk = 0 для j k,j,k Є J задача Вебера преобразуется в линейную задачу о назначениях.
Основные характеристики, по которым ведется классификация рассматриваемого класса задач: трактовка понятия "объект", структура связей между объектами, ограничения, критерии, свойства области, в которой размещаются объекты, и некоторые другие.
Понятие "объект" трактуется достаточно широко. При проектировании генеральных планов предприятий объекты - это здания и со боружения [6,24,51]; при создании робототехнологических комплексов - единицы технологического оборудования [79]. Если проектируется печатная плата, то объектами являются элементы печатного монтажа, например, микросхемы [1,7]. При расположении пунктов обслуживания объекты - это станции скорой или технической помощи, магазины, склады и т.д.
Тип связи между объектами зависит от сферы деятельности, в которой возникает задача размещения. Например, если проектируется нефтехимическое предприятие, то его составными элементами являются единицы технологического оборудования, которые связаны между собой различными трубопроводами. При проектировании печатных плат, связи - это проводники, соединяющие элементы печатного монтажа. Когда размещаются пункты обслуживания, связями являются, например, потоки товаров.
При решении задач оптимального размещения, необходимо учитывать различные ограничения на расположение объектов. Строительные нормы и правила определяют противопожарные, санитарные и другие нормативы, которые при проектировании генпланов задают ограничения на минимально допустимые расстояния между сооружениями и единицами оборудования. Максимально допустимые расстояния между объектами могут определяться технологией производства, например, мощностью насосных станций. При создании атомных станций определяется "зеленая" зона, в которой запрещено размещение населенных пунктов. Кроме того, во многих случаях расположение объектов должно быть "регулярным", например, оборудование устанавливается вдоль "красных" линий, что позволяет проектировать прямые проезды и выделять кварталы в расположении объектов.
В зависимости от поставленных целей рассматриваются различные критерии оценки качества получаемых размещений. Например, для нефтехимических предприятий стоимость трубопроводных связей может составлять около 25 процентов от общих капитальных затрат на строительство. Поэтому при размещении оборудования такого предприятия на заданной строительной площадке можно минимизировать суммарную стоимость трубопроводных связей [6,80]. Достаточно часто используются критерии минимума площади, занимаемой размещенными объектами [б], и минимума наиболее дорогой по стоимости (максимальной) связи [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.1 отмечено, что задача (1) JVP-трудна для произвольного графа Г и описан алгоритм трудоемкости 0(n\ogn) в случае, когда Г является композицией корневых деревьев и двухполюсных ориентированных графов. Граф Г назовем двухполюсным ориентированным графом, если в нем выделены две вершины vs и Vt, соединенные вершинно непересекающимися ориентированными от vs к Vt цепями. Вершина vs должна быть расположена левее всех, а вершина vt - правее всех вершин. Граф назовем композицией корневых деревьев и двухполюсных ориентированных графов, если при замене всех таких подграфов цепями, получаем корневое дерево или двухполюсный ориентированный граф. Доказана
ТЕОРЕМА 1.6. Задача оптимального линейного упорядочения для графа Г, являющегося композицией корневых деревьев и двухполюсных ориентированных графов, разрешима за O(nlogn) операций. Для произвольного ориентированного ациклического графа Г в п. 1.2 разработан гибридный алгоритм комбинаторного типа решения задачи (1), основанный на динамическом программировании и методе ветвей и границ. На предварительном этапе в графе Г находятся корневые поддеревья и двухполюсные ориентированные подграфы, которые с помощью полиномиальных алгоритмов заменяются ориентированными цепями. Проведён вычислительный эксперимент по сравнению гибридного алгоритма и алгоритма динамического программирования.
Во второй главе рассматривается обобщение задачи оптимального линейного упорядочения - одномерная задача размещения. Взаимосвязанные прямоугольные объекты размещаются на линии с критерием минимума суммарной стоимости связей и ограничениями на минимально допустимые расстояния между ними. Исследуется сложность решения такой задачи при различных условиях для минимально допустимых расстояний и структуры графа Г. Особое внимание уделяется изучению моделей ЦП, в частности, исследованию структуры многогранных множеств. Предложены алгоритмы решения указанной задачи.
Одномерная задача размещения состоит в следующем. Множество прямоугольных объектов с габаритами сц X hi, і Є J, центры которых связаны, размещаются на линии. Связи проходят вертикально от центров объектов до линии размещения, а затем вдоль нее, тогда задача сводится к размещению проекций геометрических центров прямоугольников на линию. Минимально допустимое расстояние между объектами с номерами і и j с учетом их габаритов обозначим через Гц, a R = (гц),гц = 0, г, j Є J - симметричная матрица минимально допустимых расстояний. Структура связей между объектами задается с помощью графа Г = (V,E) (см. п. 1.1). Необходимо разместить объекты на линии таким образом, чтобы выполнялись ограничения на минимально допустимые расстояния и при этом суммарная стоимость связей между объектами была бы минимальной.
Задача (2), (3) является iVP-трудной, так как при условиях гг;- = 1, і ф j и Cij = 1 для (г/г-, Vj) Є Е она эквивалентна задаче оптимального линейного упорядочения, рассмотренной в главе 1.
Доказано, что задача (25)-(30) является iVP-трудной и для ее решения предложены алгоритмы последовательно одиночного размещения.
В п. 5.3 проведены результаты анализа оптимальности расположения оборудования секции нефтехимического предприятия в проекте, созданном по традиционной методике проектирования. Для этого применялись: модель квадратичной задачи о назначении, алгоритмы ветвей и границ, локальной оптимизации и эвристический алгоритм. Анализ проводился в два этапа. На первом этапе проверялось выполнение ограничений на допустимые расстояния между оборудованием, а на втором - оптимальность размещения оборудования относительно стоимости связывающей их сети коммуникаций.
В результате проведенных расчетов получены решения, которые имеют оценку суммарной стоимости коммуникаций на 10 % меньше, чем исходное размещение.
В заключении приведены основные результаты диссертации.
В приложениях представлены результаты вычислительных экспериментов и исходные данные прикладных задач.
Основные результаты диссертации опубликованы в работах [27,28, 30-41,43-49,153,154,158] и докладывались на региональной научно-технической конференции "Проблемы повышения эффективности создаваемых и внедряемых АСУ" (Омск, 1986); 7-й школе по пакетам прикладных программ (с. Ярополец Московской области, 1987); 10-м всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988); всесоюзных и всероссийских конференциях "Методы математического программирования и программное обеспечение" (Свердловск-Екатеринбург, 1989,1991,1995,1997,1999, 2003); межреспубликанской школе-семинаре "Дискретная оптимизация" (Алушта, 1989); третьей школе-семинаре по вопросам автоматизированного проектирования объектов архитектуры и строительства (п. Эльбрус, 1989); 4-м всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989); всесоюзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск, 1990); 2-й всесоюзной школе-семинаре "Декомпозиция и координация в сложных системах" (Алушта, 1990); школе-семинаре "Дискретная математика и ее применение в задачах обработки информации" (Москва, 1990); Байкальских международных школах-семинарах "Методы оптимизации и их приложения" (Иркутск, 1995,1998, 2001, 2005); 3-м совещании по оптимизации, моделированию и принятию решений (Прага, 1994); международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997); международном симпозиуме по исследованию операций (Иена, Германия, 1997); международной конференции по исследованию операций (Цюрих, Швейцария, 1998); международной сибирской конференции по исследованию операций (Новосибирск, 1998); международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000); российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004); международной конференции по исследованию операций (Клагенфурт, Австрия, 2002), 2-м международном совещании "Методы дискретной оптимизации в производстве и логистике" (Омск - Иркутск, 2004); а также на семинарах в Белорусском государственном университете, Вычислительном центре им. А.А. Дородницына РАН, Иркутском государственном университете, Институте информационных технологий и прикладной математики СО АН СССР, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.
Автор благодарит д.ф.-м.н., профессора Александра Александровича Колоколова за полезные советы при выполнении данной работы.
Гибридный алгоритм для произвольного ориентированного графа
В общем случае, такие задачи 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" г. Кургана.
Модели целочисленного линейного программирования
Для решения СЗН предлагается алгоритм, который либо находит оптимальное решение, либо устанавливает ее неразрешимость не более чем за q шагов.
Аналогичная схема может быть реализована в случае максимально допустимых расстояний между объектами. Кроме того, показано как можно использовать СЗН для задачи размещения прямоугольных объектов на линии (см. п. 2.1).
В пятой главе описаны требования, которые предъявляются к проектам размещения технологического оборудования, традиционная методика их проектирования. Построена математическая модель оптимального размещения швейного оборудования в цехе и проведен анализ оптимальности расположения технологического оборудования нефтехимического предприятия с помощью рассмотренных в диссертации математических методов.
В п. 5.1 описана традиционная методика составления эскизных проектов размещения технологического оборудования. Кроме того, излагаются варианты моделирования ограничений (максимально и минимально допустимых расстояний между оборудованием, "регулярности" расположения и т.д.), а также критериев оптимальности. В п. 5.2 построена двухкритериальная математическая модель ЦП оптимальной расстановки технологического оборудования швейного производства. Размещение производится на осевых линиях с учетом необходимых проходов между оборудованием. При этом структура связей (поток заготовок) между участком запуска (источник) и сборки готового изделия (сток) имеет вид двухполюсного ориентированного графа с одним объектом на каждой из цепей (см. п.1.1). Необходимо разместить прямоугольники с габаритами ay х hj,j «7 на заданном числе осевых линий таким образом, чтобы были прямые проходы заданной ширины между линиями и при этом максимальная суммарная длина модулей на осевых линиях и ширина прямоугольной области, занятой оборудованием, были минимальными. Модель ЦП имеет вид: где Zjk = 1 если j-й прямоугольник находится на линии к, иначе 0; М - множество номеров линий, L - длина цеха, Я - ширина цеха, А - ширина прохода между линиями, d - минимальное техническое расстояние от боковой стены цеха. Доказано, что задача (25)-(30) является iVP-трудной и для ее решения предложены алгоритмы последовательно одиночного размещения. В п. 5.3 проведены результаты анализа оптимальности расположения оборудования секции нефтехимического предприятия в проекте, созданном по традиционной методике проектирования. Для этого применялись: модель квадратичной задачи о назначении, алгоритмы ветвей и границ, локальной оптимизации и эвристический алгоритм. Анализ проводился в два этапа. На первом этапе проверялось выполнение ограничений на допустимые расстояния между оборудованием, а на втором - оптимальность размещения оборудования относительно стоимости связывающей их сети коммуникаций. В результате проведенных расчетов получены решения, которые имеют оценку суммарной стоимости коммуникаций на 10 % меньше, чем исходное размещение. В заключении приведены основные результаты диссертации. В приложениях представлены результаты вычислительных экспериментов и исходные данные прикладных задач. Основные результаты диссертации опубликованы в работах [27,28, 30-41,43-49,153,154,158] и докладывались на региональной научно-технической конференции "Проблемы повышения эффективности создаваемых и внедряемых АСУ" (Омск, 1986); 7-й школе по пакетам прикладных программ (с. Ярополец Московской области, 1987); 10-м всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988); всесоюзных и всероссийских конференциях "Методы математического программирования и программное обеспечение" (Свердловск-Екатеринбург, 1989,1991,1995,1997,1999, 2003); межреспубликанской школе-семинаре "Дискретная оптимизация" (Алушта, 1989); третьей школе-семинаре по вопросам автоматизированного проектирования объектов архитектуры и строительства (п. Эльбрус, 1989); 4-м всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989); всесоюзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск, 1990); 2-й всесоюзной школе-семинаре "Декомпозиция и координация в сложных системах" (Алушта, 1990); школе-семинаре "Дискретная математика и ее применение в задачах обработки информации" (Москва, 1990); Байкальских международных школах-семинарах "Методы оптимизации и их приложения" (Иркутск, 1995,1998, 2001, 2005); 3-м совещании по оптимизации, моделированию и принятию решений (Прага, 1994); международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997); международном симпозиуме по исследованию операций (Иена, Германия, 1997); международной конференции по исследованию операций (Цюрих, Швейцария, 1998); международной сибирской конференции по исследованию операций (Новосибирск, 1998); международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000); российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004); международной конференции по исследованию операций (Клагенфурт, Австрия, 2002), 2-м международном совещании "Методы дискретной оптимизации в производстве и логистике" (Омск - Иркутск, 2004); а также на семинарах в Белорусском государственном университете, Вычислительном центре им. А.А. Дородницына РАН, Иркутском государственном университете, Институте информационных технологий и прикладной математики СО АН СССР, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.
Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей
В данной главе рассматривается задача оптимального размещения взаимосвязанных прямоугольных объектов на линии с критерием минимума суммарной стоимости связей и ограничениями на минимально допустимые расстояния между ними. В п. 2.1 приводится постановка задачи и исследуется сложность ее решения в зависимости от условий на минимально допустимые расстояния и структуру связей между объектами [36]. В п. 2.2 изучается задача ЛП, возникающая при фиксированном порядке расположения объектов [38]. В п. 2.3 рассматриваются две модели целочисленного линейного программирования (ЦЛП) указанной задачи, изучаются их свойства. В частности, исследуются соответствующие многогранные множества и приводятся способы построения допустимых решений исходной задачи с помощью округления решений релаксированных задач. В п. 2.4 изучается структура L-разбиения многогранных множеств [28]. Приводятся верхняя и нижняя оценки длины цепей дробных L-классов. В п. 2.5 предлагаются варианты алгоритма ветвей и границ и перебора L-классов для решения задачи [29]. Приводятся результаты вычислительного эксперимента.
Множество взаимосвязанных прямоугольных объектов необходимо разместить на заданной линии. Ограничениями являются минимально допустимые расстояния между объектами. Требуется найти расположение объектов, удовлетворяйте ограничениям, с минимальной суммарной стоимостью связей.
Пусть п - число размещаемых объектов, J = {1,..., п} - множество их номеров. Каждый объект это прямоугольник с размерами аг- х h{, і Є J. Размещение производится как показано на рис. 2.1. Коммуникациями связываются центры объектов, способ их прокладки изображен на рисунке жирной линией.
Связи проходят вертикально от центров объектов до линии размещения, а затем по указанной линии. Длина вертикальной составляющей связи для объектов і и j равна h\j2 + hj/2 и не зависит от расположения объектов. Исходные минимально допустимые расстояния задаются между ближайшими точками объектов, однако, в них можно учесть величины аг-, і Є J и считать, что заданы ограничения между проекциями центров. Задача сводится к размещению точечных объектов, т.е. проекций геометрических центров прямоугольников на линию. Минимально допустимое расстояние между объектами і и j с учетом габаритов, будем обозначать через г ,гц = 0,i,j Є J,R = (rij) - симметричная матрица минимально допустимых расстояний. Структура связей между объектами задается с помощью графа Г = (V, Е) (см. п. 1.1). Ребро (vj,Vj) Є Е, если существует связь между объектами с номерами і и j. Удельную стоимость этой связи обозначим через Cij 0, Cij = Cji. Иногда для некоторых связанных объектов может быть задан порядок размещения на линии, например, г -й объект должен быть расположен левее j-ro, тогда (г;,-, Vj) - это дуга. Необходимо разместить объекты на линии таким образом, чтобы выполнялись ограничения на минимально допустимые расстояния и при этом суммарная стоимость связей между объектами была бы минимальной. Направим координатную ось вдоль линии размещения. Обозначим через ХІ координату центра г -го объекта, х = (х\,..., хп) - размещение объектов. В задаче требуется минимизировать функцию:
Если (vi,Vj) - дуга, то в выражении #,- — Xj\ модуль можно опустить. Задача (2.1), (2.2) является iVF-трудной. Это следует из того, что при условиях: г = 1 Vi,j Є J, і ф j и Су = 1 для ( , vj) Є Е, Г - произвольный неориентированный граф, она эквивалентна задаче оптимального линейного упорядочения (см. глава 1). Рассматриваются следующие условия на элементы матрицы R : a) Гц = (ai + cij)/2, i,j Є J J ф j (условия непересечения); b) Гц + rjk Гц., i,j, к Є /, г ф j ф к (метрическая задача); c) Гц — произвольные, i,j Є J (неметрическая задача). В практических задачах иногда размещение производится на ограниченной площадке, т.е. в нашем случае - на отрезке. Кроме того, расположение некоторых объектов может быть зафиксировано. Пусть задан отрезок длины / 0. Считаем, что он направлен вдоль координатной оси ОХ и один его конец совпадает с началом координат. Через Jo = {15 5по} обозначим множество номеров размещенных (фиксированных) объектов, их координаты - x :,j Є «/о- Структура связей между объектами задается с помощью графа Г = (V ,E ), где V = V U Vo, Vo - множество вершин, соответствующих фиксированным объектам, а Е С Е . Ребро (v{,Vj) Є E ,V{ Є V,Vj Є Vo, если существует связь между г-м размещаемым и j-u фиксированным объектами. Удельную стоимость такой связи обозначим C[j О, (С- = Cj,-). Через г - 0 обозначим минимально допустимое расстояние между объектами і Є J и j Є Jo, а, ГОІ И ГЦ - минимально допустимые расстояния от г -го объекта до границ отрезка. Тогда с учетом указанных дополнительных ограничений модель принимает вид: Отметим некоторые свойства задачи (2.1), (2.2). В работе [114] для задачи нумерации показано, что добавление константы (положительной или отрицательной) к весу каждого ребра графа Г не меняет оптимального решения. Нетрудно заметить, что указанное свойство имеет место и для сформулированных задач. Во многих задачах, например, в задаче коммивояжера, удается ме-тризовать исходную матрицу путем добавления ко всем элементам одинаковой константы. Покажем на примере, что в задаче размещения объектов на линии добавление константы к минимально допустимым расстояниям может не сохранять оптимального порядка расположения объектов. Рассмотрим задачу (2.1), (2.2) для п — 3 с условиями: С\2 = 1,С із = 100, г\2 = 1, из = 2, Г2з = 1. Оптимальным порядком расположения объектов для нее является (1,2,3). После добавления 1 к минимально допустимым расстояниям - (1,3,2).
Размещение объекта с учетом запрещенных зон и прямоугольной метрикой
В этом пункте отметим некоторые свойства вершин релаксационных многогранных множеств, в частности, условия, при которых частично целочисленные вершины не сохраняют смежность.
Покажем, что при целочисленности минимально допустимых расстояний все частично целочисленные вершины в О, и О! имеют целые компоненты.
Отметим, что в Q нет вершин в пространстве Rm+n. Действительно, для каждой пары индексов і и j первые два ограничения в (2.20) не могут обращаться в равенства, так как, складывая их, имеем А — 2rjj = 0, что противоречит выбору константы А. Следовательно, такие ограничения могут дать не более m равенств. Тогда, по крайней мере, п равенств получаются из условий (2.21), т.е. в любой вершине v = (z,x) Є Q не менее п компонент вектора z имеют целочисленные значения. Нетрудно показать, что совокупность ограничений альтернативности в (2.20), в которые входят целочисленные компоненты вектора z, не могут образовать систему из более чем п—1 линейно независимых равенств. Это можно показать, рассматривая граф, вершинами которого являются индексы выбранного набора целочисленных компонент вектора z, а ребра соответствуют каждой такой компоненте, если соответствующее ограничение из (2.20) обращается в равенство. В результате будем иметь систему не более чем т — п-\-п — 1 + п = т+п—1 линейно независимых ограничений из (2.20), обращающихся в равенства. Отсюда следует, что в Q нет вершин пространства Rm+n. Систему ранга т + п - 1 можно построить, например, так. Возьмем z Є D(Bm) и для соответствующей ему перестановки it(z) построим плотную упаковку х. Легко показать, что v = (z,x) это вершина множества Q в пространстве Rm+n l. Действительно, матрица коэффициентов такой системы будет верхней треугольной с ненулевыми диагональными элементами.
Отметим также, что произвольная вершина v = (z\ х , и ) Є О образуется пересечением \E\-\-m-\-n-l линейно независимых ограничений, обращающихся в равенства. Для z Є D(Bm) такая система получается следующим образом: для z находится плотная упаковка х , а затем определяются компоненты вектора u u ij = \х\ — x j\ ф О (равенства х\ = x j не может быть, так как 7 0 для всех i,j Є J, г Ф j). Ясно, что матрица коэффициентов такой системы будет верхней треугольной с ненулевыми диагональными элементами. В частности, отсюда следует, что из каждой пары альтернативных неравенств вида (2.15) для вершины v = (z ,x ,u ) Є fi такой, что z Є D(Bm), одно из них обращается в равенство, так как иначе ранг системы равенств не превышал бы 1 1 + 771 + 72-2. Тогда между вершинами v = (z,x) Є fi, z Є D(Bm) и вершинами v = (z\ x , v!) Є П , z Є D(Bm) можно установить взаимно однозначное соответствие: z = z, х = х, u[j = \ХІ — Xj\. Причем очевидно, что других вершин в(]с целочисленным фиксированным вектором z, кроме как построенных указанным выше способом, нет. Тогда из того, что v = (2, х) О, z Є D(Bm) - вершина тогда и только тогда, когда х плотная упаковка, следует, что точка х имеет целочисленные компоненты, если координата фиксированного объекта и минимально допустимые расстояния целые. Таким образом, все частично целочисленные вершины v Є 0 имеют целые компоненты при целочисленности исходных данных. Из однозначности соответствия частично целочисленных вершин множеств ОиП и способа построения вершин Q по вершинам из Г2 следует, что аналогичное свойство имеет место и для множества Q . Справедливо
УТВЕРЖДЕНИЕ 2.8. Если все элементы матрицы R целые, то все частично целочисленные вершины в Q, и$1 имеют целочисленные компоненты. Аналогичное утверждение можно сформулировать для Сі . Отметим, что для произвольной вершины v = (z ,x ,u ) Є ГІ такой, что х\ ф x j для всех і ф j, число целочисленных компонент вектора z не меньше п. Действительно, в О любая вершина образована пересечением \Е\ + т + п гиперплоскостей из ограничений (2.15), (2.20). Так как ограничения (2.15) могут дать не более \Е\ равенств, а при х\ ф x j ограничения альтернативности в (2.16) не более т равенств (одно из каждой пары неравенств всегда будет строгим), то оставшиеся п равенств получаются из условий (2.21).
Приведем условия на минимально допустимые расстояния, при которых частично целочисленные вершины множеств Q и W являются изолированными, т.е. все соседние вершины с каждой такой вершиной дробные.
Как было отмечено выше, точка v — (z,x) Є Г2, z Є D(Bm) является вершиной тогда и только тогда, когда х - плотная упаковка. В частности, если rjj + rjk Г{к для всех i,j, к Є J, то плотная упаковка для фиксироканного z Є D(Bm) единственная, причем существует только одна система тг — 1 линейно независимых ограничений альтернативности вида (2.20), обращающихся на ней в равенства. Таким образом, для вершины v также будет существовать единственный базис, т.е. она будет невырожденной. Легко показать, что при этих условиях невырожденными будут соответствующие вершины и в Q . Условия, при которых вырожденными являются вершины для некоторой фиксированной перестановки, задающей расположение объектов на линии, рассмотренные в п. 2.2, приводят к наличию вырожденных вершин в О, и W.
