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

¿ЬСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ШАМЕШ ПОЯИТЕШЧЕОШЙ ИНСТШУТ им.С.Ы.КИРОВА

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

ИВАНОВ Геннадий Алексеевич

УДК 514.174.2:519.853.6

ПРОЕКТИРОВАНИЕ РАЗМЩЕЗШ ШОСКШС ГЕОМЕТРИЧЕСКИ! ОБЪЕКТОВ МЕТОДАМИ НЕЛИНЕЙНОГО ПРОГРАШИРОВАНИЯ

Специальность.05.13.12 -

Системы автолата зацаи проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

Екатеринбург 1993

"Диссертационная работа выполнена в Марийском политехни ком институте.

НЛУЧпЬЙ РУКОВОДИТЕЛЬ СПЦИЛЛЬНИЕ ОППОНЕНТЫ

ЕЕДУЕрЕ ПРЕДПРИЯТИЕ

Защита диссертации состоится " -/6 " сьми/ил Iс - в "15 часов на заседании специализированного ученого сове K053.I4.I3 Уральского политехнического института. Отзывы в одном экземпляре, заверенные печатью, просим напра по адресу: 620002, г.Екатеринбург, К-2, УПИ, ученому секрет института, тел. 44-35-74.

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

Автореферат разослан " У6 « ' З.И'Ёб 19Э?г.

доктор технических наук, про Зайсбурд P.A.

доктор технических наук, про Ка»»аев В.А.,

кандидат технических наук, и ПСУП завода УРАЛЖШП Петун Уфимский авиационный институ

Ученый секретарь специализированного , --

совета, кандидат технических наук , Констанс

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

>

Актуальность гд^отк. Б настоящее зрем-~ для улучшения кач за объектов проектирования и повг :?ния произподительнооти трудь. шженеров в широком масштабе рагра*атывоотся систею азтоматиги-созанноро проектирования в различных отраслях промышленности. 3 основе многих из них --ат разнообразна задачи размещения гес метрических объектов. К ним относятся, в частности, такие актуа.т задачи технического и инженерного проектирования, как, напр «ер, проектирование маикннг:-: залов, опти?/изаиия складирования rj юв, проектирование интегралънкх схем, и др. Несмотря на много« теннне разработки, до сих пор остаются актуальннмч задачи опти-«ального раскроя. ■ Во многих отраслях промышленности рас яро .1 мате го в является необходимым этапом технологи ческо?! подготовил произ юдства и считается одни»» из основных источников экономии-матери гов. Под геометрическим объектом будем понижать геометрические )бразу физических тел. На плоскости этот образ представ шлется се !й граничей, которая предполагается кусочно-гладко" просто" зам ¡утой линией. В настоящий момент метод»! решения садач размещения ■зометрических- объектов характпргзуются разнообразием подходов, 'арантивуккцих зачастую локального оптимума решения. В бояыве* мз ito касается размещения о*&ектоя сложных форч. При таком положен Лтуалььч'ми. являются вопрось* разработки методоя, позволяющих с динмх попятай сводить некотор"'< круг задач размещения геометрич их объектов к задачам математического программирования, которое рпускали бы применение утя разпиты.: методов их решения. Получен-ое таким путем решение всегда обеспечивает то крзлже-л мере лояльность оптимума.

Щль тботы. Целью диссертационном работы является разработ а одного Метода сведения задач размещения плоских геометрически бтемтов к задачам математического программирования и его приме-ения при реяедаи некоторых задач.

Задачи исследования..

I.. Показать, что площадь пересечения Д".ух геометричзЬких бъектов может бить основой сведения задп-.j размещения плоских эомэтрических объектов к задаче математического программировали.

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

3. Ha ochoss вычислительных эксп-гр; мэнтов провести исследо-а;ше разработанной методики.

4. Привести пример применанил разработанного подхода для ормализацг:и некоторых задач. •

Нау'чат новиг.ча. В диссертационной работе получены следующй' аучные результаты:

1). Проведена формалиь-.цкя задач размещения геометрических бъок;^з на основе функции, определяющей плог^дь •.■з'ресег-;,?кия бъектов.

2). Разработан оригинальный алгоритм вычисления функции, оп еделяемс-й пло;_,\лДью пересечения двух многоугольников, и ее частых производных.

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

4). Разработана моди^икзг---. алгоритма безусловной митыиза-гяи функции кваэш ь.сгоноеским методом первого ранга-без одкомгр-гай !.!иним;иации.

