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

РГ6 од - 5 ЙЮН 1995

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ (технический университет)

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

СКУНЕВ БОРИС ВАСИЛЬЕВИЧ

РАЗРАБОТКА АЛГОРИТМА УПРАВЛЕНИЯ ЭМЕКТИВЮМ РАСКРОЕМ СЫРЬЯ

Специальность: 05.13.01 - управление в технических

сис* мах

АВТОРЕФЕРАТ

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

МОСКВА

1995

Работа выполнена на кафедре управления и информатики Московского энергетического института (технического университета) .

Научный руководитель - кандидат технических наук,доцент БОЧКОВ Александр Федорович

Официальные оппоненты: доктор технических наук,профессор

Попов Вадим Иванович,

кандидат технических наук,доцент Саков ;Йгорь Алексеевич

Ведущая организация - Научно-производственное объединение технологического приборостроения г. Смоленск ( НПО "Техноприбор".;

Зашита диссертации состоится " 22 " июня 1995 г. в аудитории 3-4.0'' а 15 час;. СО мин. на заседании диссертационного Совета К 053.16.18 Московского энергетического института (технического университета).

Отзывы (з двух экземплярах, заверенные печатью) просим направлять по адресу: 111250, Москва, ул. Красноказарменная, д. 14, Ученый Совет Московского энергетического института (технического университета,.

С диссертацией молнс ознакомиться в библиотеке МЭИ.

Автореферат раэсслак " 22" мая 1995 г.

Ученый секретарь диссертационного Совета к.т.н..доцент

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

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

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

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

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

Для достижения указанной цели в работе были поставлены и решены следующее основные задачи.

1. Разработка алгоритмов управления эффективным раскроем сырья в детерминированном случае (математическая формулировка и исследование детерминированной задачи эффективного раскроя).

2. Исследование задачи эффективного раскроя сырья в условиях неопределенности (выявление источников возникновения факторов неопределенности,математическая формулировка задачи эффективного раскроя в условиях неопределенности).

3.Разработка методов и алгоритмов решения задачи эффективного раскроя в условиях неопределенности.

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

- -

исследований подтверждена данными эксперимента.

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

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

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

3.Предложен новый подход к решению задачи аффективного раскроя в условиях неопределенности, использугадй понятие "степень чувствительности решения" и гарантированный результат.

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

Реализация результатов.Результаты исследований использованы в технологическом процессе обработки кристаллов алмаза на ПО Кристалл г.Смоленск.

Диссертационная работа выполнена по тематике научно-исследовательской работы проводимой кафедрой Автоматики смоленского филиала МЭИ с СКТБ "Кристалл" .посвященной обработке кристаллов алмаза и поиску наилучших вариантов раскроя кристалла под бриллианты. Результаты практически^: кспытан;п; некоторых алгоритмов и программ показали их достаточно высокую эффективность.

В 1331 году один из вариантов разработанных программ в составе технического комплекса по разметке алмазов участвовал на ВДНХ СССР в павильоне "Народное образование" в разделе "От фундаментальных исследований до практического внедрения".Данная разработка была награждена серебряной медалью ВДНХ.

Апробация работы.Материалы диссертационной работы докладывались и обсуждались на II Всесоюзной научно технической конферен-' ции "Микропроцессорные системы автоматики" (Новосибирск 1990 г.)

Публикации .Основные результаты исследований опубликованы в 10 печатных работах .получено одно авторское свидетельство.

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

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

Во введении обоснована актуальность темы диссертационной работы, сформулирована ее цель, дала оСе^я характеристика работы.

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

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

В зависимости от конкретной практической ситуации возможны различные варианты постановки данной задачи.Традиционно в качестве целевой функции применяется максимизация коэффициента заполнения области ,

Поиск ыетслов решения задач эффект »'.б;! ого раскроя позвслил выделить два основных подхода:

- чисто геометрический (основанный на комбинаторной геометрии);

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

Кроме Есего сказанного,заметим,что в большинстве реальных задач эффективного раскрся мы сталкиваемся с неопределенностью, обусловленной отсутствием полностью адекватных объекту математических моделей,либо просто адекватного набора данных,характеризующих объект управления.Выявлены ^акторы обуславливающие возникновение неопределенности. Отбрасывание тих ¿акторов б задачах эффективногс раскроя молет привести к совершенно неприемлемы}« результатам.

СущестЕужщзе методы решения либо госГпе не учитывают факторы неопределенности,либо недостаточно эффективны.

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

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

Множество точек .образующих размещаемую фигуру называется размещаемым объектом.

Структура задач эффективного раскроя такова,что формулировка их аналитически должна включать:

а) формальное представление функции цели в виде математических символов;

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

в) условия размещения объектов в заданной области.

Пусть {5!>п - ограниченные замкнутые объекты и 30 - замкнутая область (область вписывания),в которой их необходимо разместить. Условия б) ив) можно представить в виде

• Рю^.г,) > С , 1,3>1;2....п , , (1)

*

ргЛ^Эо.З,) > С , 1-1,2----П , Г-1, (2)

где ри -расстояние между объектами 3, и 53;

К^ЧЗо-область,представляющая все пространство за вычетом области

