Методы и алгоритмы приближенного решения комплексной задачи компоновки

В «Основных направлениях развития народного хозяйства СССР на 1981;1985 годы и на период до 1990 года» указывается на «расширение автоматизации цроектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной развитие технической кибернетики и прикладной математики.

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

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

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

Существующая практика компоновок основывается на приблизительной оценке сравниваемых вариантов (полученных вручную), выбор которых во многом зависит от знания, опыта, интуиции инженеров, выполняющих цроект, и от существующих традиций. Основным методом, применяемым при компоновке машинного зала электростанции, цри разработке общего расположения оборудования на судах, является графический £з]. Однако при всех своих достоинствах этот метод имеет и определенные недостатки. Прежде всего, это связано с большим объемом чертежно-графической работы. Поэтому были сделаны попытки использовать макетно-мо-дельный метод []з ], получивший в последнее время широкое цри-менение цри проектировании промышленных предприятий. Необходимо отметить, что любой из этих методов, аребуя больших или меньших заарат на составление вариантов, не гарантирует отыскание оптимального решения.

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

В судостроении учет специфических особенностей каждого цроектируемого типа судна не исключает необходимость унификации технических решений, к примеру, для однотипных судовых энергетических установок (СЭУ). Единообразие компоновочных схем, единый принцип комплектования и размещения основного механического оборудования обеспечивает преемственность технических решений и позволяет наилучшим образом отрабатывать их на основе использования цредыдущего опыта. Блочный принцип компоновки [б] является новым црогрессивным направлением в проектировании расположения СЭУ.

Попытки автоматизированного решения задач компоновки общего расположения и, в частности, задач размещения оборудования в машинном отделении известны. В работах [б, 7 ] отмечается необходимость решения этой задачи в режиме диалога проектировщика и ЭВМ с помощью графического дисплея. В этих исследованиях содержатся ссылки на разработанную в рамках программы ВМС США по проектированию и постройке судов с применением ЭЦВМ интегрированную систему проектирования I й I) Б и на входящую в состав этой системы црограмму машинного проектирования общего расположения (СО&АР-Сопгри^ег &гарк1сб б! г1р Оллсигдегтгег^ Роодгалг).

В последнее время исследуются возможности проектирования судовых трубоцр оводов с помощью ЭВМ. На международном симпозиуме по судовым механизмам (Токио, 1973 г.) Вудворд? 8 ] (Мичиганский университет, США) цриводил примеры цроектирова-ния судовых трубопроводов с использованием ЭВМ. В Японии указанная проблема является темой обсуждения и исследуется различными судостроительными фирмами [э.

Что же касается использования математических методов и.

ВТ при компоновке многоэтажных производственных зданий, то следует отметить, что архитекторы ранее отказывались использовать вычислительную технику. «Среди представителей разных цро-фессий архитекторы наименее знакомы с инструментами системного анализа и исследования операции, а также, пожалуй, наиболее неохотно признают, что эти инструменты имеют место в их работе» 10 ]. Многие решения в процессе архитектурного проектирования субъективны и зависят от традиций, личного опыта или согласованности суждений заинтересованной технической группы. Необходимо расцределить обязанности между человеком и ЭВМ таким образом, чтобы обеспечить их эффективное взаимодействие в процессе решения задач проектирования.

Применение вычислительной техники требует от проектировщика в любой области систематизированного подхода к анализу этапов проектной деятельности. Системный подход позволяет расчленить задачу компоновки на подзадачи размещения и трассировки. К. Александер [ II ] (1962 г.) — один из первых авторов, который использовал теории систем, графов и множеств для разложения задачи архитектурного проектирования на подзадачи, поддающиеся решению. После этой процедуры он вновь комплектует все результаты для получения общего компромиссного решения. В настоящее время архитекторами широко используется теория графов и различные диаграммы для анализа и классификации исходной информации, для решения небольших задач планировки [ 12, 13 1.

В связи с декомпозицией задачи компоновки сделаем краткий анализ существующих математических методов решения задач размещения и трассировки. К наиболее ранним работам, посвященным проблеме автоматизации размещения, относятся разработки методик и црограмм размещения производственных зон, зданий и сооружений на промышленных площадках ?15 3. Размещаемые объекты в данном случае представляются в виде прямоугольников с размерами, кратными заданной величине. Площадка, где производится размещение, покрывается целочисленной решеткой, в узлах которой производится размещение. В качестве критерия для задачи компоновки выбраны частные функции цели, отражающие капитальные затраты на строительство зданий, сооружений, коммуникаций, а также эксплуатационные затраты. Аналогичный подход использован для разработки схем генеральных планов с црименением ЭВМ [16,17,18].

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

Состояние зарубежных разработок по пространственной компоновке хорошо освещено в обзоре [21 ]. Анализ некоторых из них приведен также в работе [22]. Следует отметить, что во всех этих методиках производится многократное решение задачи компоновки по этажам, при этом учитываются не только горизонтальные, но и вертикальные коммуникации.

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

I. Подход «последовательной замены частей размещения», который предусматривает наличие начального плана. В этой области можно назвать метод «КРАФТ» (1963) [23 ] в качестве первой работы.

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

Авторы Шавив и Гали в 1974 г. разработали программу, основанную на методике КРАФТ для оптимизации трехэтажного учебного здания, состоящего из 84 помещений [25] .

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

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

Среди известных авторов, которые разработали транспортную задачу для оптимизации размещения помещений внутри здания, можно назвать Мосли (1962 г.) [26 ] и Арчера (1963 г.).

27]. Используя метод транспортной задачи, можно получить такое размещение помещений, которое обеспечит минимальную стоимость коммуникационных связей между «самым важным» помещением и всеми остальными.

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

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

