Содержание к диссертации
Введение
1. Анализ задач эффективного раскроя сырья и обзор методов их решения
1.1. Общая постановка задачи эффективного раскроя сырья 12
1.2. Методы и алгоритмы получения эффективного решения в задачах раскроя 24
1.3. Учет неопределенности при решении задач эффективного раскроя 33
1.4. Выводы по главе 37
2. Эффективный раскрой области .
2.1. Постановка задачи раскроя при условии полной информации об объектах . 38
2.2. Эффективный раскрои области в случае детерминированной оптимизационной задачи 46
2.3. Постановка задачи раскроя в условиях неопределенности 66..
2.4. Эффективный раскрой области в условиях интер-вально заданной неопределенности 74
2.5. Выводы по главе 80
3. Описание алгоритмов нахождения эффективного решения в задачах раскроя
3.1. Общий алгоритм эффективного раскроя произволь ной области 82
3.2. Алгоритм эффективного раскроя сырья в условиях непределенности 85
3.3. Алгоритм вписывания окружности наибольшего радиуса в выпуклый многоугольник 97
3.4. Общее описание интерактивного режима ЛИР-ЭВМ для решения задачи эффективного раскроя алмаза 103
3.5.Выводы по главе 121
4. Оптимизация отдельных стадии технологического процесса изготовления бриллиантов
4.1. Общая характеристика процесса изготовления бриллиантов 123
4.2. Оптимизация процесса разметки кристаллов алмаза под бриллианты 131
4.3. Выводы по главе 146
Заключение 147
Список литературы
- Общая постановка задачи эффективного раскроя сырья
- Методы и алгоритмы получения эффективного решения в задачах раскроя
- Постановка задачи раскроя при условии полной информации об объектах
- Алгоритм эффективного раскроя сырья в условиях непределенности
Введение к работе
В настоящее время,когда большинство производственных процессов становятся автоматизированными,а технология в значительной мере базируется на достижениях развития вычислительной и измерительной техникумы вступаем в эпоху научно обоснованных производственных процессов.Поэтому возрастает важность проблем оптимального управления.Решение этих проблем позволит обеспечить экономию ценного сырья и электроэнергии ,довести до максимума эффективность использования производственных агрегатов и т.д.
Эффективность большого числа производственных процессов во многом определяется степенью использования ресурсов.К таким производственным процессам можно отнести металлообработку.швейное и обувное производство ,обработку драгоценных и полудрагоценных камней,использование ресурсов складских помещений и многие другие технологические процессы и производства в целом.Характерной чертой этих производств является тот факт,что более оптимальное использование сырья в производственном процессе дает прямой экономический эффект.
Задача рационального использования ресурсов может быть решена системой эффективного раскроя ,включающей аппаратные и программные модули рис.В.1.
В конечном итоге при раскрое сырья приходиться управлять специальным оборудованием (станки с числовым программным управлением, лазер и т.д.).Особое место здесь должно быть отведено алгоритму управления.Управляющее воздействие должно формироваться на основе найденного лучшего варианта.Такой подход может решить проблему оптимизации управления о достижением конечного резуль-
I—>
Д—41
&У
3_Vo
:>
Объект
^
^>
Устройство управленця
Л П Р
СП I
НУ - вычислительное устройство; НУ
ДІР - лицо принимающее решение. Р
Q - критерии оптимизации; U
4Q - задание на оптимальное управление; У
исполнительное устройство} вектор исходных данных; управляющее воздействие; вектор фазовых координат системы.
Рис.ВЛ.Система управления эффективным раскроем сырья .
- и -
тата по эффективному использованию сырья.
В данной диссертационной работе исследуется одна из составных частей общей автоматизированной системы эффективного раскроя сырья и предлагается алгоритм оптимального управления в ней.
Оптимизационный подход к постановке и решению задач синтеза сложных технических систем является резервом повышения качества управлений [1-43.
Появление и быстрое оснащение средствами вычислительной техники создает хорошие перспективы для широкого использования современных математических методов для решения большого класса практических задач.Разработка математических моделей сложных объектов управления,проектирования ,а также разработка специальных математических методов позволяет во многих случаях существенно повысить эффективность существующих производственных и технологических процессов.
Проблему рационального использования ресурсов на одном из этапов можно представлять как задачу рационального раскроя промышленного сырья,а в формализованном виде как задачу эффективного размещения физических объектов в заданном объеме либо на заданной поверхности.
Причем,чисто из геометрических соображений решить общую задачу эффективного раскроя невозможно,так как изготовителю продукции важно не просто выпустить побольше любых изделий,а необходимо получить максимально возможную прибыль при переработке промышленного сырья.Так при обработке кристаллов алмаза можно изготовить бриллианты различной формы и величины.В этом случае необходимо так раскроить кристалл,чтобы стоимость полученных из него бриллиантов получилась максимальной.Далеко не всегда более
крупные бриллианты с дефектами дороже более мелких, но бездефектных. Бриллианты же разной формы .например маркиз, багет,изумруд, имеющие одинаковую массу заметно различаются по стоимости. В легкой промышленности из одного и того же отреза ткани можно выкроить меньшее количество особомодных и дорогих изделий и получить большую прибыль,чем если бы делать большее количество устаревших и не пользующихся спросом моделей одежды.Естественно, что производитель будет изготавливать более медные изделия .если даже отходы сырья будут значительнее,чем при изготовлении устаревших моделей.Кроме всего вышесказанного,имеющиеся факторы неопределенности,такие например как цены на продукцию или невозможность точно измерить координаты расположения дефектов в кристалле,не позволяют использовать чисто геометрические преобразования для эффективного раскроя сырья.
Использование известных методов оптимизационных процедур для решения этой задачи сталкивается с целым рядом трудностей.Это прежде всего сложность получения математической модели задачи оптимизации .большая размерность области допустимых решений, многоэкстремальность функции цели,элементы неопределенности при описании области раскроя.
Наличие трудно формализуемых свойств объекта,ряда неконтролируемых параметров и возмущений приводят к необходимости поиска других (новых) постановок задачи оптимизации.В связи с этим в работах различных авторов С5-7] отмечается неприемлемость точечных задач оптимизации для управления в условиях неопределенности. В качестве решения предлагается искать некоторое допустимое множество решений ,обладающее некоторыми заданными свойствами.
Как будет показано в последующих разделах данной работы,даже
сама формальная постановка задачи эффективного раскроя имеет множество различных вариантов .причем каждый из них имеет свою область практического применения.
Цель работы.
Целью диссертационной работы является исследование математических методов и разработка алгоритмов (программ) управления эффективным раскроем сырья.
Для достижения указанной цели в работе были поставлены и решены следующие основные задачи.
1.Разработка алгоритмов управления эффективным раскроем сырья в детерминированном случае (математическая формулировка и исследование детерминированной задачи эффективного раскроя).
2. Исследование задачи эффективного раскроя сырья в условиях неопределенности (выявление источников возникновения факторов неопределенности,математическая формулировка задачи эффективного раскроя в условиях неопределенности).
3.Разработка методов и алгоритмов решения задачи эффективного раскроя в условиях неопределенности.
Методы исследования.
При решении задач исследования использовались аппарат и методы из области теории оптимизации»теории множеств и математического анализа.Достоверность теоретических исследований подтверждена данными эксперимента.
Научная новизна.
1.Предложен алгоритм решения детерминированной задачи объемного раскроя с целевой функцией,представляющей максимальную суммарную стоимость разметаемых объектов.
2.Исследована и сформулирована задача эффективного раскроя в
условиях неопределенности с функцией цели, представляющей максимальную суммарную стоимость производимых из имеющегося сырья изделий.
3.Предложен новый подход к решению задачи эффективного раскроя в условиях неопределенности, использующий понятие "степень чувствительности решения" и гарантированный результат. Практическая ценность .
В диссертационной работе разработаны алгоритмы и программы, объединенные в единую систему, имеющую законченный вид и прошедшую производственные испытания.Практическая ценность системы заключается в экономии сырья и повышении экономических показателей производства при ее иопользований.Практическая ценность работы подтверждена результатами производственных испытаний.
Реализация результатов.
Результаты исследований использованы' в технологическом процессе .обработки кристаллов алмаза на Ш Кристалл г.Смоленск ,а также на ряде других предприятий аналогичного типа.
Диссертационная работа выполнена по тематике научно-исследовательской работы проводимой кафедрой автоматики смоленского филиала УЖ с СКТБ "Кристалл" ,посвященной обработке кристаллов алмаза и поиску наилучших вариантов раскроя кристалла под бриллианты. Результаты практических испытаний некоторых алгоритмов и программ показали их достаточно высокую эффективность.
В 1991 году один из вариантов разработанных программ в составе технического комплекса по разметке алмазов участвовал на ВДНХ СССР в павильоне "Народное образование" в разделе "От фундаментальных исследований до практического внедрения".Данная разработка была награждена серебряной медалью ВДНХ.
- iU "
Апробация работы.
Материалы диссертационной работы докладывались и обсуждались на II Всесоюзной научно технической конференции "Микропроцессорные системы автоматики " (Новосибирск 1990 г.)
Публикации. Основные теоретические результаты исследований опубликованы в 10 печатных работах .получено одно авторское свидетельство.
Структура и объем работы.
Диссертационная работа изложена на 165 страницах и состоит из введения,четырех глав,заключения,списка литературы и приложений.
В первой главе дается общая постановка задачи эффективного раскроя.Проводится обзор работ,посвященных этому вопросу.Анализируются ,методы решения задач эффективного раскроя.
Во второй главе проводится анализ задачи эффективного раскроя в детерминированном случае и в условиях неопределенности.Доказывается ряд утверждений,касающихся процесса эффективного раскроя.Рассматриваются некоторые аспекты решения данной оптимизационной задачи .
В третьей главе приводятся некоторые алгоритмы, разработанные для решения задач эффективного раскроя в детерминированном случае и в условиях неопределенности.Приводится наглядный пример, позволяющий сравнить результат решения задачи эффективного раскроя при традиционном подходе и с использованием предложенных в диссертационной работе алгоритмов. Описывается интегрированная среда для разметки кристаллов алмаза под бриллианты.
В четвертой главе дается общая характеристика технологического процесса производства бриллиантов,как сложного многостадий-
і А _
~ 11
ного объекта управления.На стадии разметки алмазов решается задача эффективного раскроя.Приводятся результаты экспериментов .подтверждающие работоспособность алгоритмов и программ оптимизации.
В заключении отражены результаты исследований проведенных в работе.Делаются выводы по использованию разработанных алгоритмов и методов.
Автор выражает признательность к.т.н.,доценту кафедры автоматики смоленского филиала МЭИ Прохоренкову П.А. за помощь оказанную в процессе работы над кандидатской диссертацией.
Общая постановка задачи эффективного раскроя сырья
Более века назад возник интерес к задачам эффективного раскроя tкоторые показывали как наилучшим образом разместить объекты произвольной формы в заданной области.
Одной из первых работ,посвященных эффективному размещению плоских объектов,является исследование русского математика П.л.Чебышева "О кройке одежды" [8],опубликованное в 1878 году.В этой работе рассматривается возможность наилучшего покрытия поверхностей плоскими выкройками из ткани.Начало систематическому исследованию проблемы эффективного раскроя было положено работой Л.В.Канторовича "Математические методы в организации и планировании производства" [9],в которой рассматривается размещение геометрических объектов без учета их формы.Предложенный Л.В.Канторовичем способ решения задач получил дальнейшее развитие в его работе ПОЗ.Є этих исследованиях были заложены основы методов линейного и динамического программирования (оимплекс-метода Дан-цинга и метода динамического программирования Беллмана) [113.
Параллельно с совершенствованием методов линейного размещения объектов развивались методы комбинаторной геометрии.Одними из первых работ в этом направлении являются фундаментальные исследования русского математика Б.С.Федорова [123.Затем появились работы немецкого математика Хеша [13,14].Ими были исследованы фигуры ,которыми можно заполнить плоскость без налеганий и просветов. Значительный интерес представляет работа венгерского математика Тота [153 , посвященная задачам отыскания оптимальных укладок и покрытий в евклидовом пространстве о числом измерений не более трех.
Методы комбинаторной геометрии ,хотя и позволяют получить различного рода оценки коэффициентов плотности заполнения и покрытий ,т.е.учесть форму геометрических объектов,но часто не дают возможности определить их координаты.
Началом теоретических исследований по размещению объектов с учетом их формы,по-видимому .следует считать работу Л.В.Канторовича и В.А.Залгаллера С103,где впервые предлагаются способы и алгоритмы рационального размещения однотипных геометрических объектов.В монографии Ю.Г.Стояна [163 рассматривается проблема размещения объектов произвольной формы: формализация задач размещения объектов ,а также методы и алгоритмы их решения.Возможность для разработки методов формализации и решения таких задач появилась благодаря введению В.Л.Рвачевым аппарата R-функций [17-203.Этот аппарат позволяет описывать такие объекты с помощью математических символов без каких-либо словесных оговорок,что важно при математической постановке и решении задач.
В настоящее время интерес к задачам аффективного размещения еще более возрос.Это вызвано необходимостью автоматизации решений задач проектирования ,в частности оптимального проектирования с той или иной точки зрения технологических процессов и конструкций [21,22].
Задачи проектирования возникают в самых разнообразных областях науки и техники .В качестве примера здесь можно привести такие отрасли промышленности как металлургия(изготовление деталей из проката стали),раскрой ткани в легкой промышленности, ювелирная и деревообрабатывающая промышленность.В этих примерах область оптимизации представляет собой либо часть плоскости,ограниченной некоторыми фигурами , либо это некоторый объем,ограниченный некоторыми поверхностями.Кроме внешних границ области оптимизации часто накладываются ограничения, исключающие часть внутренней области из допустимого пространства оптимизации.В качестве примера можно представить помещение склада готовой продукции, заполняемое по мере поступления деталей.Очевидно, внутри помещения могут быть пространства (колонны,перегородки и т.д.),которые не могут быть использованы, для размещения поступающей на склад продукции.
Решение задачи оптимизации размещения базируется на математической модели области оптимизации ,а также математической модели размещаемых в этой области объектов.Объект представляет собой точечное многообразие, образующее тело или фигуру iSO в пространстве.Следует также различать две существенно различные ситуации. Первая предполагает использование полностью определенной модели области и модели размещаемых объектов независимо от их формы.Например настил ткани при ее раскрое представляет собой прямоугольник размеры сторон которого определены. Геометрические размеры и конфигурация размещаемых объектов (деталей) как прави - 15 ло также полностью определены .В качестве другого примера можно привести плоскогранный кристалл алмаза описываемый уравнениями попарнопараллельных плоскостей и не имеющих внутренних дефектов. Вторая ситуация возникает при невозможности или сложности получения точного описания области оптимизации,а также при невозможности точного описания особых областей,находящихся внутри области размещения,и нежелательных (либо вообще запрещенных ) для расположения на них размещаемых объектов. В качестве примера можно воспользоваться уже упомянутой выше задачей размещения бриллиантов в заданном кристалле алмаза,которая может рассматриваться как задача с неполностью определенной моделью при искажении формы кристалла и наличии внутренних дефектов.
Методы и алгоритмы получения эффективного решения в задачах раскроя
Как показано в [51,в задачах размещения область допустимых решений в общем случае невыпукла,многосвязна и имеет сложную геометрическую структуру.Кроме того функция цели в общем случае нелинейна.В силу нелинейности функции цели и невыпуклости области ее определения задача размещения является многоэкстремальной. Экстремумы могут достигаться внутри области допустимых решений и на ее границе.Анализ перечисленных особенностей показывает,что оптимизационные задачи размещения относятся к классу сложных нелинейных многоэкстремальных задач математического программирования большой размерности с громоздкой системой ограничений.
Для решения задач эффективного размещения можно использовать различные подходы.
Рассмотрим подробнее некоторые специфические подходы предложенные в [26] для решения задачи эффективного размещения.Как отмечалось выше этим задачам характерно не только наличие большого количества локальных экстремумов,но и значительным разбросом значений функции цели в точках локальных экстремумов.Решение задач эффективного размещения распадается на два этапа:определение локальных экстремумов функции цели и организация их перебора. Практическая реализация этих двух этапов сводится к следующему: как метод локальной оптимизации используется описанный ниже метод последовательного-одиночного размещения,а перебор экстремумов проводится о использованием методов оптимизации функционалов , заданных в пространстве перестановок.
Вопрос точности вычисления локальных экстремумов решается следующим образом.Пока отроятся произвольные локальные экстремумы, нет необходимости добиваться большой точности.Это позволяет воспользоваться методами построения приближений к локальным экстремумам не самих локальных экстремумов.Проблема точного построения локальных экстремумов становится актуальной ,когда определены начальные точки для построения лучших локальных экстремумов. Рассмотрим подробнее метод последовательно-одиночного размещения приближений к локальным экстремумам,который предложен в [27].
Этот метод является некоторой разновидностью метода Гау-са-Зайделя.
Пусть функция цели представляет собой функцию 6п - переменных (1.8),-где n-количеотво размещаемых объектов. x=7,(Pi,P2,...,Pn) (1.12) где Pi - вектор параметров размещения объекта Si; Pi - вектор параметров размещения объекта 5 . Применительно к задачам эффективного размещения реализация метода последовательно-одиночного размещения можно представить в виде следующей итерационной процедуры: i(Pkl\Pk2 ,Pki ) = extr Xi-l(Pkl ,Pk2 ,Pki-l ,Pki), (1.13) 1-1.,.n , ki [l,nl , XQ - xo(Pkl) , где Xi-i - значение функции цели при i-1 размещаемом объекте; Pkt (t l,Z. -- i-l) - вектор параметров размещенных объектов; Pki - вектор параметров размещаемого объекта; W - область допустимых решений функции цели.
Суть способа состоит в следующем.Все объекты размещаются последовательно по одному.Ранее размещенные объекты считаются неподвижными ,т.е. их параметры размещения имеют вполне определенные фиксированные значения.Каждый объект размещается так,что из всех возможных положений выбирается такое,при котором значения функции цели x-i достигает оптимального значения только по тем переменным,которые являются параметрами размещаемого объекта.
Каждому из размещаемых в области SQ объектов поставим в соответствие числа из натурального ряда 1...п,где n-чиоло размещаемых объектов.При этом объекту Si соответствует 1,объекту S2 соответствует 2 и т.д.Тогда произвольная последовательность из этих чисел однозначно определяет последовательность размещаемых объектов Si.Рассмотрим некоторую последовательность чисел A=kl...kn , (1.14) где ki ki+l (i«l..n;ki Cl,n3).
Тогда первому члену этой последовательности kl соответствует объект Ski-Если предположить ,что задача размещения рассматривается применительно к одному объекту Ski,то функция цели будет зависеть от одного вектора параметров размещения Pki,т.е. к=к(Ркі5;Ркі Є. Ю.Расположим в области раемещения Su объект Ski таким образом ,чтобы вектор его параметров размещения Pki удовлетворял условию: i(Pki ) - extr xo(Pki) PkieW # Найденное значение вектора Pki однозначно определяет положение объекта Ski в области S0.Зафиксируем это положение.Тем самым фиксируем вектор Pki
Постановка задачи раскроя при условии полной информации об объектах
Пространственные формы -Т представляют собой множества, элементами которых являются классы эквивалентности на совокупности любых точечных множеств в соответствующих линейных метрических пространствах.В качестве примеров пространственных форм можно привести следующие классы эквивалентности: отре-зок.окружность,эллипс,сфера,симплекс,конус,цилиндр и т.д.
Для того чтобы различать множества,имеющие одну и ту же пространственную форму,необходимо знать их метрические характеристики. Метрические характеристики Ш разбивают на два вида вида: ttri},-Сіли}-соответственно метрические характеристики, задающие локальные свойства точечных множеств и свойства точечных множеств в целом.Так,в качестве компонент т1У могут выступать, например радиус кривизны части границы множества,порядок соприкосновения границ множеств,a imz -площадь поверхности,центр тя жести,диаметр множества и т.д.
Объект S определенной формы с заданными метрическими характеристиками может занимать любое положение в некотором пространстве R (R-евклидово пространство).Это положение определяется параметрами -СР объекта . В качестве параметров компоненты -СР выбирают параметры, характеризующие положение собственной системы координат объекта S относительно нуля пространства R.Начало собственной системы координат называется полюсом объекта S. Компоненты -СР называют параметрами размещения объекта S С67,б8].
Определение 2.2.
Множество точек S0 с Я1", на котором решается задача раскроя будем называть областью раскроя.
Как показано в С25] ,в задачах раскроя область допустимых решений в общем случае невыпукла,многосвязна и имеет сложную геометрическую структуру.Кроме того функция цели 3c(w) в общем случае кусочно гладкая,причем нелинейна на каждом гладком куске, Пространство параметров ,в котором определена функция цели, зависит от числа размещаемых объектов и от размерности пространства в котором производится размещение ї .В силу нелинейности функции цеди и невыпуклости области ее определения основная задача раскроя является многоэкстремальной.Экстремумы могут достигаться внутри области допустимых решений и на ее границе,число локальных экстремумов может быть большим и иногда оценивается величиной порядка пі и более L64,67,68].Анализ перечисленных особенностей показывает,что оптимизационные задачи раскроя относятся к классу сложных нелинейных многоэкстремальных задач математического программирования большой размерности с гро моздкой системой ограничений.
Рассмотрим более детально оптимизационную задачу раскроя заданной выпуклой области S0. Причем внутри раскраиваемой области So могут быть выпуклые особые области Sk»B которых нежелательно (либо запрещено) размещать объекты $ц.
Определение 2.3.
Особой к-ой областью внутри области раскроя 50 будем называть подмножество Skc So,пересечение которого с множеством размещаемых объектов Si приводит к изменению значения целевой функции.
Примером особых областей могут служить внутренние дефекты кристалла алмаза. В качестве функции цели в задачах раскроя обычно используют максимизацию коэффициента заполнения \L области 30 объектами Si,Sj: MAX { ц, = , (2.2) VS0 где Vs0- объем заполняемой области SD; VSJ- объем занимаемый объектами размещения Si и Sj.
Выберем качестве функции цели не максимизацию коэффициента заполнения м- (2.2) области S0ja максимизацию стоимости (Cost) объектов Si размещаемых в области SD. Такого класса задачи размещения достаточно широко встречаются на практике.Так при изготовлении бриллиантов из алмазного сырья сначала теоретически пытаются разместить бриллианты различной формы (круглый,маркиз.багет и т.д.),представляющие собой выпуклые объекты в заданный ал маз.Алмаз может иметь дефекты , которые могут быть учтены как дополнительные объекты размещения Sit и представлять собой выпуклую область. Около двадцати пяти процентов всего ювелирного алмазного сырья можно аппроксимировать выпуклой областью.При кажущейся незначительности этого количества,необходимо помнить об исключительно высокой стоимости алмазов и бриллиантов.И решения оптимизационной задачи максимизации стоимости размещаемых бриллиантов даже для этого класса алмазного сырья дает большую прибыль при изготовлении бриллиантов.
Алгоритм эффективного раскроя сырья в условиях непределенности
Сравнив эти результаты выбирается наилучший,который и является гарантированным результатом Cost r-При этом фиксируются углы наклона следа на гранях кристалла плоскости разметки к видимому ребру ,а также расстояние от следа до реперной точки на ребре (эта информация для правильного нанесения на гранях плоскости распила).
Заметим,что для большой группы алмазов разметчик, как правило, производит вписывание двух или трех бриллиантов,имеющих максимальную стоимость.Это обусловлено тем,что оставшийся объем экономически выгоднее пустить на алмазный инструмент,чем на ювелирную продукцию.В общем случае, согласно алгоритму,в алмаз можно вписывать произвольное количество бриллиантов.
На этом второй этап оптимизации заканчивается.
Третий этап.
На этом этапе ищется множество неулучшаемых решений Q (2.27)(гл.2.,п.2.4.).Критерием оптимизации остается стоимость получаемых бриллиантов.Область допустимых решений расширяется за счет неопределенности границ раскраиваемой области (кристалла) и размера особой области (дефекта) .Процесс оптимизации хотя и ана - 96 логичен второму этапу,но имеет некоторые особенности С59,60].
Неопределенность значения стоимости заставляет использовать бинарные отношения - отношение неразличимости и отношение доминирования (см.гл.,п.2.3,п.2.4.)
Для каждой из ориентации кристалла на этом этапе оптимизацию начинают не из произвольной точки ,а из найденных во втором этапе решений соответствующих Costal,COStflni,COStflci,COStflUi.
Практически подученное множество неулучшаемых решений представляет собой интервалы ,в которых должны находиться углы наклона следа на гранях кристалла плоскости разметки к видимому ребру и расстояние от следа дс реперной точки на видимом ребре.
Четвертый этап.
На найденном множестве неулучшаемых решений решается еще одна оптимизационная задача.В качестве критерия оптимизации выбирается минимизация " степени чувствительности решения" (см.гл2.,п.2.4.).
Варьируя параметрами оптимизации,не выходя за пределы допустимых диапазонов ,в которых должны находиться углы наклона следа на гранях кристалла плоскости разметки к видимому ребру и расстояние от следа до реперной точки на видимом ребре ищется минимальное значение степени чувствительности решения SDmin Пятый этап.
Имея такую информацию как множество неулучшаемых решений Q , миннималъная "степень чувствительности решения" 5ВщІП, стоимость гарантированного результата Coster (пессимистический подход) пользователь сам решает каким выбрать окончательное эффективное решение из множества неулучшаемых решений.При этом пользователь учитывает еще и факторы,которые не удалось формализовать,напри мер технологичность решения. Если ни один из результатов не приемлем для ЛПР,то он возвращается к первому этапу изменяя исходные данные. Как видно из параграфа 3.1. общий алгоритм эффективного раскроя является сложным и многоступенчатым.Он сам включает в себя множество решений локальных задач. Например,при вписывании рундиста бриллианта в сечение кристалла приходится решать задачу вписывания окружности максимального диаметра в выпуклый многоугольник. Остановимся на алгоритме вписывания окружности максимального диаметра в выпуклый многоугольник,использующий метод Заутендаика.
Пусть область размещения описывается линейной математической моделью вида (.5).При этом в сечении плоскостью,области раскроя получится выпуклый многоугольник рис.3.6,число сторон которого зависит от сложности математической модели области раскроя и месторасположения плоскости сечения.
Пусть объект размещения описывается сочетанием поверхностей второго порядка (Е.б).При этом в сечении плоскостью,размещаемого объекта получится линия второго порядка - окружность или эллипс.
На данном этапе оптимизационная задача предотавляет собой нахождение параметров размещения максимально возможной по размеру окружности ИА2-[г,х,у},где г-радиус,х,у-координаты центра (эллипса :RAZ-{а,Ь,х,у , где а,Ь- полуоси, х,у-координаты центра)
Похожие диссертации на Разработка алгоритма управления эффективным раскроем сырья