вписывания 30;

рГ1 .расстояние от области К^' .Зо до объекта

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

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

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

х(и") = ехЦ х(и) . (3)

«с и

где V задается согласно выражениям (1) к (2).

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

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

(бездефектности ).3а счет выведения дефекта за продели размещаемого бриллианта путем уменьшения размеров последнего,можно повысить его стоимость до такого уровня ,что она Судет выше,чем у большего бриллианта,но имеющего внутри сеОя дефекты.

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

Формализуем данную задачу рзскроя с учетом ее особенностей. Функция цели здесь - стоимость размещаемых в заданной области объектов Cost (70!: ,МС„ .PCjj .ВС,.;) .которая зависит от пространственных форм размещаемых объектов ТС,,, метрических характеристик размещаемых объектов МС1Э, параметров размещения вписываемых объектов PC13(Uij,e,3) и цен на объект ВСОсобенностью задачи является тот факт,что на начальном этапе мы не располагаем информацией о метрических характеристиках MCj и количестве размещаемых объектов.Известными являются их пространственные формы ГС!.Так,например,при разметке алмазов мы заранее не знаем геометрические размеры и количество бриллиантов,которые можно вписать в кристалл алмаза,получив максимальную стоимость,-—Тогда согласно"(3):

Cost(к*) = MAX iCost(w)/ , (4)

«С*

при этом область допустимых решений V задается

Фц(МСг.РСг.М?з,?С,) > D i, = 1... n; i*i }

VnWr.PCr.MCi,PC,} > D i=l...n;r=l

(f^CMCx.PC^MCk.PCk) > О l-i... n; k-1.. 1

BC,>0 i-l..n

(5)

где МСцМСк- метрические характеристики размещаемых объектов 3, и особых областей Зк»

МСГ- метрические характеристики области представляющей дополнение к облагти раскроя 20 дс всего гростракстза Е^хЗо; РСг.РС,,РСк- соответственно вектора параметров размещения (^ХЗо, , ¿к» ~ *

ВС4о- стоимость 1-го объекта; п - количество размещаемых оСъектсв; 1 - количество особых областей.

Первое неравенство в (5) задает условие взаимного нёпересе-

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

Cost (стоимость)

2

интервал неопределенности

(диаметр)

Рис.2.Целевая функция с учетом неопределенности.

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

СсзЦСГ) = МАХ <С05^- . (6)

а* с а

где 0*-множество неулучшаемых решений; 0 -множество допустимых решений.

В связи с тем.что ? дзкком случае невозможно точно определить ы&зторасполслека? осс£ыу областей 5;-.. например. дефектов в алмазе., а также точно списать область раскроя Б0, область допустимых решений Ц задается :

Ф,,(МС,,РСХ,МС,,РС,) > 0 1,3=1...П;

Фп (.МС^. гиг .МС; ) ^ 0 1=1... Г»; Г=:

МСГ" < МСГ < МСГ+

ф1к(МС1,РС1,МСк,РСк) > О 1=1...п; к»1..1 (7)

МСк" < МСк < МСу+ РСк" С РСк < РСкт !

Г>Г. Г^ , п I

Ьь: ^ и х=1. .(I |

ВС! .ВС 1 * БС1 I

I

То есть метрические характеристики МСГ области раскроя могут принимать любые значения из соответствующих интервалов СМСг~,МСг+] и им не приписывается никакой вероятностной меры. В

овов очередь, метрические характеристики МСя в параметры размещения PCic особых областей Sk могут принимать любое аначеняе из соответствующих интервалов tMCk~,MCk+j.ГРСк".РСк+3 и им тоже не задаст ни какой вероятностной меры.И наконец, цены на продукцию могут принимать любое значение из интервала CBCi",BCi+3 и им тоже не задают ни какой вероятностной меры.

Заданные интервалы определяют допустимые диапазоны вариации соответствующих параметров.

На формальном уровне в данном случае можно выделить лишь множество неулучшаемых решений (рис.3).которое определяется выражением:

Q"-< Q с Q I Cost*(q) > max Cost~(q)> , (8)

Q с Q

где Q - множество допустимых решений; Q* - множество неулучшаемых решений;

Cost~(q),Cost+(q) - соответственно нижняя и верхняя границы значений стоимости.

Рис!3.Множество неулучшаемых решений.

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

Для оценки роли неопределенности при принятии окончательного решения ЛПР .введено понятие "степень чувствительности решения" ББ.Определим ее как отношение разности стоимостей текущего варианта и гарантированного случая к стоимости гарантированного варианта раскроя.Тогда

НАЧАЛО

1 ЛПР

Тринятие решения о характере аадата эффективного раскроя заданной оСласти.

I

Т

Детерминированная оптимизационная задача раскроя.

4

ЛПР

JL

Задание моделей области ■ | раскроя, размещаемых _ I оОъектоЕ.осоСых областей. '

6 ЭВМ Эффективный раскрой области.Критерии оптимизации - максимальная суммарная стоимость размещаемых объектов.

8 ЛПР _ Принятие заключения о возможности реализация полученного ЭВМ решения.

3 Оптимизационная задача раскроя в условиях неопределенности.