Практкчас кг-.я ценность. Подучекг-ые результат:-: реализованы'в акплексс программ для решен« - задач размер-н>:я одинаковых фигу:: з ы;ауклой области и в об.^е.л произвольной формы п запретна/::

Eue хрниз комплекса позволяет находить оптихатьное решек-Яз, 1скл2'-й: •. или существенно уы-зньЕглть макетирование. Ванной c&taci применения комплекса программ является учебный процесс, йспользс занке программ освобождает студентов от рутинных работ при курковом и дипломнсл прсзктирооаник по ряду сгэциальностей, споссбс Eye? выработке творческого подхода к решению задач проектирован;

Реализация тлзуяьтатов. Рззультаты диссертационной работа i посредственно использовались:

при проектировании вкл-лд'.жей для упаковки одинаковых издел;

в стандартные контейнеры;

на лесосек

при разбиении ^отдельных участков лесоснрьевой базы Волжско] лесокомбллага территориального лесохозя>'.атзенг:зго производствен-кзго объединения "Марилее";

при курсовом и дипломном П-. эктировании по специальности 26.01 "Лесоинаенерное дело" для разбиения яесосырьево"- базы на лзсосеки.

Апробация работы. Основные полояония диссертационной pat>

0 клади вались и обсуждались на следу/гцих конференциях:

областной научно-технической конференции "Проблемы .автомата ации проектирования" (Свердловск, 1983);

научно-технической конференции "Проблемы и опыт применения истом автоматизированного проектирования в машиностроении" Свердловск, 1936);

Всесоюзной конференции "Математическое обеспечение рационал г-го раскроя в системах автоматизированного проектирования" Уфа, 1987);

научно-технических конференциях профессорсно-пргподзватзль-кого состава Марийского политехнического института (Йошкар-Ола, 38I-I9S5).

Публикации. Основное содержавшие работы отражено в 10 публи-

1ЦИЯХ.

Структура и объем тойоты. Диссертационная работа состоит з введения, четырех глав с выводами, списка используемой литера*. j и трех приложений.

Основная --асть работы содер;кит YZ9 страниц машинописного зкета, 4 рисунка, I таблица и сгпсск источников из 131 наимено-1НИЯ.

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

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

1 в постановках задач и методах их решения. Классификацию мето-IB решения трудно отделить от постановок задач. Выделяются зада; возникающие в некоторых математических дисциплинах. И«.» посвя-:нм работы Г.Минкозского, §.<Тота, К.Роджерса и др. Основной цел! :азанных работ является получение различного рода оценок, но в :х не рассматриваются размещения фигур. Из задач, возникаюцих посредственно из практических потребностей, наиболее paspaSoTai ми являшея задачи раскроя и'классификация, будем проводить на

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

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

Первую группу образуют методы, которые исходят из четкой, математической постановки. Однако, круг задач решаемых этими метода:;:;! узок. Это в основном гильотинный раскрой и планирование раскроя. Основателями этих методов являются Л.В.Кантароэич и Б.А.Залгаллер. Они свели эти задачи раскроя к задачам линейного программирования. Различные модификации симплекс метода явлчютс 5 н&стоящес время основными при решении такого класса задач. Существует целый ряд публикаций советских и зарубежных авторов, посв.уценных методам репения задач гильотинного раскроя с помощь :;дэй. и моделей динамического программирования. Большая практиче кая работа по созданию программного обеспечения гильотинного раскроя проделана в Уфимском авиационном институте под руководством Э.Л.Мухачзвах. К данной группе методов, видимо, можно сгнести метод зон для раскроя полубесконечной полосы на пряшуго/ ники, появившиеся в последнее время.

Вторую группу образуют методы построения укладок. Они применяйся для реикния задач прямоугольного я фигурного раскроя. Построение алгоритмов решения э'-.ой группы производится без испс зования математической модели исходной задач;;. Принципиальной чертой методов построения укладок является следугаций процесс. Пусть имеется ' 72 фигур. Определяется последовательность.фигур, называемая перестановкой. Производится процесс,укладки из 72 шагов.. На / -ом шаге укладывается /-а>я фигура из. данной последовательности. К кесткой конфигурации из £ фигур по некоторому, правилу. После размещения' П- -ой фигура оценива« ся качество полученного, размещения. •

