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

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

ЗАБУДСКИЙ Геннадий Григорьевич

МОДЕЛИ И МЕТОДЫ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ВЗАИМОСВЯЗАННЫХ ОБЪЕКТОВ НА ДИСКРЕТНЫХ МНОЖЕСТВАХ

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

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

Иркутск - 2006

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

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

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

доктор физико-математических наук, профессор Попков Владимир Константинович . доктор физико-математических наук Попов Леонид Денисович

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

Вычислительный центр имени A.A. Дородницына РАН

Защита состоится 16 июня 2006 г. в 13 чгьсов на заседании диссертационного совета Д 212.074.01 в Иркутском государственном университете по адресу: 664003, г. Иркутск, ул. К. Маркса, 1, ИМЭИ ИГУ.

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

Автореферат разослал ¿О мая 2006 г. Ученый секретарь

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

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

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

Среди задач оптимального размещения можно выделить два класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения. Отличие состоит в том, что в задачах первого класса необходимо найти места расположения объектов, между которыми имеются некоторые связи (не обязательно между всеми). В задачах второго класса связи устанавливаются в результате их решения. Например, при размещении пунктов обслуживания к ним прикрепляются клиенты (устанавливаются связи). Классическими представителями первого класса являются задача Вебера и квадратичная задача о назначении. Разработкой этой проблематики занимались Ахмедов И.С., Демиденко В.А., Жак С.Б., Зинченко А.Б, Иорданский М.А., Паню-ков A.B., Сергеев С.И., Сигал И.Х., Стоян Ю.Г., Трубин В.А., Яковлев C.B., Adolfson D., Beckmann M.J, Burcard R.E., Francis R.L., Koop-mans T.C., Tamir А. и другие. Наиболее известные задачи второго

класса: простейшая задача размещения, задачи о р-медиане и о р-центре. Заметный вклад в исследование задач этого класса внесли Агеев A.A., Бахтин А.Е., Береснев B.JL, Гимади Э.Х., Глебов Н.И., Дементьев В.Т., Емеличев В.А., Ильев В.П., Колоколов A.A., Кочетов Ю.А., Леванова Т.В., Хачатуров В.Р., Hakimi S.L., Kariv О., Krarup J., Pruzan P.M. и ряд других авторов.

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

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

В настоящее время известны точные и эвристические алгоритмы решения NP-трудных вариантов задач размещения на линии с критерием минимума суммарной стоимости связей. Для задачи оптимального линейного упорядочения (размещения точечных объектов в целые точки на линии, не более чем по одному в каждую) и одномерной задачи размещения разногабаритных объектов на линии с условием их непересечения разработаны алгоритмы динамического программирования и ветвей и границ (Picard J.С., Queranne М., Simmons D.M.). Предложен эвристический алгоритм решения одномерной задачи с ис-

пользованием модели целочисленного программирования (Love R.F., Wong J.Y.). Полиномиальные алгоритмы решения указанных задач построены для случая, когда структура связей между объектами представлена в виде взвешенного корневого дерева, в котором вершины соответствуют объектам, а дуги - связям (Adoifson D., Hu Т.С., Picard J.С., Queranne M.). Задача оптимального линейного упорядочения полиномиально разрешима для невзвешенного дерева и некоторых графов специального вида (Иорданский М.А., Shiloach Y.).

В случае взаимно однозначного размещения объектов на произвольном дискретном множестве позиций (квадратичная задача о назначении) описаны модели комбинаторной оптимизации и целочисленного программирования. Разработаны эвристические алгоритмы и алгоритмы ветвей и границ (Сергеев С.И., Burcard R.E, Francis R.L., Gilmore P.C., Lawer E.L, Mirchamdani P.B.), выделены полиномиально разрешимые варианты задачи для специальных матриц расстояний между позициями и связей между объектами (Гордон B.C., Деми-денко В.М., Finke G.).