5 JUIF Задание моделей области раскроя, размещаемых объектов.особых областей. (Использование интервальных моделей.)

1

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

Решение не 1

1U удовлетво-!

ряет J

Предлагаемое ЭВМ решение I приемлемо. !

ЗЕК

I

12

¡ЛПР

Дополнительная информация для ЛПР.( Оптимизация с ориентацией на гарантированный результат.пессимистический подход,самые жесткие ограничения.Расчет степени чувтвительности)

-Г

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

I

! 131

Эффективное решение принято.

Выдача управления на ислолк.устройство]

14

I

Эффективное решение не принято. Корректировка границ и параметров моделей.

Рис.5. Блок-схема агоритма управления эффективным раскроем.

Максимизация отоимооти второго размещаемого объекта в оставшуюся часть области раскроя.

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

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

- минимизация степени чувствительности решения.

Пятый этап.Выбор ЛПР единственного приемлемого для него решения из множества неулучшаемых решений.

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

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

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

После завершения оптимизации,по желанию исследователя,на принтере создается твердая копия полученного эффективного решения рис.6.На распечатке показаны :

- изометрическое изображение кристалла и его четыре проекции;

- вид плоскости разметки на изометрическом изображении алмаза;

- след оставляемый на гранях кристалла от плоскости разметки на проекциях алмаза;

- проекции вписанных бриллиантов (некоторые их характерные контуры).

Кроме этого выведена числовая информация:

- 1.1,1.2,1.3,1.4,Н1,Н2 - Ш-параметры кристалла (в случае наличия неопределенности они представляют собой параметры пессимистической модели) выраженные в миллиметрах ;

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

КРИСТАЛЛ: 1.1=4.12 О

1а=3.93 о

1-3-2.87 О ^ . 18 О 111=7.4? О Н2=7.63 О МасслгО.77 С т оим . - 5

й

. оо

■ ОО . оо

■ ОО

,оо

• ОО

бриллианты:

к»»«- . <КР—57 >

НИР.-3.вэ

Длин. =2 .89

а =36 О Ь=42 О О

Ь = 2

Масса -О .09 Цви= 1 Дечл»ек т . -2

Ст= 73.6

Клà . <КР-37> Мир.=4.09 Длин.=4.09

а=36 О Ь=42 О О

Ь = 2

Насса^О.25 Цвет: 1 ДеякРект.=2 Ст= 405.0

Степень чувств. О,О X

РЙЗМЕТКЙ:

Я1=15.91 02 -О . ОО «3=15.91 «4 =0 . ОО N1=0.80 N2=0.91 N3=0.64 N4=0.52

ХЙРЯКТЕР.КРИСТАЛЛА ПО <С1Т¥> »11-ЭСП 2 Ю 1С

Номер партии:12345

Рис.6.Иллюстрация эффективного раскроя алмааа.

- укамш ыаооа (я каратах) и стоимость крютша (в долларах);

- а раздел» "БПШИАНТЫ" указаны тип впвоажвых бриллиантов, их геометрические размеры (длина, ширина, углы наклона граней) .масса (в каратах),цвет,дефектность и стоимость (в долларах);

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

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

- в разделе "РАЗМЕТКА" показаны углы наклона следа на гранях краотадла плоскости разметки к видимому ^еОру (А1-А4),а также расстояние от следа до реперной точки на ребре (N1-N4) (зта информация для правильного нанесения на гранях линий разметки);

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

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

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

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

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

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

- 18 -

• . _. Таблица 1.

РАСКРОЙ АЛМАЗНОГО СЫРЬЯ НА ПАРТИИ МОДЕЛЕЙ N300

N АЛМАЗ стоим Прогноз ЭВМ М: масса,С:стоим. Прогноз разметчика М-. масса, С: стоимость 1 Факт М:масса,С:стоим

Большой брилл. Малый брилл. Большой брилл. Малый брилл. Большой брилл. Малый Оридд.

1 7533 М-. 1.36 С: 12240 М: 0.47 С: 17Э5 М: 1.26 С: 11340 М: С.57 С: 2522 М: 1.36 0:12240 М: 0.46 С: 17Б7

Сумм.масса 1.83 Сумм.стоим. 14035 Сумм.масса 1.83 Сумм.стоим. 13962 Сумм.масса 1.82 Сумм.ст. 13997

2 7493 М: 1.16 С: 10440 М: 0.57 С: 2622 М: 1.07 С: 9630 М: 0.63 С: 2898 М: 1.15 С:10350 М: 0.56 С: 2576

Сумм.масса 1.73 Сумм.стоим. 13062 Сумм.масса 1.70 Сумм.стоим. 12528 Сумм.масса 1.71 Сумм.ст. 12926

3 9087 М: 1.43 С: 12870 М: 0.39 С: 1306 М: 1.38 С: 12420 М: 0.44 С: 1581 М: 1.43 С:12870 М: 0.38 С: 1273

Сумм.масса 1.82 Сумм.СТОИМ. 14176 Сумм.масса 1.82 Сумм.стоим. 14101 Сумм.масса 1.81 Сумм.ст. 14143