Методы построения укладок, известные в литературе, отлича ся друг от друга правилами размещения очередной фигуры и прави лами определения очередной перестановки." Типичный метод постро ния укладок излагает в своих'работах,Ф.В.Бабаев. Имеется большое количество работ, выполненных а институте проблем мязмност ния АН УССР под руководством Ю.Г.Стояна, посвященных.задачам £ мещения геометрических-объектов. Данные работы излагают разли! вопросы метода построения укладок применительно к различным зг дачам практики, на основе понятия годографа функции плотного £ мещения.

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

Третью группу образуют методы, в которых общая задача разб1 а на несколько подзадач. Причем каадая подзадача является оптимизационной и существуют методы их решенля. Однако несогласо-анность целей не'поэ-\:ляет говорить об оптимальности решения, днным методом в основном решают задачи наиплотнейгаих решетчат.: кладок фигур сложных форм. Работы, посвященные этим задачам, ¡азбиваются на~две группы, отличающиеся своими подходами, руко-одителями которых соответственно являются Д.Б.Еслгжоваи Ю.Г.Стс ¡адо заметить, что в них рассматриваются задачи размещения толы ' прямоугольной области.

Целью исследования является разработка метода сведения за-,ач размещения к задаче математического программирования и обос-оваЯие работоспособности метода разработкой алгоритма численно] еше:>ая задач реиетчатого. размещения в области произвольной фор

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

• На плоскости положение любого геометрического объекта опре-.еляется параметра-.-я &,Ь, 0 , где С£ и Ь координаты полка, а (р угол позорота. Обозначим - площадь пересечени; 'бъектоз ?2 и £> , через - площадь выхода объекта с кн.'.лей площадью за объект с. большей площадью. Очевидно,

гч ~ шп > - >

Существует зависимость введенных величин от параметров положен«: '.е.

1 сбою счер-здь параметры положения могут зависеть от некоторых ■бобдекних парамзтроо задачи, т.е.

дэ - трехмерный вектор, завис яй от Л . словие непересечения или полного включения объектов и ^

трахаются соответственно соотношениями = О . и = ¿р

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

ТП6П Г¿X, Я], (I)

:ри ^ =¿7 ^(2)

(Ч&еЪ, (3)

Са», С4)

Ь(Х) О. (5)

;аесь /)Гх1 - вектов-шункция обичных ограничений; < ооъектов

<¡2 - множество,геометрических участвующих в размещении;

Н? ~ множество пар объектов, которые не должны пересекаться;