Задачи Вебера (в одной точке может размещаться произвольное число объектов) в литературе изучались на плоскости и сетях. В случае древовидных сетей и прямоугольной метрики на плоскости указанные задачи с минимаксным критерием и критерием минимума суммарной стоимости связей с ограничениями на максимально допустимые расстояния между объектами сводятся к задачам линейного программирования (ЛП) и их частным вариантам (Трубин В.А., Erkut Е., Francis R.L., Ichimori Т., Lowe T.J., Morris J.G., Picard J.C., Ratliff D.H., Tamir А.). Для задачи на дереве с минимаксным критерием предложены более эффективные алгоритмы (Erkut Е., Francis R.L., Tamir А.).

Если объекты прямоугольные, то для задачи на плоскости с критерием минимума суммарной стоимости связей предложен алгоритм локальной оптимизации (Панюков A.B.) и алгоритм ветвей и границ (Степанов В.П.). Рассматривались также задачи размещения опасных производств на плоскости и сетях как можно дальше от фиксированных (Katz M.J., Kedem К., Segal М.). Известны постановки задач размещения, когда при их решении принимают во внимание наличие барьеров, которые необходимо учитывать при прокладке связей между объектами (Hamacher H.W., Klamroth К.)

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

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

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

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

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

Основные результаты диссертации, выносимые на защиту.

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

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

т

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

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

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

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

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

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

Исследования по теме диссертации поддержаны грантами: РФФИ № 97-01-00771, РГНФ № 04-02-00238а, ИНТАС № 00-217.

Апробация работы. Результаты работы докладывались на региональной научно-технической конференции "Проблемы повышения эффективности создаваемых и внедряемых АСУ" (Омск, 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); а также на семинарах в Белорусском государственном университете, Вычислительном центре им. A.A. Дородницына РАН, Иркутском государственном университете, Институте информационных технологий и прикладной математики СО АН СССР, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.

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

публикаций входят 10 статей из "Перечня ведущих научных журналов и изданий, выпускаемых в Российской Федерации, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук" [1-10].

Личный вклад автора. Все основные результаты получены автором лично. В совместной работе [20] Бикбавовым Д.Ф. был сделан обзор по задачам оптимальной нумерации. В [22] Легких С.А. описана процедура формирования модулей. В работе«: [17,18] соавтором Мотовиловым В.А. разработал алгоритм нумерации деревьев. В [16] Нежинским И.В. предложен способ выбора разрешающего множества. В [3,6,19,25] Филимонову Д,В. принадлежит разработка алгоритма для одинаковых весов ребер дерева и алгоритма последовательно одиночного размещения. Указанные результаты соавторов в диссертационную работу не включены.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы (158 наименований) и двух приложений. Общий объем диссертации 272 страницы, включая 15 рисунков и 16 таблиц.

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

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

ствуюхцих методов и обосновываются новые подходы к их решению, предложенные в диссертации.

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

Задача оптимального линейного упорядочения состоит в следующем. Имеются взаимосвязанные точечные объекты с множеством номеров J = {1,...,п}, которые размещаются в позиции (не более чем по одному в каждую), находящиеся на линии на одинаковом расстоянии друг от друга. Структура связей между объектами определяется с помощью графа Г = (V, Е). Вершины соответствуют объектам, а каждая дуга (v,-, vj) из Е указывает на наличие связи между объектами с номерами i,j и имеет вес (удельную стоимость связи) СУ,- > 0. При этом предполагается, что Cij — Сц для любой дуги (v,-, Vj) Q Е. Требуется разместить вершины графа Г в указанные позиции так, чтобы суммарная стоимость связей между смежными вершинами была минимальной. Размещение задается с помощью перестановки 7Г вершин графа Г. Перестановка 7г является допустимой если 7r(t>,) < зт(vj) для любой дуги (Vi,Vj) £ Е. Задача состоит в поиске допустимой перестановки тг* такой, что:

min £ CvMv,) - *(vj)l = £ CyKfc) - 7r'(vj)\. (1) {vt,vj)eE E

Аналогично формулируется задача для неориентированного графа Г.

В п. 1.1 отмечено, что задача (1) iVF-трудна для произвольного графа Г и описан алгоритм трудоемкости 0(п log п) в случае, когда Г является композицией корневых деревьев и двухполюсных ориентиро-

ванных графов. Граф Г называется двухполюсным ориентированным графом, если в нем выделены две вершины и, и vt, соединенные вер-шинно непересекающимися ориентированными от vs к v¡ цепями. Нами доказана

ТЕОРЕМА 1.6. Задача оптимального линейного упорядочения для графа Г, являющегося композицией корневых деревьев и двухполюсных ориентированных графов, разрешима за O(nlogn) операций.

Для произвольного ориентированного графа Г в п. 1.2 разработан гибридный алгоритм комбинаторного типа решения задачи (1), основанный на динамическом программировании и методе ветвей и границ. На предварительном этапе в графе Г находятся корневые поддеревья и двухполюсные ориентированные подграфы, которые с помощью полиномиальных алгоритмов заменяются цепями. Проведён вычислительный эксперимент по сравнению гибридного алгоритма и алгоритма динамического программирования.

В случае, когда Г - двухполюсный неориентированный граф и Cij = 1 для (vj,vj) е Е (задача оптимальной нумерации), в п. 1.3 предложен алгоритм решения задачи (1) трудоемкости O(nlogn). Если C¡ — множество вершин цепи с номером г графа Г, соединяющей va и vt, |C¡| = п,- и цепи упорядочены так, что выполняются неравенства щ <п%< то справедлива

ТЕОРЕМА 1.7. Существует оптимальная нумерация 7Г вершин двухполюсного неориентированного графа Г вида:

... Сы, Сгь-2,..., С4, С2, vs, С\, vt, С3, С5, ..., Си-\, Си+1,... .

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

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