4 1 ЛГГГ} С М: 1.34 С: 12060 М: 0.29 С: 469 М: 0.98 С: 5568 М: 0.69 С: 3174 М: 1.33 С:11970 М: 0.28 С: 454

Сумм, масса 1.63 Сумм.стоим. 12529 Сумм.масса 1.67 Сумм.стоим. 8742 Сумм.масса 1.61 Сумм.СТ. 12424

5 745? М: 1.42 С: 12780 М: 0.39 С: 1306 М: 1.35 С: 12150 М: 0.48 С: 1834 М: 1.41 С:12690 М: 0.39 С: 1306

Суш. масса 1.81 Сумм.стоим. 14086 Сумм.масса 1.83 Сумм.стоим. 13984 Сумм, масса 1.80 Суш. СТ. 13995

веденных в работе.Делаются выводы по использованию разработанных

алгоритмов и методов.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Основным результатом работы является разработка алгоритмов и программ для решенил задач эффективного раскроя. В частности:

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

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

изделий . Доказан ряд теоретических утверждений ,имеющих гажно®

практическое значение при построении алгоритмов оптимизации.

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

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

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

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

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

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

Основные положения диссертационной работы опубликованы в следующих работах........

1.'0кунев Б.В. .Прохоренков П.А..Храименков М.И. Применение персональных ЭВМ для задач автоматизации измерений контроля и испытаний // II Всесоюзная конференция "Микропроцессорные системы автоматики": Тез.докл. - г.Новосибирск,-19ЭС.-С.31-33.

2.Скунев Б.В.,Прохоренков П.А..Храименков М.И. Оптимизация раскроя кристалла алмаза по интервальной математической модели // IV Всесоюзная конференция "Перспективы и опыт внедрения статистических методов в АСУ ТП": Тез.докл. - г.Тула,-1990.-С.67,68.

З.Окунев Б.В..Прохоренков П.А. Автоматизированная система для объемного раскроя кристаллов // II Всесоюзная конференция "Измерение и контроль при автоматизации производственных процес-

сов"; Tea.докл. -г.Барнаул,-1891.-С.72-74.

4.0кунев Б.В..Прохоренков П.А..Поляков В.А. Определение качества бриллиантов по их математической модели // Труды института / Смол.фил.МЭИ. - 1992.- N1.- С.55-63.

5.Окунев Б.В..Прохоренков П.А..Титов Д.Д. Восстановление геометрической формы кристалла по телевизионному изображению // Труды института Смол.фил.МЭИ. - 1992.- N1.- С.63-70.

б.Окунев Е.В.,Прохоренков П.А.,Ковадков А.Н.Диалоговая система для раскроя кристаллов алмаза // Труды института / Смол.фил. МЭИ. - 133S.- N2.- С.169-179.

7.0кунев Е.В..Прохоренков П.А..Баринсв С.М. Оптимизация размещения лекал на ткани // Труды института / Смол.фил.МЭИ. - 1993. - N5.- С.47-50.

8.Окунев Е.В..Прохоренков П.А..Ковааков А.Н..Прохоренкова

A.Т. Анализ задач оптимизации размещения деталей в заданной области // Труды института / Смол.фил.МЭИ. - 1393.- N5.- С.35-37.

9.Окунев Б.В..Прохоренков П. А..Фомченков В.П. Разработка математических методов оптимального раскроя кристаллов алмаза // Труды института / Смол.фил.МЭИ. - 1994.- С.14-19.

10.Окунев Б. В.,Прохоренков П.А.,©омченков' В. П. Алгоритм управления оптимальным раскроем сырья в условиях неопределенности ft Труды института / Смол.фид.МЭИ. - 1994.- С.101-109.

11.А.с.N11710330,МКИ3 В 25 Н 7/00 Автоматическое устройство для разметки драгоценных камней /П.А.Прохоренков,М.И.Храименков,

B.Г.Куликов //Открытия.Изобретения.3S92.N5

Ппипнгшт г.- печати

Типографии МЭИ, Красноказарменная, 13.

ВВЕДЕНИЕ

1. АНАЛИЗ ЗАДАЧ ЭФФЕКТИВНОГО РАСКРОЯ СЫРЬЯ И ОБЗОР МЕТОДОВ ИХ РЕШЕНИЯ

1.1. Общая постановка задачи эффективного раскроя сырья.

1.2. Методы и алгоритмы получения эффективного решения в задачах раскроя

1.3. Учет неопределенности при решении задач эффективного раскроя.

1.4. Выводы по главе

2.ЭФФЕКТИВНЫЙ РАСКРОЙ ОБЛАСТИ.

2.1. Постановка задачи раскроя при условии полной информации об объектах

2.2. Эффективный раскрой области в случае детерминированной оптимизационной задачи.

2.3. Постановка задачи раскроя в условиях неопределенности. 66-.

2.4. Эффективный раскрой области в условиях интер-вально заданной неопределенности.

2.5. Выводы по главе

3. ОПИСАНИЕ АЛГОРИТМОВ НАХОЖДЕНИЯ ЭФФЕКТИВНОГО РЕШЕНИЯ

В ЗАДАЧАХ РАСКРОЯ

3.1. Общий алгоритм эффективного раскроя произвольной области.

