Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА I. НЕФОРМАЛЬНАЯ ПОСТАНОВКА НЕКОТОРЫХ КОМПОНОВОЧНЫХ ЗАДАЧ
1.1. Задачи общего расположения на судах 18
1.2. Проектирование компоновки машинного зала энергоблока 24
1.3. Компоновка химико-технологических систем 28
1.4. Компоновка многоэтажных производственных зданий 31
1.5. Структура компоновочных задач и их место в системе проектирования 34
1.6. Модель комплексной задачи компоновки в категориях общей теории систем 41
Выводы 50
ГЛАВА 2. МАТКУІАТИЧЕСКАЯ МОДЕЛЬ КОМПЛЕКСНОЙ ЗАДАЧИ КОМПОНОВКИ
2.1. Математическая модель комплексной задачи компоновки 51
2.2. Математическая модель задачи размещения геометрических объектов
2.2.1. Формализация задачи размещения с использованием понятия Ф - функции 55
2.2.2. Матричное представление объектов размещения
2.3. Математическая модель задачи телесной трассировки 68
2.3.1. Основные сведения о задачах трассировки 69
2.3.2. Математическая постановка задачи телесной трассировки и ее особенности 75
2.4. Учет влияния обратной связи в математической модели комплексной задачи компоновки 86
Выводы 91
ГЛАВА 3. МЕТОДЫ И АЯГОРИТШ РЕШЕНИЯ КОМПЛЕКСНОЙ ЗАДАЧИ КОМПОНОВКИ 3.1. Общая схема решения комплексной задачи компоновки 92
3.2. Метод решения задачи размещения геометрических объектов
3.2.1. Метод последовательно-одиночного размещения 101
3.2.2. Размещение объектов, имеющих сложную геометрическую форму III
3.3. Структура решения задачи телесной трассировки 120
Выводы 126
ГЛАВА 4. ПРИМЕРЫ РЕШЕНИЯ МОДЕЛЬНЫХ И ПРАКТИЧЕСКОЙ ЗАДАЧ
4.1. Структурная схема комплекса программ размещения 128
4.2. Структурная схема комплекса программ трассировки 137
4.3. Анализ существующей методики решения задачи компоновки машинного зала электростанции и разработка нового подхода к решению 141
4.4. фактическая реализация. Пример компоновки машинного зала энергоблока .
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ Документы по внедрению результатов исследования
Введение к работе
В "Основных направлениях развития народного хозяйства СССР на 1981-1985 годы и на период до 1990 года" указывается на "расширение автоматизации цроектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники" \_1J , что, в свою очередь, предполагает дальнейшее развитие технической кибернетики и прикладной математики.
Сказанное в полной мере относится к важному для практики классу задач, имеющему название задач компоновки, которые связаны с размещением объектов различной физической природы и с построением схемы црокладки объемных комглуникации. Такие задачи возникают в различных отраслях промышленности: энергетике -при проектировании компоновки машинного зала электростанции; судостроении - при разработке общего расположения на судне; химической промышленности - при аппаратурно-технологической компоновке; строительстве - при определении объемно-планировочного решения многоэтажных промышленных зданий.
Цроцесс проектирования в настоящее время еще не поддается полному формальному описанию. Вследствие этого существуют несколько подходов к процессу проектирования. Сторонники первого подхода рассматривают процесс проектирования как интуитивный, не поддающийся наблюдению, и поэтому получивший название "черный ящик". Представители второго направления предполагают полностью систематизировать и описать процесс проектирования на формальном языке. Представители третьего направления считают, что для таких задач, как те, которые были перечислены выше, должны использоваться оба названных выше подхода.
Сложность формализации и разработки методов решения подобных задач обусловлена многими причинами, и в том числе отсутствием [2 J универсальных моделей, общепринятых критериев оптимальности.
Существующая практика компоновок основывается на приблизительной оценке сравниваемых вариантов (полученных вручную),выбор которых во многом зависит от знания, опыта, интуиции инженеров, выполняющих проект, и от существующих традиций. Основным методом, црименяемым при компоновке машинного зала электростанции, при разработке общего расположения оборудования на судах, является графический з J . Однако при всех своих достоинствах этот метод имеет и определенные недостатки. Прежде всего, это связано с большим объемом чертежно-графической работы. Поэтому были сделаны попытки использовать макетно-мо-дельный метод [3 J , получивший в последнее время широкое применение при проектировании промышленных предприятий. Необходимо отметить, что любой из этих методов, требуя больших или меньших затрат на составление вариантов, не гарантирует отыскание оптимального решения.
Отсутствие единых методологических принципов затрудняет осуществление качественных изменений в системах проектирования компоновок [4]. Преодолеть существующие недостатки можно, применив автоматизированный подход к решению задачи компоновки, который позволяет получить решения более приемлемые (с точки зрения проектировщика) в сравнении с известными в настоящее время подходами. При этом не отбрасывая опыт, накопленный за десятилетия, следует глубоко его проанализировать, систематизировать и обобщить, синтезировав его с новыми научными методами, подходами и т.д. Реализовать это можно, как показывает практика, используя современную вычислительную технику и математические методы.
В судостроении учет специфических особенностей каждого проектируемого типа судна не исключает необходимость унификации технических решений, к примеру, для однотипных судовых энергетических установок (СЭУ). Единообразие компоновочных схем, единый принцип комплектования и размещения основного механического оборудования обеспечивает преемственность технических решений и позволяет наилучшим образом отрабатывать их на основе использования предыдущего опыта. Елочный принцип компоновки [5 J является новым прогрессивным направлением в проектировании расположения СЭУ.
В последнее вреда исследуются возможности проектирования судовых трубопроводов с помощью ЭВМ. На международном симпозиуме по судовым механизмам (Токио, 1973 г.) Вудворд 8 ] (Мичиганский университет, США) приводил примеры проектирования судовых трубопроводов с использованием ЭВМ. В Японии указанная проблема является темой обсуждения и исследуется различными судостроительными фирмами [9 J.
Что же касается использования математических методов и ВТ при компоновке многоэтажных производственных зданий, то следует отметить, что архитекторы ранее отказывались использовать вычислительную технику. "Среди представителей разных профессий архитекторы наименее знакомы с инструментами системного анализа и исследования операции, а также, пожалуй, наиболее неохотно признают, что эти инструменты имеют место в их работе".
Многие решения в процессе архитектурного проектирования субъективны и зависят от традиций, личного опыта или согласованности суждений заинтересованной технической группы. Необходимо распределить обязанности между человеком и ЭВМ таким образом, чтобы обеспечить их эффективное взаимодействие в процессе решения задач проектирования.
Применение вычислительной техники требует от проектировщика в любой области систематизированного подхода к анализу этапов проектной деятельности. Системный подход позволяет расчленить задачу компоновки на подзадачи размещения и трассировки. К. Александер [ II ] (1962 г.) - один из первых авторов, который использовал теории систем, графов и множеств для разложения задачи архитектурного проектирования на подзадачи, поддающиеся решению. После этой процедуры он вновь комплектует все результаты для получения общего компромиссного решения. В настоящее время архитекторами широко используется теория графов и различные диаграммы для анализа и классификации исходной информации, для решения небольших задач планировки .
В связи с декомпозицией задачи компоновки сделаем краткий анализ существующих математических методов решения задач размещения и трассировки. К наиболее ранним работам, посвященным проблеме автоматизации размещения, относятся разработки методик и программ размещения производственных зон, зданий и соо - 9 ружений на промышленных площадках [15 3 . Размещаемые объекты в данном случае представляются в виде прямоугольников с размерами, кратными заданной величине. Площадка, где производится размещение, покрывается целочисленной решеткой, в узлах которой производится размещение. В качестве критерия для задачи компоновки выбраны частные функции цели, отражающие капитальные затраты на строительство зданий, сооружений, коммуникаций, а также эксплуатационные затраты. Аналогичный подход использован для разработки схем генеральных планов с применением ЭВМ [16,17,1.
В работе [19] сообщается о разработке программы для ЭВМ, предназначенной для компоновки моногоэтажного здания. В диссертационной работе [20 J делается попытка оптимизации решений многоэтажных общественных зданий. При этом учитывается многокритериальное ть задачи. Для поиска вариантов компоновок применяется метод динамического программирования.
Состояние зарубежных разработок по пространственной компоновке хорошо освещено в обзоре [21 J . Анализ некоторых из них приведен также в работе [22 J . Следует отметить, что во всех этих методиках производится многократное решение задачи компоновки по этажам, при этом учитываются не только горизонтальные, но и вертикальные коммуникации.
При анализе существующих методов оптимизации на ЭВМ планировочных решений на начальной стадии проектирования были выделены два главных направления, на которых основаны эти методы:
I. Подход "последовательной замены частей размещения", который предусматривает наличие начального плана. В этой области можно назвать метод "КРАФТ" (1963) [23 J в качестве первой работы.
Попытка внедрения факторов, учитывающих функциональные и пространственные требования объекта при формировании и оценке решений, была сделана группой советских авторов при компоновке одноэтажных промышленных зданий [24 J .
Авторы Шавив и Гали в 1974 г. разработали программу, основанную на методике КРАФТ для оптимизации трехэтажного учебного здания, состоящего из 84 помещений L25 J .
Основным недостатком методов последовательной замены частей размещения является то, что оптимальное решение находится только после составления всех возможных вариантов расстановок. Дополнительные недостатки этого метода - конечное решение зависит от конфигурации первоначального исходного плана; замена элементов плана возможна только тогда, когда они имеют равный размер. Из-за имеющихся недостатков весьма ограничено применение этих методов.
П. Прямой подход, при котором используются исходные данные для создания единственного решения безотносительно к какому-нибудь первоначальному плану. Этот подход включает транспортные методы и конструктивные.
Среди известных авторов, которые разработали транспорт -ную задачу для оптимизации размещения помещений внутри зда -кия, можно назвать Мосли (1962 г.) [26 ] и Арчера (1963 г.) [27J . Используя метод транспортной задачи, можно получить такое размещение помещений, которое обеспечит минимальную стоимость коммуникационных связей между "самым важным" помещением и всеми остальными.
Конструктивный подход в отличие от изложенных пользуется эвристическим алгоритмом для создания плана, близкого к оптимальному. Решение производится с помощью последовательных размещений компонентов помещений на плане. Первая программа этого типа была разработана Вайтхедом и Элдарсом в 1964 г. Вычисляется синтетический порядок важности и согласно этому располагаются компоненты на плане.
Анализ всех работ, ведущихся по двум направлениям, позволяет сделать следующие выводы: ни один метод не удовлетворяет основным требованиям планировки многоэтажных зданий; все они, кроме методов Арчера и Мосли, решают только проблему планировки здания до 3-х этажей; методы же Арчера и Мосли можно ис -пользовать только при решении определенных задач, таких как реконструкция существующих зданий; определение путей циркуляции затруднено при применении любого из этих методов; в случае решения задач большой размерности применение этих методов затруднительно из-за большой затраты времени работы на ЭВМ.
Таким образом, необходима разработка новых методов, лишенных этих недостатков. Перейдем к анализу существующих ме -тодов трассировки.
По-видимому, одним из первых, кто занимался математическими методами решения задач трассировки, был Л.Эйлер, сформулировавший в 1736 г. знаменитую задачу о кенигсбергских мостах [28 J . В настоящее время решением задач оптимизации путей на графах, сетках занимаются многие советские ученые, в том числе 10. М. Ермольев [29], А.А. Зыков [зо] , B.C. Михалевич [Зі] , а также зарубежные ученые 0. Ope [32J , Р.К. Прим [зз] и многие другие. Разработанные методы в рамках теории графов нашли широкое применение при решении практических задач оптимизации различных коммуникаций.
Значительный вклад в решение задач оптимизации путей на множествах внесли советские ученые А.Н. Колмогоров [34 ] , B.C. Михалевич [35] , Н.Н. Моисеев , Л.С. Понтрягин [37 J , а также зарубежные ученые Р. Беллман[з8.], И.Экланд [зэ] и др.
Учитывая особенность прикладных задач и возможности ма - 12 шинного моделирования, целесообразным является [31, 36, 40 3 развитие специальных и общих методов поисковой оптимизации, ориентированных на применение в автоматическом режиме. При построении математических моделей задач трассировки, прежде всего, возникает вопрос о разработке модели допустимого пространства, в котором можно прокладывать коммуникации. Рассмотрением вопросов моделирования множеств при решении задач оптимального размещения геометрических объектов занимались П.Л. Чебышев [41 ] , В.А. Залгаллер [42] , I.B. Канторович [43] , Ф.Л. Тот [44]. Развитие численных методов решения подобных задач геометрического характера привело к появлению специальных методов геометрического моделирования, разработкой которых занимались В.Л. Рвачев [45 J , Ю.Г. Стоян [4б] , зарубежные ученые А.Альбано [47] , Р. Кубиак [48].
Широкое применение находят результаты исследований по оптимизации трассировки в радиоэлектронике. Решением задач в этой области плодотворно занимались советские ученые Л.Б.Абрай-тис [49] , р.п. Базилевич [50] , B.C. Линский [бі] , К.К. Морозов [52 J , а также зарубежные ученые СЕ. Дрейфус [53J , СИ. Ли [54] и др. Разработанные в этой области методы оптимизации на дискретных множествах (например, волновые, лучевые алгоритмы) применяются и в других областях.
Однако задача трассировки в энергетике, в судостроении, химической промышленности, в строительстве является значительно более сложной, так как решение необходимо построить на множестве ломаных в областях сложной геометрической формы. В этом случае возникает необходимость в совместном решении задачи размещения геометрических объектов и трассировки, ограничения и функционалы имеют специфический вид [ 55, 56, 57 ] . Открытым является вопрос об оптимальном вложении в данное множество решений, полученных на дискретных моделях, часто это связано с необходимостью ручной доработки решений, полученных на ЭВМ, Вследствие этого необходимо [55, 58, 59 j построение решения задачи трассировки непосредственно в данном множестве, это облегчает представление результатов решения и исходных данных в естественной для задач проектирования геометрической форме.
В настоящее время известны лишь две уникальные системы, выполняющие одновременно размещение и трассировку: серийно выпускаемая система &AELIC-COMPEBA [ео] и экспериментальная система глобальной трассировки, разработанная фирмой.
Метод компоновки, предложенный Мидом L6IJ , в известном смысле также сочетает размещение и трассировку. Проектирование построено таким образом, что большинство модулей (этот метод и предыдущие два используются при компоновке электронных схем) разрабатываются с учетом общего построения схемы; небольшие модули вписываются в более крупные. Большая часть размещения предопределяется заранее общей компоновкой схемы, а разводка осуществляется путем стыковки модулей.
Хеллер и др. [62J вывели универсальные зависимости, позволяющие оценить возможность выполнения соединений во вновь разрабатываемых схемах еще до начала процесса компоновки. Метод позволяет определить вероятность реализации компоновки с небольшим количеством незавершенных соединений. Эти результаты можно использовать в качестве критерия приемлемости новых схемных разработок.
Размещение, приближенная трассировка и окончательная трассировка взаимосвязаны, хотя решение каждой задачи в отдельности уже достаточно сложно. Здесь кроется объяснение того, почему задача компоновки традиционно решается в несколько этапов: размещение, приолиженная трассировка и окончательная трассировка.
Сказанное позволяет считать актуальными следующие задачи, исследование которых составляет цель настоящей р а б о ты: разработка математической модели комплексной задачи компоновки и методики (схемы) ее решения, а также использование этой методики и комплекса программ для решения реальных задач, возникающих в практике проектирования.
Для достижения этой цели следует остановиться на следующих этапах работы:
- анализ постановок реальных компоновочных задач, построение общей содержательной модели комплексной задачи компоновки, обоснование декомпозиционной схемы системы компоновки;
- разработка математической модели и методики решения комплексной задачи компоновки;
- построение модификации существующей математической модели задачи размещения геометрических объектов (сфер, цилиндров, параллелепипедов) с учетом специфических особенностей рассматриваемой комплексной задачи компоновки и взаимного влияния этапов размещения и трассировки в процессе решения поставленной задачи;
- разработка математической модели задачи телесной трассировки и структуры ее решения;
- создание комплекса программ открытого типа как алгоритмической базы для автоматизированного решения задач проектирования компоновок в энергетике, судостроении, строительстве химической промышленности.
Научная новизна работы
Построена и исследована математическая модель комплексной задачи компоновки, которая вследствие специфики рассматриваемых практических задач представляет собой иерархическую систему математических моделей: модели задачи размещения геометрических объектов и модели задачи телесной трассировки.
Разработана методика решения комплексной задачи компоновки и алгоритмическая база ее реализации в виде комплекса программ открытого типа.
Разработаны методы и алгоритмы решения задачи телесной трассировки.
Построены алгоритмы решения задачи размещения геометрических объектов сложной формы (тел, составленных из наборов сфер, цилиндров и параллелепипедов).
Работа выполнена в Институте проблем машиностроения АН УССР (ИПМаш АН УССР) в соответствии с бюджетной темой № 59 "Создание математических методов, алгоритмов и программ размещения геометрических объектов при проектировании в машиностроении", выполненной по постановлению Президиума АН УССР & 393 от 25 ноября 1976 г., номер государственной регистрации $ 77045552 (отчет ИПМаш АН УССР, № Б 935736, ВНТЩентр, 1981 г.), с бюджетной темой № 73 "Разработка математических методов размещения Ф -объектов и источников физико-механических полей в машиностроении" утвержденной постановлением Президиума АН УССР от 25 декабря 1980 г. $ 604, а также в соответствии с планом обучения в аспирантуре без отрыва от производства ИПМаш АН УССР и договорами о научно-техническом сотрудничестве, заключенными ИПМаш АН УССР с Научно-производственным объединением Цетрального научно-исследовательского и проектно-конструкторского котлотурбинного институ - 16 та им. И.И. Ползунова (НПО ЦКТИ им. И.И. Ползунова), Ленинградским Ордена Ленина кораблестроительным институтом (ЛКИ), производственным объединением Харьковский турбинный завод им. СМ. Кирова (ПОАТ "ХТЗ" им. СМ. Кирова).
Разработанный комплекс программ размещения геометрических объектов внедрен (Приложение I) с годовым экономическим эффектом 109 тыс. руб. в НПО ЦКТИ им. И.И. Ползунова в 1983 г. и внедрен в учебный процесс в ЛКИ.
Основные положения работы, выносимые на защиту
Математическая модель комплексной задачи компоновки. Математическая модель задачи телесной трассировки.
Двухуровневая методика решения комплексной задачи компоновки. Методы и алгоритмы решения задачи телесной трассировки. Методы и алгоритмы решения задачи размещения геометрических объектов сложной формы.
Всесоюзной конференции "Автоматизация поискового конструирования" (г.Иваново, 1983г.); Всесоюзной научно-технической конференции "Проектирование судовых корпусных конструкций" (г.Николаев, 1983г.); Ш Республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе" (г.Канев, 1982г.); Республиканской научно-технической конференции "Методы и модели в системах автоматизированного проектирования энергетических турбоустановок" (г.Готвальд, 1979 г.); Республиканской научно-технической конференции "Математические модели процессов, конструкций энергетических турбомашин в сие - 17 темах их автоматизированного проектирования"(г.Готвальд,1982г.); Всесоюзном научно-црактическом семинаре "Прикладные аспекты управления сложными системами" (г.Кемерово, 1983г.); Межотраслевом семинаре "Атомно-водородная энергетика и технология" (г. Москва, 1983г.); У региональной школе-семинаре по оптимальному проектированию и смежным вопросам (г.Ростов-на-Дону, 1982г.).
Основной материал исследований опубликован в работах [?8, 84, 97, 103, I05-II3 ] .