Одномерная задача размещения состоит в следующем. Множество прямоугольных объектов с габаритами сц х /г,-, г € центры которых связаны, размещаются на линии. Связи проходят вертикально от центров объектов до линии размещения, а затем вдоль нее, тогда задача сводится к размещению проекций геометрических центров прямоугольников на линию. Минимально допустимое расстояние между объектами с номерами i и j с учетом их габаритов обозначим через гу, а Л = (гу),Г{; = 0, г,3 € 1 — симметричная матрица минимально допустимых расстояний. Структура связей между объектами задается с помощью графа Г = [У,Е) (см. п. 1.1). Необходимо разместить объекты на линии таким образом, чтобы выполнялись ограничения на минимально допустимые расстояния и при этом суммарная стоимость связей между объектами была бы минимальной.

Координатная ось расположена вдоль линии размещения, и Х{ - координата центра объекта с номером г, г Е J■ Модель имеет вид:

£ — —* шш (2)

при ограничениях

к,- - > г<у, г,у € 7, г < 3. (3)

Задача (2), (3) является ЛТ-трудной, так как при условиях гу = 1,

1Ф 3 и Су ~ 1 Для ("п У}) € Я она эквивалентна задаче оптимального линейного упорядочения.

В п. 2.1 приведена постановка задачи (2), (3) и определена сложность ее решения для различных типов графа Г: цепи, корневого дерева и двухполюсного ориентированного графа. Доказана

ТЕОРЕМА 2.2. Если Г - корневое дерево, а элементы матрицы Н удовлетворяют неравенству треугольника, то задача (2), (3) является ИР-трудной.

Аналогичная теорема доказана для двухполюсного ориентированного графа.

В п. 2.2 исследуется задача (2), (3) для фиксированного порядка расположения объектов, определяемого перестановкой ж. Она принадлежит к классу задач ЛП, а двойственная является задачей нахождения оптимального потока. Изучается многогранное множество М(тг) указанной задачи ЛП. В частности, отмечается, что если элементы матрицы Я удовлетворяют неравенству треугольника, то М(п) является конусом для произвольной перестановки п. Кроме того, приводится другая эквивалентная задача ЛП, количество ограничений которой зависит от числа нарушений неравенства треугольника в матрице К.

Особое внимание в п. 2.3 уделяется изучению моделей целочисленного линейного программирования (ЦЛП) задачи (2), (3). Одна из моделей имеет следующий вид:

/1 (и) = X! Супу-* пип

(4)

при ограничениях

i,jeJ,i<j. (6)

X; — Xj — тц 4- Агц > О, X] - Хг - Гц + А(1 - г1;) > О,

«У €{0,1}

Значение булевой переменной гц указывает вариант взаимного расположения объектов с номерами г и з на линии, А - достаточно большая константа, непрерывные переменные и = (и^) для (ч»,^) £ Е связаны с расстояниями между объектами.

Предложены варианты построения моделей ЛП для задачи (4)-(6) и проведено исследование их многогранных множеств. В частности, показано, что при целочисленности элементов матрицы й все вершины будут иметь целочисленные компоненты, а также, что эти многогранные множества не являются квазицелочисленными. Исследована структура многогранного множества Г2:

Xi-Xj - Гц + Ахц > 0,

X] - х{ - щ + А( 1 - гу) > О,

0 < гц < 1

*,3 3-

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

Дадим некоторые определения. Пусть множество всех ¿-мерных целочисленных векторов, - символы лексикографического сравнения. Тогда Ь-разбиение пространства В? задается следующим образом. Пусть х,у € х у у. Будем говорить, что х эквивалентен у, если ле существует г 6 Я1*, такого, что х У г У у. Для произвольного V/ С В? через \У/Ь обозначим фактор-множество, образованное отношением эквивалентности Ь. Элементы множества \У/Ь называются

¿-классами. Множество V лексикографически больше V (V У V'), если у У у1 для всех у € V, у' € V.

компонент целые. Подмножество С? дробных Ь классов из \У/Ь называется цепью, если для любых V, V' 6 <5, V у V' не найдется г 6 IV П 2/^* такого, что V У г У V'. Обозначим через С{\¥) множество всех таких цепей в IV и определим степень "дробности" множества IV с помощью функции

Нами доказана

ТЕОРЕМА 2.4. Длл многогранного множества П при произвольном упорядочении координат вектора г справедлива оценка

В работе предложено упорядочение компонет вектора г, для которого доказана

ТЕОРЕМА 2.5. Для многогранного множества П при специальном упорядочении координат вектора г справедлива оценка

Из теорем 2.4 и 2.5 следует, что многогранное множество задачи (4)-(6) достаточно "насыщено" целыми точками и для ее решения можно применять алгоритмы ЛП с последующим .округлением нецелочисленных компонент.

В п. 2.5 описан алгоритм решения задачи (2), (3) с использованием модели (4)-(6) с помощью лексикографического перебора классов.

Пусть - множество всех ¿-мерных векторов, у которых первые 4

Ф(И0 = тах{|<3| : С} €

Ф(П) < (п — 1)(п — 2) + 1.

Кроме того, разработаны варианты комбинаторного алгоритма ветвей и границ для решения задачи размещения объектов на отрезке с фиксированными на нем объектами.

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

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

В п. 3.1 рассматривается следующая задача. Пусть дана связная неориентированная древовидная сеть Т = (У, Е). В узлах V — {«¿}, i El— {1,...,m} расположены фиксированные объекты. Новые объекты размещаются в точках Xj,X — (xj), j £ J, которые могут быть расположены как; в вершинах, так и на дугах. Расстояние р(х, у) между точками а: и у в сети Т определяется как длина кратчайшего пути. Известны Wij > О (vjij = Wji) i 6 I,j G J и Uß > 0 (ujk = Ukj) j,k € J

- стоимости связей между объектами, а су (су = с;1) и Ьд (Ьд = Ь/у) г £ /, j, к £ J задают ограничения на максимально допустимые расстояния между ними. Необходимо найти размещение объектов на сети Т, удовлетворяющее указанным ограничениям, в котором максимальная по стоимости связь имеет минимальное значение (минимаксный критерий). Модель имеет вид:

max(. тах Ujhp(xj,xk),. тах tuyp(v,-, Xj)) min, (7)

J<* »£/, JG«/ -Л

при ограничениях

Р{х,,хк) < bjk,j,k е J, j < к, (8)

P(v>, Xj) < су, i е j G J. (9)

Для проверки совместности ограничений (8) и (9) строится вспомогательная сеть N следующим образом (Francis R.L.). Каждому фиксированному объекту с номером i ставится в соответствие узел Е{, i £ /, а каждому новому объекту с номером j - узел Nj, j G J. Узлы £?,- и Nj соединяются дугой длины су, а узлы Nj и Nk - дугой длины bjk. Длина кратчайшего пути в сети N между узлами Ее и Et обозначается через L(Es,Et), s,t £ I. Ограничения (8), (9) эквивалентны следующим неравенствам:

L{Es,Et) > p(v„ vt), s,t е I, s<t. (10)

Для общей сети эти условия лишь необходимые. Найти допустимое размещение на дереве можно с помощью процедуры SLP (Sequential Location Procedure) трудоемкости 0(n(m+n)).

Введем дополнительную переменную г, обозначим min{zfujk,bjk) через min(z/W{j, Cij) через 5у(г) и перепишем задачу (7)-(9) в

эквивалентной форме :

z —> min (И)

при ограничениях

p(xj,xk) < pjk(z), j,k £ J, j < к, (12)

p{vuXj) < дф), г G /, je J. (13)

Для проверки совместности ограничений (12), (13) при фиксированном значении z строится сеть N(z) аналогично сети N.

Для решения задачи (11)—(13) предлагается алгоритм, состоящий из двух этапов. На первом этапе находится верхняя оценка гцв оптимального значения z* :

После первого этапа для значения z* определен интервал [zi, zy], zl < z* < zjj. Для значения zi не существует допустимого размещения, а для zu — существует.

На втором этапе применением деления пополам ищем оптимальное значение z*. Если для текущего z' не существует допустимого решения, то с помощью модификации процедуры SLP (Erkut Е., Francis R.L.) определяем пару вершин vs, vt, для которых нарушено условие (10). Из сети N(z) удаляем все узлы Ei, г ф s,t и получаем сеть Net(z). Далее алгоритмом Дейкстры находим кратчайший прямой путь (не содержащий вершин Е{, г ф s, t) в сети Nst(z') между узлами Еа, Et, длины az И- Ь, где а > 0, 6 > 0. Записываем модель ЛП для поиска кратчайшего пути между узлами (Es,Et) в сети Nsi(z), считая z параметром. С помощью двойственной задачи и условий дополняющей нежесткости находим интервал [21,23], на котором найденный для значения z' путь остается кратчайшим и функция L(ES, Et : z) линейная и равна az + Ь. Решаем уравнение az + & = p(vs,vt) и получаем значение z". Доказана

ТЕОРЕМА 3.1. Если для z" существует допустимое решение задачи (11)-(13) и z" G [zijz?], то z" - оптимальное значение целевой функции (11).

В п. 3.2 предложен алгоритм решения задачи размещения на древовидной сети Т с критерием минимума суммарной стоимости связей

£ Ujkp(xj,xh) +ЕЕ mjpivu xi) min, (14)

i.keJ, }<k iei jeJ Л

ограничениями (9) и условиями ху € V, V? £

На дереве Т вводим ориентацию дуг от произвольной корневой вершины IV, Е' - множество ориентированных дуг Т, V = V \ {г)г}, V/ -множество вершин поддерева с корнем V/. Для фиксированного размещения X — (^1,..., хп) и € V определим множества Я;,!^ С J, Я/ Г)1у1 = 0. Бели ^ е то путь из гу в х^ содержит вершину IV,'иначе

з е А.

Выберем произвольно вершину € V. Стоимость связей С;(Х-;, Л;) между объектами, проходящих через вершину у\ (или дугу (г-^, V;)), находится следующим образом:

ОД.д,) = Е £ и5к + Е Е £ Е (15)

тогда целевую функцию (14) можно представить в виде:

Е

Для того, чтобы найти минимум (14), достаточно минимизировать каждое слагаемое вида (15). Решение задачи (9), (14) сводится к решению т — 1 задач поиска минимального разреза в специальных сетях.

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

П. 3.4 посвящен квадратичным задачам о назначении на сетях. Заданы неориентированные граф Г1*' = (V, Е) и сеть М1У — V), символ IV означает, что ребра имеют веса. Ребро (г>,-, г^) € Е имеет вес аду > 0, а ребро (тг,-, п;-) € V - вес гу > 0. Считаем, что |У| = = т.

Размещение графа Г'*' на сети М™ - это взаимно однозначное соответствие 7г : V —¥ N. Необходимо разместить вершины графа в вершины сети таким образом, чтобы суммарная стоимость связей или максимальная связь между вершинами графа Tw были минимальными. Целевые функции имеют вид:

Е «'цРС'Ф'О >*■(";)) шш, (16)

= тт, (17)

где /^(г^тг^)) кратчайшее расстояние между вершинами тг(г;,) и 1г(у,) в сети