3.2.Алгоритм эффективного раскроя сырья в условиях непределенности.

3.3. Алгоритм вписывания окружности наибольшего радиуса в выпуклый многоугольник.

3.4. Общее описание интерактивного режима ЛПР-ЭВМ для решения задачи эффективного раскроя алмаза.

3.5.Выводы по главе

4. ОПТИМИЗАЦИЯ ОТДЕЛЬНЫХ СТАДИЙ ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА ИЗГОТОВЛЕНИЯ БРИЛЛИАНТОВ

4.1. Общая характеристика процесса изготовления бриллиантов

4.2. Оптимизация процесса разметки кристаллов алмаза под бриллианты.

4.3. Выводы по главе

Актуальность проблемы.

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

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

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

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

Tr 0 в у uy

Устройство управленця u

Объект y I

СП I

ВУ - вычислительное устройство; ИУ

ЛПР - лицо принимающее решение. Р

Q - критерий оптимизации; о

Vo - задание на оптимальное управление; Y исполнитель ное устройство; вектор исходных данных; управляющее воздействие; вектор фазовых координат системы.

Рис.В.1.Система управления эффективным раскроем сырья тата по эффективному использованию сырья.

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

Оптимизационный подход к постановке и решению задач синтеза сложных технических систем является резервом повышения качества управления С1-4].

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

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

Причем,чисто из геометрических соображений решить общую задачу эффективного раскроя невозможно,так как изготовителю продукции важно не просто выпустить побольше любых изделий,а необходимо получить максимально возможную прибыль при переработке промышленного сырья.Так при обработке кристаллов алмаза можно изготовить бриллианты различной формы и величины.В этом случае необходимо так раскроить кристалл,чтобы стоимость полученных из него бриллиантов получилась максимальной.Далеко не всегда более rf I крупные бриллианты о дефектами дороже более мелких, но безде фектных.Бриллианты же разной формы ,например маркиз, багет,изумруд, имеющие одинаковую массу заметно различаются по стоимости. В легкой промышленности из одного и того же отреза ткани можно выкроить меньшее количество особомодных и дорогих изделий и получить большую прибыль,чем если бы делать большее количество устаревших и не пользующихся спросом моделей одежды.Естественно, что производитель будет изготавливать более модные изделия, если даже отходы сырья будут значительнее,чем при изготовлении устаревших моделей.Кроме всего вышесказанного,имеющиеся факторы неопределенности,такие например как цены на продукцию или невозможность точно измерить координаты расположения дефектов в кристалле,не позволяют использовать чисто геометрические преобразования для эффективного раскроя сырья.

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

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

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

Цель работы.

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

Для достижения указанной цели в работе были поставлены и решены следующие основные задачи.

1.Разработка алгоритмов управления эффективным раскроем сырья в детерминированном случае (математическая формулировка и исследование детерминированной задачи эффективного раскроя).

2. Исследование задачи эффективного раскроя сырья в условиях неопределенности (выявление источников возникновения факторов неопределенностиматематическая формулировка задачи эффективного раскроя в условиях неопределенности).

3.Разработка методов и алгоритмов решения задачи эффективного раскроя в условиях неопределенности. .

Методы исследования.

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

Научная жжиана.

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

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

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

Практическая ценность .

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

Реализация результатов.

Результаты исследований использованы в технологическом процессе обработки кристаллов алмаза на ПО Кристалл г.Смоленск ,а также на ряде других предприятий аналогичного типа.

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

В 1991 году один из вариантов разработанных программ в составе технического комплекса по разметке алмазов участвовал на ВДНХ СССР в павильоне "Народное образование" в разделе "От фундаментальных исследований до практического внедрения".Данная разработка была награждена серебряной медалью ВДНХ.

Апробация работы.

Материалы диссертационной работы докладывались и обсуждались на II Всесоюзной научно технической конференции "Микропроцессорные системы автоматики " (Новосибирск 1990 г.)

Публикации. Основные теоретические результаты исследований опубликованы в 10 печатных работах ,получено одно авторское свидетельство.

Структура и объем работы.

Диссертационная работа изложена на 165 страницах и состоит из введения,четырех глав,заключения,списка литературы и приложений.

4.3.Выводы по главе.

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

2.Разработанные в диссертационной работе алгоритмы и программы позволяют повысить' эффективность обработки кристаллов.

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

ЗАКЛЮЧЕНИЕ.

Основным результатом работы является разработка алгоритмов и программ для решения задач эффективного раскроя.

В частности:

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

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

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

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

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

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

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

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

1.Реклейтис Г.,Рейвиндран А.,Рэгсдел К.Оптимизация в технике.В 2-х кн.-М.:Мир,1986 г.

2. Advances in Optimimization and Control/Ed.H.A.Eiselt and G. Pederoli.Berlin:Springer,1988.

3. Goicoechea A.,Hansen D.R.,Duckstein L.Multiobjective Decision Analysis with Engineering- and Business Application.N.Y.: Wiley,1992.

4. Greig D.M.Optimization.London:Longman,1980.

5. Солодовников В.В.,Бирюков В.Ф.,Тумаркин В.И.Принцип сложности в теории управления.-М.Наука,1977.с.341.