Таким образом, необходима разработка новых методов, лишенных этих недостатков. Перейдем к анализу существующих методов трассировки.

По-видимому, одним из первых, кто занимался математическими методами решения задач трасс^овки, был Л. Эйлер, сформулировавший в 1736 г. знаменитую задачу о кенигсбергских мостах [28 ]. В настоящее время решением задач оптимизации путей на графах, сетках занимаются многие советские ученые, в том числе Ю. М. Ермольев [29], A.A. Зыков [30 ], B.C. Михалевич [31], а также зарубежные ученые 0. Ope [32], Р. К. Прим [зз] и многие другие. Разработанные методы в рамках теории графов нашли широкое применение при решении практических задач оптимизации различных коммуникаций.

Значительный вклад в решение задач оптимизации путей на множествах внесли советские ученые А. Н. Колмогоров [?34 ], B.C. Михалевич [35], H.H. Моисеев [36], Л. С. Понтрягин [37], а также зарубежные ученые Р. Беллман [з8.], И.Экланд.

Учитывая особенность прикладных задач и возможности машинного моделирования, целееообразным является [31, 36, 40j развитие специальных и общих методов поисковой оптимизации, ориентированных на применение в автоматическом режиме. При построении математических моделей задач трассировки, превде всего, возникает вопрос о разработке модели допустимого пространства, в котором можно црокладывать коммуникации. Рассмотрением вопросов моделирования множеств при решении задач оптимального размещения геометрических объектов занимались П. Л. Чебышев [41],.

B.А. Залгаллер [42], Л. В. Канторович [43 ], Ф. Л. Тот [44 J. Развитие численных методов решения подобных задач геометрического характера цривело к появлению специальных методов геометрического моделирования, разработкой которых занимались В, Л. Рвачев [45], Ю. Г. Стоян [4б], зарубежные ученые А. Альбано [ 47], р. Кубиак [48].

Широкое црименение находят результаты исследований по оптимизации трассировки в радиоэлектронике. Решением задач в этой области плодотворно занимались советские ученые Л.Б.Абрай-тис [49], р.п. Базилевич [50], B.C. Линский [si], К. К. Морозов [52], а также зарубежные ученые С. Е. Дрейфус [бз] ,.

C.И. Ли [54J и др. Разработанные в этой области методы оптимизации на дискретных множествах (например, волновые, лучевые алгоритмы) применяются и в других областях.

Однако задача трассировки в энергетике, в судостроении, химической промышленности, в строительстве является значительно более сложной, так как решение необходимо построить на множестве ломаных в областях сложной геометрической формы. В этом случае возникает необходимость в совместном решении задачи размещения геометрических объектов и трассировки, ограничения и функционалы имеют специфический вид [ 55, 56, 57 J. Открытым является вопрос об оптимальном вложении в данное множество решений, полученных на дискретных моделях, часто это связано с необходимостью ручной доработки решений, полученных на ЭВМ, Вследствие этого необходимо ?55, 58, 59 j построение решения задачи трассировки непосредственно в данном множестве, это облегчает представление результатов решения и исходных данных в естественной для задач проектирования геометрической форме.

В настоящее время известны лишь две уникальные системы, выполняющие одновременно размещение и трассировку: серийно выпускаемая система &AELIC-COMPEBA fco] и экспериментальная система глобальной трассировки, разработанная фирмой bell Tloxtlгегп йебеагсК,(ВШ.

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

Хеллер и др. [623 вывели универсальные зависимости, позволяющие оценить возможность выполнения соединений во вновь разрабатываемых схемах еще до начала процесса компоновки. Метод позволяет определить вероятность реализации компоновки с небольшим количеством незавершенных соединений. Эти результаты можно использовать в качестве критерия приемлемости новых схемных разработок.

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

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

Для достижения этой цели следует остановиться на следующих этапах работы:

— анализ постановок реальных компоновочных задач, построение общей содержательной модели комплексной задачи компоновки, обоснование декомпозиционной схемы системы компоновки;

— разработка математической модели и методики решения комплексной задачи компоновки;

— построение модификации существующей математической модели задачи размещения геометрических объектов (сфер, цилиндров, параллелепипедов) с учетом специфических особенностей рассматриваемой комплексной задачи компоновки и взаимного влияния этапов размещения и трассировки в процессе решения поставленной задачи;

— разработка математической модели задачи телесной трассировки и структуры ее решения;

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

— 15.

Научная новизна работы.

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

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

Разработаны методы и алгоритмы решения задачи телесной трассировки.

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

Работа выполнена в Институте проблем машиностроения АН УССР (ИПМаш АН УССР) в соответствии с бюджетной темой № 59 «Создание математических методов, алгоритмов и про1рамм размещения геометрических объектов при проектировании в машиностроении», выполненной по постановлению Президиума АН УССР № 393 от 25 ноября 1976 г., номер государственной регистрации № 7704 5 552 (отчет ИПМаш АН УССР, Я Б 935 736, ВНТИЦентр, 1981 г.), с бюджетной темой № 73 «Разработка математических методов размещения Фобъектов и источников физико-механических полей в машиностроении», утвержденной постановлением Президиума АН УССР от 25 декабря 1980 г. № 604, а также в соответствии с планом обучения в аспирантуре без отрыва от цроизводства ИПМаш АН УССР и договорами о научно-техническом сотрудничестве, заключенными ИПМаш АН УССР с Научно-производственным объединением Цетрального научно-исследовательского и цроектно-конструкторского котлотурбинного института им. И. И. Ползунова (НПО ЦКТИ им. И.И. Ползунова), Ленинградским Ордена Ленина кораблестроительным институтом (ЛКИ), цроиз-водственным объединением Харьковский турбинный завод им. С. М. Кирова (ПОАТ «ХТЗ» им. С.М. Кирова).

Разработанный комплекс программ размещения геометрических объектов внедрен (Приложение I) с годовым экономическим эффектом 109 тыс. руб. в НПО ЦКТИ им. И. И. Ползунова в 1983 г. и внедрен в учебный цроцесс в ЛКИ.

Основные положения работы, выносимые на защиту.

Математическая модель комплексной задачи компоновки. Математическая модель задачи телесной трассировки.

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

Содержание работы доложено н, а :

Ш Всесоюзной конференции «Автоматизация поискового конструирования» (г.Иваново, 1983 г.) — Всесоюзной научно-технической конференции «Проектирование судовых корпусных конструкций» (г.Николаев, 1983 г.) — Ш Республиканской конференции «Вычислительная математика в современном научно-техническом процессе» (г.Канев, 1982 г.) — Республиканской научно-технической конференции «Методы и модели в системах автоматизированного проектирования энергетических турбоустановок» (г.Готвальд, 1979 г.) — Республиканской научно-технической конференции «Математические модели процессов, конструкций энергетических турбомашин в системах их автоматизированного проектирования» (г.Готвальд, 1982 г. Всесоюзном научно-црактическом семинаре «Прикладные аспекты управления сложными системами» (г.Кемерово, 1983 г.) — Межотраслевом семинаре «Атомно-водородная энергетика и технология» (г. Москва, 1983 г.) — У региональной школе-семинаре по оптимальному цроектированию и смежным воцросам (г.Ростов-на-Дону, 1982 г.).

Основной материал исследований опубликован в работах [78, 84, 97, 103, 105−113 ] .

Выводы.

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

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

3. Получен приемлемый вариант компоновки машинного зала электростанции дня турбины К-300−240.

ЗАКЛЮЧЕНИЕ

.

По результатам работы можно сделать следующие основные выводы:

1. Проведен общий анализ свойств и особенностей компоновочных задач в содержательной постановке.

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

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

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

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

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

7. Разработана структура и алгоритмы решения задачи телесной трассировки.

8. Созданы комплекс программ размещения объектов с учетом специфики рассматриваемого класса задач и комплекс.

Программ телесной трассировки, ориентированные на ЭВМ БЗСМ-6 и ЕС ЭВМ.

9. Проведена апробация предложенной методики на примере решения задачи компоновки машинного зала энергоблока.

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