7г(г;;) ф 7г(г>у),г ф j. Такие задачи будем обозначать тройками (Ги (Г^М^.Гг).

Задачи (16) и (17) являются ДГР-трудными, так как Л/'Р-трудны задачи (Г, М, (задача оптимальной нумерации см. п. 1.3) и (Г,М, Рг) в случае, когда Г - произвольный граф, а М - цепь.

В диссертации предложены полиномиальные комбинаторные алгоритмы решения задач (ГИ\5И\*'1), (5^, М]где - взвешенная звезда, и некоторых других задач.

В п. 3.5 разработан алгоритм динамического программирования для решения задачи (Г^Т^,Рх), где Тъу - взвешенное дерево. Считаем, что нумерация вершин в каждом поддереве сплошная (п. 1.3) и номер подкорня больше номера любой вершины поддерева. Состояние в динамическом процессе зададим множеством номеров вершин I) = {»!,•• ■>*«} С I (гк ф ¿¡, к ф I) графа Г^, которые размещены в первых з вершинах сети Т™. Начальное состояние: £> = 0, конечное состояние: И — I. Переход от одного состояния к другому рассматривается как "движение" по вершинам сети Т^ в соответствии с заданной нумерацией.

В п. 3.6 изучается ¿-структура многогранника Мр, соответствующего модели ЦЛП задачи о р-медиане. Показано, что многогранник Мр имеет структуру "лучше", чем многогранное множество Г2 (см. п. 2.4) и для решения задачи о р-медиане можно применять различные релаксационные и эвристические алгоритмы.

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

В п. 4.1 приводятся постановки задач размещения на плоскости с прямоугольной метрикой и запрещенными зонами. Описан метод построения моделей ЦЛП для рассматриваемых задач. Обозначим через Р<,» € I фиксированные объекты и € 3 - новые объекты, которые необходимо разместить на той же плоскости. Стоимости связей обозначим как в гл. 3. Задано г прямоугольных запрещенных зон £ 2 = {1,..., г}, со сторонами, параллельными осям координат, Р = и.егР.'- Зона Р* - это прямоугольник [(4,4)>' (Ь'к> 4)]> где (а'к, 4) - координаты левого нижнего угла, а (Ь'к, с1'к) - правого верхнего. ■ Пусть X]), р(Х], Хк) - расстояния между соответствующими