6. Чебышев П.Л.О кройке одежды.-УМНД946.1,2

7. Канторович Л.В. Математические методы в организации и планировании производства.-Изд-во Ленингр.ун-та 1939 .

8. Ю.Канторович Л.В.,3алгаллер В.А. Рациональный раскрой промышленных материалов.-Новосибирск,Наука, 1971.

9. Беллман Р.Динамическое прграммирование.-Ил,М.1960.

10. Федоров Б.С.Симметрия кристаллов.Т1,2.-Изд-во АНСССР,1949

11. Heesch H.Der topologisch gleichwertige Kristallbindungen.--Zeitschrift fur Kristallographie 1933,84.

12. Heesch H., Kienzle 0. Flachenschlub System der Fomen Zuckenlos aneinanderschlibenden Flaohenteil. Springer-Verlag, Berlin-Gottingen-Heidelberg,1963.

13. Тот Ф.Л. Расположения на плоскости,на сфере и в пространстве .-М.Физматгиз.1958.

14. Стоян Ю.Г.Размещение геометрических объектов.-Киев, "Наук. думка" 1975.

15. Рвачев В.Л. Об аналитическом описании некоторых геометрических объектов.- ДАН СССР 1963,153,4.

16. Рвачев В.Л.Теория R-функций и некоторые ее применения .-Киев.:Наук.думка.1982.

17. Рвачев В.Л.,Стоян Ю.Г.Алгоритмы построения неравенств,которым удовлетворяют параметры размещения непересекающихся тел.-Кибернетика,1966,5,82-92.

18. Рвачев В.Л.Элементы дискретного анализа и теории R-функ-ций.-Изд.Харьковского политех.инст.1972 г.

19. Скатерной В.А. Оптимизация раскроя материалов в легкой промышленности. -Москва. Легкопромиздат. 1989.

20. Скатерной В.А.,Попова Л.С.,Фесенко А.Г,Свистунова Л.Т. -Изв.вузов.Технология легкой промышленности.1987.N3.с.114-120.

21. Окунев Б.В.,Прохоренков П.А.,Ковалков А.Н.,Прохоренкова А.Т. Анализ задач оптимизации размещения деталей в заданной области // Труды института / Смол.фил.МЭИ. 1993.- N5.- С.186-191.

22. Стоян Ю.Г.,Гииль Н.И. Методы и алгоритмы размещения плоских геометрических объектов.Киев.Наук.думка,1976

23. Стоян Ю.Г.,Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования.-Киев.Наук.думка, 1986.

24. Стоян Ю.Г.,Соколовский В.3.Решение некоторых многоэкстремальных задач методом сужающихся окрестностей.-Киев."Наукова думка" 1980.

25. Стоян Ю.Г.,Черепахин В.М.Об одном способе рационального размещения кругов в полосе. В кн.Тезисы докладов и сообщений на Всесоюзн.межвузовской симпозиуме по прикл.математике и кибернетике. -Горький. 1967. с. 176.

26. Стронгин Р.Г.Численные методы в многоэкстремальных задачах .-Москва."Наука".1978.

27. Стоян Ю.Г.,Гиль Н.И.Метод асимптотического перебора локальных экстремумов.-Изд.инст.проблем машиностроения. АН СССР (1974).

28. Соболь И.М.Численные методы Монте-Карло,-М. "Наука", 1973.

29. Гурин Л.С.,Лобач В.П.Комбинация метода Монте-Карло с методом наискорейшего спуска при решении некоторых экстремальных задач.-Вычислит.математика и матем.физика,2,3(1962),с.499-502.

30. Моцкус Й.Б.Многоэкстремальные задачи в проектировании.-М. "Наука",1967.

31. Ермолаев Ю.М.Методы стохастического программирования. -М. :Наука.1976.

32. Уайльд Дж.Методы поиска экстремума.-М.:Мир.1966.

33. McMurtry G.J.,Fu K.S.A variable structure automation used as a multimodal searching teechniqe,IEEE Trans., AS-11,3 (1966), p.379-387

34. Хилл Д.С.,Гибсон Д.И.Способ автоматической оптимизации многоэкстремальных функций.Сб."Теория самонастраивающихся систем управления",-М."Наука",1969.

35. Половинкин А.И.Оптимальное проектирование с автоматическим поиском схем инженерных конструкций.-Изд.АН СССР,Техническая кибернетика,5(1971),29-38.

36. Зв.Растригин Л.А.,Рипа К.К.Автоматная теория случайного поиска. "Зинатне",Рига,1973.

37. Моисеев Н.Н.Элементы теории оптимальных систем.-М."Наука", 1975.

38. Сотиров Г.Р.Оптимизация при неопределеност//0птимизация на произволствени системи/Под ред.на И.Попчев.-София:Техника, 1986.

39. Тимохин С.Т.Шапкин А.В.О задачах линейного программирования в условиях неточны данных.-Экономика и матем.методы 1981.Т17.N5

40. Шокин Ю.И.Интервальный анализ.-Новосибирск:Наука.1981.

41. Юдин Д.Б.Вычислительные методы управления в условиях неполной информации.-М:Сов.радио.1974.