/X, - множество пар, для которых требуется полное вк; чоние оцного объекта-другим, менис вычислить зка-- ния хотя бы самих функций /* ;; п5

тбых значениях параметров позволяет для решения задачи (1-5) щ ¡енять любые, методы нелинейного программирования с эффективное?! >бычной для многоэкстремальных задач.

.Исследования «У^ : выявили сдедущие закономерности. . Пусть некото плоская фигура 7". с полюсом ( СС,Ь ) и тлом поворота р пересекается с некоторым геометрическим объ< •ом О . Границы Т и 6 в точках пересечения образуют угс 1Тличные от нуля. При движении в положительном направлении вдол! границы Т точкой в.хода в область является ( )

1 такой выход является ( )> тогда верна

Теорема I.

Я . (о)

- 7 -

Ж*-«'-я*

др

где £ - площадь пересечения

Следствие I. Пусть некоторая фигура Т с параметрами

<2,Ь, ф) пересекается с другой фигурой • б . Границы фи гут

¡ересекаюгся з точках ( а^} уЗ^; ), где / =1,2,...2к.

Ьчки пересечения пронумероваг:ы против часовой стрелки относите;]

ю Т . Точки с нечетными номерами являются точками входа в О

1 точках пересечения границы образуют углы, отличные от нуля.

£ - площадь пересечения фигур. Тогда существуют частные про-

зводные , , которые удовлетворяют

асе с/О с><р

словиям:

¿*ч

Гп2 -г2 ? СП

Гп2 -

Следствие 2. Пусть две фигурм с параметрами размещения й.?, рг ) и ( о2, )пересекаются в точках ( ^¿^Д образуют углы отличные от нуля. Пусть точки пересечения пронум: да относительно первой фигуры и перзсГ; точкой является точка »да границы первой фигуры внутрь зторол фигуры. Тогда справед-[вы соотношения

83 - - 22.

эя

Щ " ЭЬ<

...,2К,

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

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

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

2. Вычислить частные производные по точкам входа и выхода границ.

3. Граница области пересечения состоит из участков границ ка-ядого многоугольника, находящиеся, внутри другого. Определить все такие участки и вычислить площадь пересечения.

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

Пусть нужно заполнить заданную ограниченную область наибо! ним количеством одинаковых фигур в виде одной или двух решеток. Данные задачи являются частным случаем задачи (1-5) и имеет ви;

min f(x, S?J - -

при

где Tfff&J - мощность множества размещаемых фигур;

- площадь части ^ -ой фигуры, выходящей за

размещения.

.(15;

(16;

(и: (18;

- 9 -

р ' имеет вид

Р-. / ^ *8

О а

>

"де параметры размещения.

Задача упрощается, если область размещения выпуклая.

Пусть Q ~ , где Sc^ множество узлов то;

со первой решетки, a - множество узлов только втярок p-rv:

гл. Пусть фегЗ? и Vft'J, ' то

1ри этом пусть Ск ^ £)к и AjK ^ I ^ .

Ьгда количество элементов в i? равно

. *>fG) Z (Bjr-Ajc+iJ. (191

к-f J'CX

усть О = Gf(JG2 , где QK - множество узлов вида

AJK,J> X ( £jW>J,X- )Тгде JefC^&J .

Ke{Otf} •

Пусть , где

де Pip - максимальное расстояние от полюса фигуры до ее эрданы.

ри этих условиях моишо образовать агграф.-гую функцию вида

maj-ifoz: tfi+zrr*) (20)

ае ¿17 - положительная константа.

:ли !С1 — О , то имеем размещение -Т-игур из

параметром X

зиведепы формулы расчета частннх производных. Трудоемкость ре-2ния задачи существенно уменьшится из-за использования £ замен 57

<

Рассмотрим случай, когда область размещения имеет произвол; норму и возможно запретные зоны.

Пусть IV , где ¡V множество фигур, кото-

рые заведомо содержат искомое множество. С каждым элементом :вязываем переменную и» - Задача (15-13) преобразуется к видз

т1П,РГх,и) = -Ж. цА-, (2т:

1 *

(2з:

(24:

"очная штрафная функция, хогда норма Гельдера превращается в Евклидову, приводит ее к задаче'

min Ф(х, ¿¿J

зри о ^ U„ ^ М , где

у . ----(26:

uf + ТУИ z Sf

0 - множество узлов соседних к нулевому'узлу. 1ростота Ф от U , позволяет небольшими вычис-

лительными затратами освободиться от него. Введем функцию

Фа(х)= mir? ф{Х,и].

(2?:

iDH этом

Un- mln{H/(2~rj3} . <28

Значение R > О определяется уравнением

I

V

(20)

¡называется единственность положительного корня уравнения (29) предлагается итерационный процесс, которы" сходится за конэч->е число шагов. Приводятся Формулы для вычисления •

В третье:1 главе разработаны алгоритмы решетчатого размещения юметричееких объектов в ограниченной области.

Алгоритмы реаения задач решетчатого размещения одинаковых ггур в ограниченной области состоят из следующих чаете?*.

1. Вычисление штрафном функции и ее градиента.

2. Минимизация безусловной функции.

3. Организация решения задачи путем последовательной миними-1ции штрафной функпии с различных точек с разными значения!®? >щности множества размещаемых Лигур.

Необходимость рассмотрения алгоритмов размещения в выпукло"-!ласти, в области произвольной конфигурации с запретны?"/ зонами отдельно алгоритма минимизации вытекает из следующих уелоей?.

1. Организация решения задачи и вычисление штра^ноЯ функции шисит от способа (формирования штрафной функции, которая в свою даредь зависит от способа Армирования множества размещае?/!ых 1Гур.

2. Эффективность решения задачи в многом зависит от выбора ггоритма безусловной минимизации с учетом особенностей класса ¡нишэируемах йункци";. Особенностям класса используемых Функпи" зляется практическое отсутствие вычислительных затрат для нахок-5ния градиента.

Основными этапами в алгоритме вычисления функции (20) и ее задиента при размещении в выпуклой области являются:

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

- 12 -

определение пределов изменения индексов множества узлов т ккх, что соответствующие им фигуры могут иметь ненулеБую плаца г^рссеч^Н'лл с фигурой, соответстеувцс?: нулеьому узлу;

зьпгхлекие функции и ее градиента непосредственно по формулам .

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

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

Схема вычисления функции и ее градиента задач размещения в области произвольной конфигурации с запретными зонами имеет л входа. По первому входу множество размещаемых фигур И/ , и множество узлов соседних к нулевому узлу 3 должны быть из вестными. Функция и градиент вычисляются по соответствующим фор мулам, но предварительно должны быть вычислены Г^ , и их частные производные для /рс № и ¿; £¿3 •■ - После этого производится определение'система коэффициентов > кот

рое представляет итерационный процесс, состоящий из конечного числа Еагов. По второму входу производится определение множества Ж и 0 которое включает следующие этапы:

преобразование .параметров размещения с целью уменьшения значения векторов и угла поворота, которые составляют вектор па-раметроБ;

строится эллипс подобный некоторое исходному, но с количес вам узлов внутри него не превосходящим заданное число;

Из построенного эллипса выбираются узлы: в множество V/ наименьшими штрафами;

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

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

Общая схема решения задач размещения одинаковых фигур з 1сти произвольной конфигурации с запретными зонами попразделл I на подготовительную часть и сам процесс решения. Подготовите:» ая часть включает ввод геометрических объек:- =>, установления по с размерам величин необходимой точности, нахождения эллипса наи ;ньщей площади, описанного около области, и определение первона итьного значения количества ожидаемого размещения. Процесс реше-1я состоит из последовательной минимизации штрафной функции яри зследовательном уточнении значения Т и количества фигур ежи-аемого размещения.

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

1. Отсутствует минимизация вдоль направления.

2. Направление шага может совпадать с векторами - ¡/Т1"''^ •/У^р/г^-^уЛ^ру^ зависимости от признака выполненности или ^положительности матрицы

3. Длина шага выбирается по величине

з имеет ряд ограничений в зависимости от успеха или неудачи пре едущего шага.

В четвертой главе дается обоснование применимости разработз их методов для решения задач размещения.

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

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

2. Контур объекта должен быть аппроксимирован многоугольни-

ом.

3. Углы при вершинах не должны быть слишком острыми.

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

Программы

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

практики.

Программы решения резетчатого размещения в ограниченной о< ласти произвольной формы с запретными зонами применялись для проектирования разбие^шя леео сырьевой базы на лесосеки, которо! является необходимым этапом проектирования освоения лесосырьевс базы. Лесосека предстазляет из себя, как правило, прямоугольны! участок леса, который вырубается за один прием. Количество лесс сэк в решаемых задачах достигало 1000. При этом получены резул* ■таты, приемлемые для практики.

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

по 2Г , который составлен из.параметров положения подвижных малин. Приведены формулы для вычисления градиента этой функции. Размещение будет наДдено, если /г(/0гЛ=: & , ■ где £ до гаточно маленькая величина.

Произведен вычислительный эксперимент с алгоритмом безусло жнимизации. При этом разработанный"алгоритм испытывалоя на задачах решетчатого- размещения и на общепринятых тестовых задачах Ъиведен график минимизации 'функции (27), при котором получено допустимое размещение. Приведены графики минимизации некоторых тестовых задач. На основе сравнения результатов тестирования, «окно утверждать, что разработанный алгоритм безусловной минимизации не уступает хорошим алгоритмам, по количеству вычисления гункции, когда вычисление градиента приравняется к 72 еычис-тениям функции. Но если считать, что в тех алгоритмах преоблада-:т количество вычислений функции, то.этот алгоритм значительно !фбектиенее в классе функции, где трудоемкость вычисления значений функции существенно больше трудоемкости вычисления градиента.

рис.1 приведены графики, соответствующие мшг.Г'-.язапии |уше.г.г 7) при фиксированном количестве размещаемых фигур равном 14 к Т = .8325*10-!1. Эскиз, пг-лучйикыЗ в ходе резегая этой заца»«: здставЛен на рис.3. На рис.2 приводен график минимизации л Розенброка. На рлс.4 приводен эскиз разбиение лесосырьсзс;-* зы на лесосеки, полученный программой оптимального раз!."?щз::-гя л«аковьи£ 'в виде решетки в области произвольной фор:....: с заерзт-ии зонами.

Воококнш напраЕдг:-гие;.т дальнейшего развития разработанн;-;:-: годов яелястся расширение области их применения и и. :ользс^а-э современных методов глобапьноП оптимизации непрерывных цук;:~ й.

ОСНОВНЫЕ РЕЗУЛЬТАТ РАБОТЫ

1. Показано, что площадь пересечения геометрических сЗъектоз ляясь мерой их пересечения и одновременно штрафом за н? 'улеь--.-ловия непересечения, как «функция от координат полюсов и углоз ворота этих объектов, ночеет быть основой для подхода по формованию математической модели задач размещения геометрических ъентов. При этом задача представится как' задача математического ограммирования и для решения применимы ее численные методы.

2. Исследована зависимость площади пересечения двух геомет-ческих объектов от положения их полисов и углов поворота, з

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

3. Ка основе теоремы о частных производив;:: площади пересече-я разработан алгоритм вычисления площади пересечения двух про-еольнюс многоугольников и ее.частных производных ггч любых знаниях параметров их положения,.причем значения частных произвол,-:х' вычисляются без затрат в ходе вычисления значения площади пе-еечения.

4. Для оптимального размещения геометрических объектов, фор-лизованных на основе (функции, каждая из которых'является плоды» пересечения двух объектов, участвующих в размещении, пред-■авляется целесообразным с. вычислительной точки зрения и процес-I алгоритмизации применять методы штрафных функций.

, ' - 15 -

5. Сформирована штрафная функция и разработан алгоритм для решения задач однорешетчатого и двухрешетчатого размещения оди-чаг-.ГБЫх фигур в выпуклой области ¡¡а основе представления искомо го множества ыножестзом его граничных элементов.

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

7. Разработ: .- ^оригм поиска минимума функции к?лзиньюто-новс-ким методом крзого ранга без одномерной минимизации и уст; ковлено, что на известных тестовых задачах алгоритм не уступав' лучшим алгоритмам, с-сли считать вычисл • где градиента за Tl at числений функции, и, следовательно, значительно эффективен на .классе фунь:.:.г«1, где трудоемкость вычисления'значения функции сi щественно больше трудоемкости вычисления градиента, Использование алгоритма при решении практических задач показывает, что д. оптимизационных задач размещения геометрических объектов применим градиентный метод.

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

Основное содер:ание диссертации опубликовано в следующих работах. ■ -

1. Иванов Г.А. Задачи решетчатого размещения фигур в-зада ноЛ плоской области// Автоматизированные подсистемы поискового конструирования.-Горький, 1982. - С.53-63,. . -.

2. Иванов Г.А, Минимизация безусловной функции штрафа при рЕзмещении фигур/Автоматизированные.подсистемы поискового кон струирования.-Горький, 1981,- С.64-68.

3. Иванов Г.А. Зависимость площади-пересечения фигур от и расположения/Автоматизация поиска технических регений на ранн

- 17 -

1иях проектиров. ::ия.-йг- !.чар-0ла, 1982.- С. 120-136.

4.. Иванов Г.А. Решетчатое размещение фигур г.ен погс 'Проблемы автоматизации проектирования. Те^окл.-Сзердловсх, 3.- С.25-27.

5. Иванов Г.А. Метод штрафов в задачах размещения. Map.пол:!-.ин-т.-Йоакар-Ола, 1985.- 30 е.- Библногр.12 назв.-Рус.-Деп. Й?И, 18.03.86, I859-BS6.

6. Иванов Г.А. Решетчатое размещение фигур в области с за-тшми зонам:-. с использованием штрафа//Троблеш и опыт приме-ия систем автоматизированного проектирования в машиностроении. ..докл.-Свердловск, 1986.- С.24-35.

7. Иванов Г.А. Площадь пересечения как мэра перссенасуости г формализации и решении задач размещения на плоскости//.',!ате-гическое обеспечение рационального раскроя в системах автема-з.ировакного проектирования.Тез .докл.-Уфа, 198?.- С. 77-73.

8. Иванов Г.А.,, Гордеев СЛ. Моделирование процесса разме-ния лесосек на лесосырьевой базе.-Map.политех.ик-т.-Дол. II.03,С 2050- ДБ87.

9. Иванов Г.А. Решетчатое размещение фигур в замкнуто^ обла> [ с запретными зонами и связанные с ним вопросьг//Автоматиз-з:г-ifiopa и оценки проектных решений.-Йошкар-Ола, 1988.- С.70-77.

10. Иванов Г.А., Гордеев С.М., Третьяков В.З. Система а п тонизированного проектегования процесса лесосечно-транспорткого звоения лесосырьевой базы.- Инфотаац.шк.ч:;й листок Я 706., Map. элитзх.ин-т.-Йошкар-Ола, 1990,- 4 с.

- Id -

7io?ie4HCLsi позиция

Ряс. 3 .

.- Z1 -

Тазомс/ме

лесосыръевак базы на ' яесаселж

fíiC- Ч.