объектами г £ I, j, к £ J. Необходимо разместить новые объекты Xi, i Е J вне объединения зон F так, чтобы минимальным было максимальное взвешенное расстояние:

max^ max ^ ujkp{Xh Хк), .rnax^ wijp{Pu X,)} ->■ min (18) при ограничениях

Xi$.F, j Е Z. (19)

Рассматривается аналогичная задача с целевой функцией

Е Щкр[Хи Хк) + £ Е ЩР{Ри Xj) min. (20)

j.keJ, j<k ieijeJ х

Для построения моделей ЦЛП задач (18), (19) и (19), (20) в случае прямоугольной метрики р(-, ■), представим область F = R2\F в виде объединения прямоугольных разрешенных зон. Предварительно строим контур (границу) области F. Ограничим область F прямоугольником [(Л,С), (5,£>)], где: А — min^ а'к, С = minjt В = таXkezb'k, D = max^gz d'k. Разрешенные зоны определяем внутри указанного прямоугольника перебором точек пересечения горизонтальных ребер контура F с вертикальными прямыми, проведенными по вертикальным ребрам контура F-

Для решения задач (18), (19) и (19), (20) предложены алгоритм ветвей и границ и эвристические алгоритмы. Проведен вычислительный эксперимент.

В п. 4.2 для решение задачи (18), (19) в случае п — 1 предложен алгоритм, состоящий из двух этапов: решение задачи (18) и размещение объекта на ребрах контура F.