42. Ватолин А.А.О задачах линейного программирования и интервальными коэффициентами.-Журнал выч.математики и мат.физики. 1984.Т24.N11.

43. Вилкас Э.И.Майминас Е.З.Решения:теория,информация,моделирование. -М: Радио и связь.1981.

44. Вощинин А.П.,Сотиров Г.Р.Метод оптимизации объектов в условиях неопределенности целевой функции.-Перспективы и опыт внедрения статистических методов в АСУ ТП.Тез.докл.III Всесо-юзн.конф.Тула 1987.

45. Калмыков С. А.,Шокин Ю.И. ,Юлдашев З.Х.Методы интервального анализа.-Новосибирск:Наука.1986.

46. Кини Р.Л.,Райфа X.Принятие решений при многих критериях Предпочтения и замещения.М:Радио и связь.1984.л со1. JLUO

47. Макаров И.М. и др.Теория выбора и принятия решений.-М:Наука. 1982.

48. Орлов А.И.Задачи оптимизации и нечеткие переменные .-М:Знание.1980.

49. Трухаев Р.И.Модели принятия решений в условиях неопределенности. -М:Наука.1981.

50. Вощинин А.П.,Сотиров Г.Р. Оптимизация в условиях неопределенности. -Изд.МЭИ,СССР,'Техника' НРБ,1989.

51. Пугачев В.С.Теория вероятностей и математическая статистика. -М: Наука. 197*9.

52. Растригин Л.А.Статистические методы поиска.-М:Наука. 1968.

53. Ширяев А.Н.Статистический последовательный анализ.-М:Наука. 1976.

54. Вощинин А.П.Решение задач оптимизации по регрессионным моделям в АСУ ТП. Тр. ШИ. 1980. Вып. 507.

55. Вощинин А.П.Элементы оптимизации стохастических систем. -М: МЭИ, 1982.

56. Бочков А.Ф.,Вощинин А.П. ,Сотиров Г.Р.Интервальный анализ данных как альтернатива регрессионному анализу.Планирование и автоматизация эксперимента в научных исследованиях.Тез.долкл.IX Всесоюзн.конф.-М:Изд.МЭИ,1989,ч.1

57. Вощинин А.П.Выделение множества предпочтительных решений в задачах оптимизации в условиях неопределенности.-Тр.МЭИ 1982.

58. Вощинин А.П.Метод оптимизации объектов по интервальным моделям целевой функции.-Москва.МЭИ.1987.

59. Milanese М.,Belforte G.Estimation theory and uncertainty intervals evaluation in presence of unknown-but-bounded error: linear- families of models and estimations. IEEE Trans. 1982.л с л j.lm±1. АС-27.

60. Mo S.H., Norton J.P. Parameter bounding- identification algoritms for bounded-noise records.IEE Proc.1988,Pt.D.Vol.135 N2

61. Шмелев В.П. Специальный курс математического анализа.Часть 1. -Москва МЭИ 1974.

62. Стоян Ю.Г.,Винарский В.Я. Алгебро-топологические свойства Ф -объектов.-Харьков,1981(Препринт /АН УССР.Ин-т пробл.Машиностроения 166).бб.Алексадров П.С.Введение в теорию множеств и общую топологию. М. 1977.

63. Фуко Д.Б.,Фоменко А.Т.,Гунтмахер В.Л. Гомотопическая топология. -М.Изд-во Моск.ун-та 1969.

64. Стоян Ю.Г. Основная задача геометрического проектирования. Харьков. 1983 (Препринт /АН УССР.Ин-т пробл.Машиностроения 181).

65. Стоян Ю.Г. Пространства геометрических информации.Харьков. 1985(Препринт /АН УССР.Ин-т пробл.Машиностроения 223).69.0кунев Б.В.,Прохоренков П.А.,Баринов С.М. Оптимизация размещения лекал на ткани // Труды института / Смол.фил.МЭИ. 1993. - N5.- С.47-50.

66. Прохоренков П.А.,Окунев Б.В.,Куликов В.Г. Оптимизация объемного раскроя кристаллов.В сборнике научн.трудов СФМЭИ N1.Устройства и системы автоматического контроля.1992 г.

67. Выгодский М.Я. Справочник по высшей математике ,- Москва. "Наука",1975.

68. Дегтярев Ю.И.Методы оптимизации.-М."Советское радио". 1980.

69. Рвачев В.Л.Геометрические приложения алгебры логики.Техника, Киев, 1967.

70. Рвачев В.Л.,Стоян Ю.Г.К вопросу об оптимальном раскроематериалов.В кн.Вопросы теоретической кибернетики.-Киев."Наукова думка", 1965.

71. Edgar T.F.,Himmelblau D.Optimization of Chemical Processes. N.Y.iMcGraw Hill,1988.

72. Multicriteria Optimization in Engineering and in the Science/Ed.W.Stadier.N.Y.Plenum Press 1991.77.трейдер Ю.А.Равенство, сходство, порядок.- Москва.Наука. 1971.

73. Прохоренков П.А., Окунев Б.В., Храименков М.И. Разработка методов сортировки и выбора оптимальной плоскости разметки алмаза. Отчет о НИР,ОНИР,МЭИ,N01880053834,1990 г.

74. Окунев Б. В., Прохоренков П. А., Ковалков А. Н. Диалоговая система для раскроя кристаллов алмаза // Труды института / Смол.фил.

75. МЭИ. 1992.- N2.- С.169-179.

76. Епифанов В.И.,Песина А. Я.,Зыков Л.В.Технология обработки алмазов в бриллианты.-М:Высшая школа.1982.

77. Золотых В.Д.Критерии оценки ювелирных алмазов.-Сб.трудов НИИЧаспром.М.,1976.

78. Обработка алмазов.Сб.переводов ВНИИГознака № СССР,1962--1969 гг.

79. Орлов Ю. Л.Минералогия алмаза. -М.:Наука, 1973.

80. Бочаров A.M.,Симоненков В.А.,Тимошенков В.Е.Классификация алмазного сырья по системе SITY.Учебное пособие.МоскваЛ991.

81. Бонрой Д.Распиловка алмазов.Материалы Международной конференции по применению синтетических алмазов в промышленности. Киев :Наукова думка.1974.

82. Марков А.И.Ультразвуковое резание труднообрабатываемых материалов.-М.:Машиностроение 1968.

83. Окунев Б.В.,Прохоренков П.А.,Фомченков В.П.Разработка математических методов оптимального раскроя кристаллов алмаза // Труды института / Смол.фил.МЭИ. 1994.- С.14-19.

84. Авторское свидетельство. N 1710330 от 5.02.1990."Автомати-ческое устройство для разметки драгоценных камней"1. А сгfj.U I

85. Постников M.M.Аналитическая геометрия.-Москва,"Наука" 1979

86. Математика и САПР."Основные методы теории полюсов",Перевод с французского к.физ.-мат.н.Чигиря С.Д.Москва,Мир 1988.- J.UO lipjruiumeriyie i.

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

88. В системе х'Оу* рис.2.4.первый эллипс описывается системой уравнений 71.:

89. XI « a-cos(4i) У1 = b-sinUi) J где а,Ь- полуоси первого эллипса.

90. В системе х"Оу" второй эллипс описывается системой уравнений 713:

91. Х2 A-cos(42) 1 У2 - B-sin(42) где А,В-полуоси второго эллипса.

92. С учетом правила поворота и переноса осей координат 94,95. второй эллипс в системе координат хОу будет описываться системой уравнений:1. А спlua

93. Ф1 (=х=ГА• cos(42) +Х2) «003(82)-(В-sinCteJ+ya) -sin(82)(П. 2)

94. Ф2(42)=У»(A-cos(42)+X2)•sin(82)+(В•sin(42)+У2)•00s(82)где 82-угол поворота оси абсцисс(ординат) системы координат; х"Оу'* относительно оси абсцисс(ординат) системы координат хОу; Х2, У2~ координаты центра системы координат х"Оу" в системе координат хОу.

95. Функцию плотного размещения ,согласно,163 можно выразить:fi2.(B) = Ф(41)-Ф(42) (П.З)

96. Ф1"(41)*£'(4а) " Ф2'(42)Ф1'(41) 0 , (П.5)где Ф1* (Ci) ,?2(4i) * ,*i(te)* ,Ф2.(С»2,)производные от функций Ф1 (4i), 1>2(4i) ,Ф1 (42) A2U2);

97. А2 • cos (82) ос - В2 • sin (82) • 3

98. А2*«2 + В2«32 A2-sin(82)+ В2-cos(82)-3 / А2'«2 + В2-32л a-sin(0•(cos(81)sin(82)-sin(81)sin(82))+ +b-cos(0 *(sin(81)sin(82)+cos(81)cos(82));

99. В = a-sin(0•(cos(81)cos(82)+sin(81)sin(82))--b-cos(0•(cos(81)sin(82)-sin(81)cos(82));с* ' <v•Д о t«1. I , ч л

100. Рис.П.1. Бриллиант круглой формыл an 1uo ttwtf 4»/"«w л »тт»пиршилс ни«1. Л GET jluij1. Утверждай1. Начал1. Утверждаю1. ТАЛ!!'1. Бочаров А,1992 г.

101. Заместитель директора СФМЗИ по научнот.н,,доцент1. Круглов В. В/1. Щ I ге 0) ! >f-Lmi1992 г,ъ?///1. АКТ

102. Об использовании в СКТБ "КРИСТАЛЛ" алгоритмов и программ оптимизации разметки кристаллов алмаза и о оценки стоимости бриллиантов.

103. Диалоговая программа разметки кристаллов.

104. Диалоговая программа оценивающая стоимость алмазов с полным каталогом видеоизображений типового алмазного сырья.

105. Разработанные алгоритмы и программы могут служить основой для авто-* матизации процесса разметки алмазного сырья под бриллианты и более эффективного его использования.

106. Представители СКТБ "КРИСТАЛЛ" Представители СФИЭИ

107. Кутько Ю.И./ /Прохоренков П.А./

108. С^/ /Сидоренков К.А/ /Куликов В.Г./1. Окунев Б. В . /