Алгоритм решения задачи (19), (20) при п = 1 сводится к вычислению значений функции (20) в конечном множестве точек. Проведем через каждую точку Р,-, i Е I, вертикальную линию Z;, параллельную

оси OY и горизонтальную линию параллельную оси ОХ. Пронумеруем линии Z; слева направо от 1 до г, а линии к{ снизу вверх от 1 до q, обозначим через F' - контур области F, F" - множество угловых точек F'. Доказана

ТЕОРЕМА 4.2. Существует оптимальное решение X* задачи

(19), (20) такое, что X* е (IiПkj)U(/,-ПF')U ПF')UF", t = j =

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

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

Задача размещения объектов в позиции Р = {1,...,р}, р > п с известными расстояниями между ними D = (dy), dfi = 0, dy = dji, i, j 6 P заключается в следующем. Необходимо разместить п объектов в р позиций, не более чем по одному в каждую, таким образом, чтобы выполнялись ограничения на минимально (максимально) допустимые расстояния между объектами и суммарная стоимость связей была минимальной.

Каждому объекту с номером i 6 J сопоставим позицию <p(i) € Р, тогда модель задачи с минимально допустимыми расстояниями имеет вид:

£ CijdpWMi) min (21)

при ограничениях

dr(i)Mi) ^ ru'.bi € J,* < 3- (22)

Если n = p и отсутствуют ограничения (22), то указанная задача становится классической квадратичной задачей о назначении.

Пусть веса ребер графа Г перенумерованы и упорядочены следующим образом: С\ > Съ > ... > Сч, а элементы матрицы D -di<d2< ... < dw. Для нахождения нижней оценки функции (21) можно использовать минимальную сумму покомпонентного произведения указанных выше наборов. Такую процедуру можно рассматривать как линейную задачу о назначениях (ЗН), в которой стоимость назначения элемента г в позицию <р(г) равна С\г1,р^. Матрицу такой ЗН обозначим через Л = (Ast), s € Q — {l,...,g}, t G W — {l,...,tu}, которая будет во-первых, прямоугольной, а , во-вторых, иметь запрещенные элементы, т.е. получается специальная задача о назначениях (СЗН). В матрице Л для всякой строки s е Q можно указать такой номер столбца и>е, начиная с которого все элементы будут разрешенными Js = {fc|u>i < к < ш}. Пусть Ф однозначное отображение Q в W. Тогда СЗН можно записать следующим образом:

F{Ф) = £ Csdm min (23)

sSQ w

при ограничениях

Ф(а)бЛ, seQ. (24)

Если задача (23), (24) не имеет допустимого решения, то задача (21), (22) неразрешима, иначе оптимальное значение функции (23) является нижней оценкой для (21).

Пусть ¡с — это количество незапрещенных элементов в столбце с номером ® матрицы СЗН. Справедлива

ТЕОРЕМА 4.3. Для разрешимости СЗН необходимо и достаточно,. чтобы выполнялись неравенства

Для решения СЗН предлагается алгоритм, который либо находит оптимальное решение, либо устанавливает ее неразрешимость не более чем за q шагов.

Аналогичная схема может быть реализована в случае максимально допустимых расстояний между объектами. Кроме того, показано как можно использовать СЗН для задачи размещения прямоугольных объектов на линии (см. п. 2.1).

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

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

мальности.

В п. 5.2 построена двухкритериальная математическая модель целочисленного программирования оптимальной расстановки технологического оборудования швейного производства. Размещение производится на осевых линиях с учетом необходимых проходов между оборудованием. При этом структура связей (поток заготовок) между участком запуска (источник) и сборки готового изделия (сток) имеет вид двухполюсного ориентированного графа с одним объектом на каждой из цепей (см. п.1.1). Необходимо разместить прямоугольники с габаритами х hj,j £ J на заданном числе осевых линий таким образом, чтобы были прямые проходы заданной ширины между линиями и при этом максимальная суммарная длина модулей на осевых линиях и ширина прямоугольной области, занятой оборудованием, были минимальными. Модель целочисленного программирования такой задачи имеет вид:

f(z) = max{ £ ajzjk} -+ mm, (25)

KfzM jeJ

g(z) = E hjZjk} -> min (26)

кем ^J

при ограничениях

E ajzjk < L, keM, (27)

jeJ

E max{/ij2,t} + (|M| - 1) Д + 2<i < ff, (28)

кем

E zik = 1, i € J, • ,(29)

k£M

2зк e {o,i},у eJ,k ем, 1 (30)

где Zjk — 1 если j-й прямоугольник находится на линии к, иначе 0; М — множество номеров линий, L - длина цеха, Н - ширина цеха, Д - ширина прохода между линиями, d — минимальное техническое расстояние от боковой стены цеха.

Доказано, что задача (25)-(30) является ЛГР-трудной и для ее решения предложены алгоритмы последовательно одиночного размещения.

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

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

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

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

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

[1] Забудский Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы (с 1994 г. журнал переименован в "Дискретный анализ и исследование операций").. - 1990. - Вып. 30. - С. 35-45.

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

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

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

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

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

- 2004. - № 5. - С. 33-36.

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

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

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

[10] Забудский Г.Г. Оптимальное размещение взаимосвязанных объектов на древовидных сетях с ограничениями на расстояния // Журнал вычислительной математики и математической физики.

- 2006. - Т. 46, № 3. - С. 395-400.

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

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

[13] Забудский Г.Г. Задачи оптимального размещения взаимосвязан-

ч

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

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

[15] Забудский Г.Г. С? некоторых задачах размещения на графах // Тр.

XI Байкальской межд. школы-семинара "Методы оптимизации и их приложения". - Иркутск, 1998. - С. 135-138.

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

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

[18] Забудский Г.Г., Мотовилов В.А. Оптимальное размещение объектов на дереве с помощью динамического программирования //Тр.

XII Байкальской межд. школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2001. - Т. 1.- С. 144-149.

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

школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2001. - Т. 1. - С. 150-155.

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

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

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

[23] 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.

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

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

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

Подписало в печать 06.05.2006. Формат 60x84/16. Бумага офсетная. Отпечатано на ризографе. Усл. печ. л. 2. Уч.-изд. л. 2,0. Тираж 120 экз. Заказ №.

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

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

Введение

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

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.