WWW.OS.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Научные публикации
 

Pages:   || 2 | 3 |

«ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ ДВУМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА АНИЗОТРОПНОМ МАТЕРИАЛЕ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ МАТЕМАТИЧЕСК ...»

-- [ Страница 1 ] --

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

ПЕТРЕНКО Семен Васильевич

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ ДВУМЕРНЫХ

ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА АНИЗОТРОПНОМ

МАТЕРИАЛЕ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель – доктор технических наук, профессор М.А. Верхотуров УФА – 2005 Используемые в работе сокращения

Введение

Глава 1. Обзор существующих моделей и методов решения задачи нерегулярного размещения деталей сложных форм

1.1. Многообразие задач раскроя-упаковки

1.2. Классификация моделей раскроя-упаковки

1.3. Основные определения и постановка задачи размещения плоских геометрических объектов

1.3.1 Основные понятия и определения

1.3.2 Общая постановка задачи размещения плоских ГО

1.4. Методы решения задач упаковки ГО



1.4.1 Классификация методов решения задач нерегулярного размещения ГО

1.4.2 Точные методы решения задач нерегулярного размещения ГО..... 31 1.4.3 Методы комбинаторной оптимизации и способ выборочного размещения и удаления

1.4.4 Метод последовательного уточнения оценок

1.4.5 Решение задачи размещения плоских ГО на основе дискретнологического представления информации

1.5. Выводы по первой главе

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

2.1. Описание математической модели задачи

2.2. Решение задачи поиска локального оптимума

2.3. Иллюстрация работы метода

2.4. Выводы по второй главе

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

.............. 67

3.1. Алгоритм реализации итерационного метода нахождения локального экстремума

3.2. Построение выпуклой оболочки для многоугольника

3.3. Алгоритм разбиения невыпуклых многоугольников на выпуклые....... 73

3.4. Построение годографов для моделирования УВН и УРО

3.5. Ликвидация взаимного пересечения годографов

3.6. Выводы по третьей главе

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

4.1. Общая схема комбинации точного метода поиска локального экстремума и приближенных методов ПОР

4.2. Модификация предложенной схемы для классического «жадного»

алгоритма

4.3. Модификация предложенной схемы для метода ПОР по принципу «первый подходящий с упорядочиванием» (ППУ) на основе ДЛПИ и ЦК... 95

4.4. Вычислительные эксперименты

4.5. Выводы по четвертой главе

Заключение

Список литературы

Используемые в работе сокращения Р-У – раскрой-упаковка ГО – геометрический объект ОР – область размещения УВН – условия взаимного непересечения УРО – условие размещения в области ПОР – последовательно-одиночное размещение ОДР – область допустимых решений ЛП – линейное программирование МГП – моделирование геометрических преобразований ДЛПИ и ЦК – дискретно-логическое представление информации и цепное кодирование Введение Актуальность темы. На сегодняшний день и в обозримом будущем в различных сферах производства возникают и будут возникать проблемы ресурсо- и энергосбережения, связанные с задачами раскроя и упаковки (компоновки) (Р-У).

К таким задачам относятся:

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

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

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

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

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

Анализ отечественной и зарубежной литературы, информационных интернет-источников позволяет сделать вывод, что исследованием и разработкой методов решения данного класса задач занимаются: Харьковская школа Р-У академика Ю.Г.Стояна; Институт алгоритмов и научных вычислений Германии (Т. Ленгауэр); В. Миленковик, К. Даниэльс (США); К.





Доусланд, В. Доусланд (Великобритания); ряд российских ученых, среди которых Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов, А.А. Петунин, В.Д.

Фроловский [7].

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

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

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

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

Основные задачи

исследования в соответствии с поставленной целью сформулированы следующим образом:

1) Разработать математическую модель представления задачи двумерного размещения ГО с ограничениями в виде линейных неравенств.

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

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

4) Провести вычислительные эксперименты для разработанных методов.

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

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

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

Результаты, выносимые на защиту

:

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

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

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

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

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

Научная новизна работы заключается в следующем:

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

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

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

Практическая ценность работы состоит в создании математического и программного обеспечения для решения задач построения двумерных планов раскроя-упаковки, учитывающего технологические ограничения, возникающие при решении прикладных задач. Данные вычислительных экспериментов показывают, что при использовании разработанного программного обеспечения улучшение решения, полученного приближенным методом на основе классического «жадного» алгоритма, составляет от 0,5 до 8 %.

Основание для выполнения исследований Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в 2002-2005 гг. в рамках проектов РФФИ 01-99-00937 и 01-01-00510.

Внедрение результатов в учебном процессе Уфимского государственного авиационного технического университета;

в Рекламном агентстве RMC (г. Уфа).

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

Основные результаты работы докладывались и обсуждались на следующих конференциях:

Международная конференция «Информационные системы и технологии»

(Новосибирск, 2003);

Российская конференция «Дискретный анализ и исследование операций»

DAOR04 (Новосибирск, 2004);

XIII Байкальская международная школа семинар ИркутскСеверобайкальск «Методы оптимизации и их приложение»

(Северобайкальск, 2005);

Научно-технические семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета (2002-2005гг.).

Публикации. По теме диссертации опубликованы 7 работ.

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

Основное содержание работы

.

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

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

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

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

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

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

Заключение содержит основные выводы и результаты диссертационной работы.

Глава 1. Обзор существующих моделей и методов решения задачи нерегулярного размещения деталей сложных форм

1.1. Многообразие задач раскроя-упаковки Под задачами раскроя и (или) упаковки понимается широкий класс задач, объединенных однообразной логической структурой и допускающих различное толкование. В отечественной и зарубежной литературе [1, 2, 7, 5, 17, 9, 6, 7] они встречаются под следующими названиями:

задача раскроя запаса материала;

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

задача загрузки рюкзака;

задача упаковки ящиков (контейнеров);

задача загрузки транспорта;

задача выбора ассортимента;

задача планировки помещений;

задача обеспечения ритмичности производственного процесса;

задача распределения памяти вычислительной машины;

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

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

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

Приведенные проблемы рассматриваются далее под одним названием:

задачи раскроя и упаковки (Р-У). Логической основой для отнесения какойлибо проблемы к классу задач Р-У является наличие двух групп сущностей. К первой группе относятся, как правило, крупные сущности (именуемые далее – области), ко второй группе – малые (именуемые – объекты). Требуется установить соответствие и порядок назначений между некоторыми областями и объектами. При этом предполагается, что среди объектов существует такой, что ему может быть назначена хотя бы одна область (разрешимость задачи).

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

Впервые задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым [52]. В его докладе «О кройке одежды» в 1878 г. рассматриваются вопросы о наилучшем покрытии кривых поверхностей плоскими выкройками из ткани.

В 1885 г. была опубликована работа Е.С.Федорова [51], в которой рассматривался ряд вопросов, возникавших при изучении кристаллов как природных многогранников. В книге «Симметрия и структура кристаллов»

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

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

Так, в конце 30-х – начале 40-х годов фундаментальные исследования в области рационального раскроя были выполнены Л.В.Канторовичем и В.А.Залгаллером [32, 33, 34, 35]. Ими было показано, что для расчета оптимального раскроя могут быть использованы методы линейного программирования. Для преодоления трудностей, связанных с построением допустимых карт раскроя, указанными авторами были предложены приемы, которые, по существу, предвосхитили идеи динамического программирования.

В 1951 году [30] Данциг, независимо от Л.В.Канторовича и В.А.Залгаллера, также показал связь между задачами раскроя и теорией линейного программирования.

В 1961 г. [67] независимо от работ Залгаллер В.А. и Канторовича Л.В.

Гилмори и Гомори решили с помощью метода линейного программирования проблему одномерного раскроя. В 1963 г. [68] они применили технику линейного программирования к задаче раскроя бумаги. В 1965г. [69] ими был предложен метод решения двумерной задачи раскроя. Для получения решения они ввели ограничения на направления резов, т.е. гильотинный раскрой, который может быть применен для решения практических проблем. В 1966 г.

для решения задач одномерного и двумерного раскроев они использовали динамическое программирование.

В 1960-х годах методам решения задач фигурного раскроя были посвящены работы Л.Б.Беляковой [4, 3]. В 1975 г. Фримэн [65] первым из зарубежных исследователей рассмотрел нерегулярное размещение объектов в прямоугольные области.

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

Во второй половине 70-х годов появилось много эвристических способов решения [7, 77].



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

В начале 90-х годов для решения проблемы раскроя были применены другие эволюционные методы, такие как, Simulated Annealing, Tabu Search, Ant Colonies и др.[54].

В зависимости от мерности раскраиваемого материала различают одномерный, двумерный раскрой и объемный раскрой-упаковку (рис. 1).

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

Рис. 1. Задачи раскроя и упаковки.

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

Все остальные способы реализации раскроя-упаковки – негильотинные.

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

Задачи нерегулярного размещения плоских геометрических объектов относится к классу NP-трудных задач [63]. В общем случае и ограничения, и функция цели для задачи нерегулярного размещения плоских ГО являются нелинейными.

Решению задачи нерегулярного фигурного раскроя посвящены работы [2, 1, 29, 38, 42, 47]. Достаточно полный обзор алгоритмов и методов нерегулярного фигурного раскроя приведен в [10].

В зависимости от изменения свойств материала Р-У различают размещение ГО на изотропном материале, одинаковое по всем направлениям, и анизотропном материале, различное по разным направлениям. Анизотропное размещение ГО накладывает жесткие ограничения на возможность поворота ГО во время размещения, делая такой параметр размещения ГО, как угол поворота постоянным или значительно уменьшая область его определения, поэтому является фактором, упрощающим решение соответствующей задачи упаковки ГО.

1.2. Классификация моделей раскроя-упаковки В основу классификации моделей положены известные работы Л.В.

Канторовича и В.А. Залгаллера [35], Э.А. Мухачевой [39], И. Терно [80] и Дикхофа [64].

Среди множества различных факторов, определяющих классы моделей РУ, выделим следующие основные характеристики:

1) мерность областей: различаются детерминированные (Д) и стохастические (С) модели, соответствующие областям с фиксированными и случайными параметрами;

2) ассортимент областей: единственная область (задачи Г – генерирования Р-У) или много областей (задачи П – планирования Р-У);

3) вид назначения: все объекты назначаются выборке областей (задача З – на заказ) или всем областям назначаются объекты некоторой выборки (задача О – оперативный Р-У);

4) ассортимент объектов: много или мало объектов каждого вида порождает непрерывную (Н) или целочисленную (Ц) модели планирования Р-У;

5) оптимизация: однопараметрическая (Е) или многопараметрическая (M) оптимизация в задачах Р-У;

6) размерность объектов и областей: одномерные, двумерные, трехмерные или N-мерные задачи;

7) геометрия объектов: прямолинейные (задачи Л) или фигурные (задачи

Ф) объекты.

Фактор-классификация основных моделей Р-У изображена на рис. 2.

На верхнем уровне классификации находятся исходные данные (детерминированные или случайные меры областей). Учитывая, что в приведенной классификации детализированы только детерминированные модели, отведем для идентификации ситуации Р-У 6 позиций, первые 3 из них предназначены для задачи планирования, последние 3 – для задачи генерации Р-У. Таким образом, в записи вида /a/b/c/d/e/f/ каждому символу a, b,...

отвечает соответствующий фактор, начиная с вида назначения. Например, запись /О/Ц/Е/2/Ф/*/ означает, что решается задача оперативного планирования Р-У, при этом используется целочисленная модель с однопараметрической оптимизацией. В задаче генерации рассматривается двумерная задача фигурного раскроя. Последний символ «*» означает, что для фигурного раскроя вид реализации не указан.

–  –  –

В приведенной классификации [17] рассматривается 8 различных постановок задач планирования и 7-генерации Р-У. Учитывая, что задача генерации включается в процесс решения задачи планирования Р-У, имеем 8 * 7 = 56 различных моделей задачи планирования Р-У, а с учетом локальной реализации задач генерации, получаем 56 + 7 = 63 основных моделей.

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

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

1.3. Основные определения и постановка задачи размещения плоских геометрических объектов 1.3.1 Основные понятия и определения Под плоским геометрическим объектом пространства R2 будем понимать двухпараметрические точечные множества, ограниченные соответственно замкнутыми, открытыми, связными или несвязными точечными подмножествами s, граница которых определяется каноническим уравнением [50]:

f ( x, y ) = 0 (1-1) Здесь знак = соответствует точкам, принадлежащим границе s, знаки и соответствуют точкам, лежащим вне и внутри границы s, если s – замкнутая линия, или точкам, лежащим по разные стороны разомкнутой границы s.

–  –  –

Рис. 4. Задание системы координат в k-мерном пространстве.

Для задания в выделенном R k -пространстве k-мерной системы координат X1OX2…Xk, связанной с ГО, относительно k-мерной системы X1OX2…Xk пространства Rk, требуется задать: начало координат – точку O (k параметров) и оси OXk (по к-1 параметру на каждую в общем случае). Всего k + (k 1) k = k 2 параметров.

Таким образом, для однозначного определения положения двумерного ГО в R2-пространстве требуется задать четыре параметра. Если же оси двумерной системы координат будут выбраны не произвольно, а связаны определенным соотношением, например, взаимно перпендикулярны, то число параметров для определения ГО в такой системе координат будет меньше на единицу, т.е. равно трем.

Если обозначить XOY систему координат плоскости, а X Y – систему, связанную с ГО, - угол между осями XO и OX, то O точечное множество, определяющее плоский ГО в двумерном пространстве и заданное каноническим уравнением (1-1) и согласно формулам преобразования движения, будет определяться неравенством:

f [( x x' ) cos + ( y y ' ) sin, ( y y ' ) cos ( x x' ) sin ] = (1-2) = F ( x, y, x ', y ', ) 0 Движением (процессом размещения) будем считать такие преобразования ГО, которые сохраняют его форму, изменяя лишь параметры положения (в вышеприведенном примере это x, y, ).

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

Введем обозначения для внутренних точек ГО P – Int P, для точек, лежащих на границе – clP, также обозначим операции пересечения, объединения и вычитания двух ГО P1 и P2 соответственно [50].

Два ГО P1 и P2 могут пересекаться IntP1 I IntP2, не пересекаться – P1 I P2 =, касаться – clP1 I clP2, IntP1 I IntP2 =.

–  –  –

Под годографом функции плотного размещения (в дальнейшем – внешним годографом или просто годографом) Hij объекта Pj относительно Pi понимается такое множество положений центра объекта Pj, при котором выполняется условие IntPi I IntPj = (рис. 5).

Внутренним годографом H ij объекта Pj относительно Pi понимается такое множество положений центра объекта Pj, при котором выполняется условие Pi I Pj = Pj (рис. 5).

Размещением (укладкой, упаковкой) называется такое расположение ГО, когда они не имеют пересечений между собой, т.е. когда выполняется условие IntPi I IntPj = для всех пар ГО i и j её составляющих.

–  –  –

где m = ±1,± 2,...,± ; j 1,2,...,k.

Остальные размещения составляют группу нерегулярных.

Качество заполнения пространства может быть оценено при помощи численной величины, называемой критерием размещения (заполнения).

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

1.3.2 Общая постановка задачи размещения плоских ГО Общая формулировка задачи заключается в нахождении оптимального варианта размещения геометрических объектов в пределах области Р-У с учетом критерия размещения [7]. Предполагая применение средств вычислительной техники важно, всесторонне проанализировав ситуацию, правильно с математической точки зрения сформулировать задачу и выбрать критерий оптимизации размещения.

Общая постановка задачи плотного размещения ГО формулируется следующим образом:

Задача. Пусть имеется набор ГО Pi, i=1, 2, …, n, которые требуется разместить в области пространства R2 в соответствии с каким-либо условием (рис. 6).

–  –  –

Рис. 6. Непересечение ГО между собой и границей области Р-У.

Обозначим ij кратчайшее расстояние между границами s i и s j ГО Pi и P j. ГО должны располагаться в области без пересечений друг с другом и с

–  –  –

цели R p, p = n t, где n – число ГО, t – число параметров их положения. В то же время из-за комбинаторной сложности она относится к классу NP-трудных задач [62].

1.4. Методы решения задач упаковки ГО 1.4.1 Классификация методов решения задач нерегулярного размещения ГО Задачи размещения ГО получили широкое распространение как в теории, так и на практике и, поэтому, существует множество методов, применяемых для их решения.

Отличительной особенностью этого класса задач по сравнению с линейным и прямоугольным видами раскроя – упаковки является трудность определения условий взаимного непересечения в результирующих картах Р-У.

Если в задачах прямолинейного раскроя-упаковки эта проблема решается тривиально и отдельно не выделяется, то при решении задач размещения ГО она является самостоятельной и вносит дополнительные сложности в разрешение основной задачи – оптимизации Р-У.

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

Классификация методов решения таких задач выглядит следующим образом [7] (рис. 7).

Ме т од ы ре ше ния задач нерег улярног о раз ме ще ния ГО

–  –  –

Рис. 7. Классификация методов решения задач нерегулярного размещения ГО.

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

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

Для случая прямоугольников решение будет состоять из следующих трех этапов:

нахождение для каждого ГО описывающего его прямоугольника минимальной площади (для изотропного, например, размещения ГО);

размещение полученных прямоугольников в заданную область Р-У;

доуплотнение исходных ГО после «отброса» прямоугольных оболочек.

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

Тем не менее, понятно, что большинство реальных задач размещения ГО имеет дело с такими объектами, которые сильно отличаются от простых ГО.

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

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

Точные методы базируются на использовании идей и методов линейного программирования [49, 63]. В частности методы активного набора [26].

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

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

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

Методы поиска локальных экстремумов основываются как на тех же идеях, используемых для точного решения задач [49, 73], так и методах нелинейного программирования (например, методом штрафных функций [31]).

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

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

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

Для него поиск решения осуществляется последовательными шагами, ведущими от исходной точки из области допустимых решений (ОДР) через

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

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

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

Во втором случае используются классические методы условной оптимизации. В частности те же методы, которые использовались для нахождения точных решений: методы активного набора [26].

Вторым набором методов в приближенных способах решения являются методы нахождения рациональных (допустимых) укладок близких к оптимальным. Они, в отличие от вышерассмотренных методов, являются эвристическими. Но, как известно [45, 36], такие методы являются широко распространенными и оправданными при решении NP-трудных задач. Они отличаются тем, что, как правило, на каждом элементарном шаге решения оперируют отдельными геометрическими объектами, т.е. производят некоторые геометрические преобразования каждого из них.

Безусловно, существует большое количество разнообразных эвристических методов, применяемых для решения задач нерегулярного размещения ГО. В основном же используются два, наиболее развитых и дающих неплохие результаты, класса методов. Первый – это метаэвристики типа «simulated annealing(SA)», «genetic algorithm(GA)», «tabu search(TS)», «ant colonie(AC)» и их модификации. И, второй, эвристические методы, разработанные специально для этого класса задач.

Нередко для решения задач нерегулярного размещения ГО применяют последовательно несколько подходов. Двухэтапный подход размещения ГО в нескольких областях представлен Dali и Talolu [61]. На первом этапе распределение объектов по областям выполняется методами динамического программирования. Собственно размещение ГО в каждой области выполняется с помощью эвристических подходов на втором этапе. Bounsaythip, Maouche и Roussel [58, 71] используют локально-глобальный подход. Локальная оптимизация применяется для уменьшения границ прямоугольной оболочки двух ГО. Глобальная часть алгоритма построена на основе метода «эмуляции отжига» и «ближайшего подходящего». Дерево решений строится добавлением нового объекта к размещению подмножества объектов с использованием локальной эвристической процедуры оптимизации.

1.4.2 Точные методы решения задач нерегулярного размещения ГО

–  –  –

( x R k,t = 1,2,...,m ) с определенными для каждой пары неравенств операциями конъюнкции или дизъюнкции, представленными в виде симметричной матрицы = ij такой, что ij = 1 соответствует операции конъюнкции между i-м и mm j-м неравенствами, а ij = 0 – операции дизъюнкции.

–  –  –

определяющей допустимую область размещения объекта Pi относительно Pj, необходимо выполнить следующие действия:

1) построить годограф функции плотного размещения Hij объекта Pi относительно Pj;

2) описать, используя предикатное представление, допустимую область Dij;

3) перейти от предикатов к структуре линейных неравенств.

–  –  –

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

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

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

Рис. 9. Годограф объекта P2 относительно объекта P1.

–  –  –

элементарную конъюнкцию в форме (1-13).

Матрица 12 структуры, описывающей условия взаимного непересечения объектов, изображенных на рис. 8, и построенная по предикатному описанию области Gij (рис.

9), выглядит так:

12 =

–  –  –

Для компактного и удобного представления информации о структуре неравенств в виде объединения систем можно в форме (1-11) использовать вместо симметричной матрицы размерностью ( mij mij ) несимметричную

–  –  –

c T u i c T u i 1, p, u i R 2 n + 1.

Одно из достоинств этого метода – то, что он является итерационным.

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

Каждая итерация этого процесса будет заключаться в:

1) выборе вектора p – направления движения, обеспечивающего уменьшение функции цели, и скалярной величины – длины шага в ui этом направлении, гарантирующей принадлежность области допустимых решений;

2) построении очередного приближения u i в соответствии с (1-19) и проверке в этой точке выполнения условия (1-18).

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

Движение по невыпуклым областям осуществляется за счет последовательного движения по выпуклым областям. В процессе решения задачи каждое очередное приближение u k 1 принадлежит, в общем случае, нескольким выпуклым подмножествам допустимого множества решений, но, несмотря на это, для движения в направлении экстремума можно ограничиться одним из них. Тогда направление движения и длина шага выбираются так, как это производится при движении по выпуклой области, до тех пор, пока не будет найден минимум на этом подмножестве, например, на r -ом шаге. Затем области G, которые производится анализ всех выпуклых подмножеств содержат u r. Если находится хотя бы одно такое подмножество, для которого u r не является точкой экстремума, то движение продолжается теперь уже по этому подмножеству. Иначе, в соответствии с (1-18), u r – точка локального минимума на области G.

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

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

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

Здесь Gj – выбирается из тех выпуклых подобластей, которым принадлежит u k 1.

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

–  –  –

Предположим, что точка размещения p i ГО Pi находится внутри выпуклой области C ij ( p j c j ), для каждой пары ГО Pi и P j, 1 i j n, и для каждой пары Pi и W, 1 i n, соответственно (рис. 10).

–  –  –

C iW H iW,1 i n, то координаты размещения, вычисленные методами ЛП, будут удовлетворять соответствующим ограничениям. Метод поиска для определения этих подмножеств C ij H ij, которые определяют оптимальное

–  –  –

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

На каждой итерации алгоритм берет очередной список C из стека. Вопервых, алгоритм делает проверку – есть ли в списке такой элемент C ij, что

C ij H ij. Если не существует таких элементов, то C не нужно разбивать на

части и при помощи методов ЛП может быть найдено такое размещение ГО, которое не содержит их взаимопересечений. Если полученная упаковка лучше, чем наилучшая из найденных ранее, то алгоритм сохраняет эту упаковку как новое лучшее размещение. Если же в списке есть такой элемент C ij, что

–  –  –

выполняется, то размещения, которые соответствуют подмножеству C z больше не могут быть свободны от взаимопересечений. Еще одним условие для выбора C ij и C ij является следующее: ( C ij U C ij ) I H ij = C ij I H ij. Это гарантирует, что нет таких возможных размещений Pi относительно P j (определяемых H ij ), которые были бы потеряны на шаге разбиения. Задачи, которые определяются списками C z, z = 1,2, проверяются на возможность применения методов ЛП.

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

Пример этого алгоритма представлен на рисунке 11. На нем показана та часть дерева решения, которая соответствует двум ГО – P1 и P2. Корень этого поддерева не является корнем всего дерева решения.

Уровень 0: C, список который принадлежит корню поддерева C = ( H 1W, H 2W, 2 ), C1W уже разделена на выпуклые области, одной из которых является H 1W (не показана на рисунке), тоже самое сделано для C 2W. C 12 = 2 (светлая область) еще не разбивалась на подмножества. Точка занесения объекта P1 должна находиться внутри C 12 ( p 2 c 2 ). Все размещения, в которых P1 и P2 находятся внутри области W, удовлетворяют ограничениям, наложенным на список C.

–  –  –

C12 I H 12, C12 I H 12.

Это разбиение ограничивает возможные размещения P2 относительно P1, что приводит к таким расположениям ГО, которые соответствуют оптимальным размещениям.



Pages:   || 2 | 3 |
Похожие работы:

«В. Н. Игнатович ВВЕДЕНИЕ В ДИАЛЕКТИКОМАТЕРИАЛИСТИЧЕСКОЕ ЕСТЕСТВОЗНАНИЕ Киев – 2007 УДК 168.521:528.8:536.7 ББК 15.1 И26 Рекомендовано к печати Ученым советом факультета социологии Национального технического университета Украины “Киевский политехнический институт” (Протокол №3 от 22.06.2007) Рецензенты А. Т. Лукьянов, канд. филос. наук, доц. А. А. Андрийко, д-р хим. наук, проф. Л. А. Гриффен, д-р техн. наук, проф. Ответственный редактор Б. В. Новиков, д-р филос. наук, проф. Игнатович В. Н. И 26...»

«УДК 530 ФОРМИРОВАНИЕ У СТУДЕНТОВ МОТИВАЦИИ К САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ КУРСА ОБЩЕЙ ФИЗИКИ Трунов Г.М. ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет», Пермь, Россия (614990, г. Пермь-ГСП, Комсомольский пр-т, 29), e-mail: plazma@perm.ru В последние несколько лет преподавателям физики вузов приходится сталкиваться с тем обстоятельством, что многие студенты плохо усваивают знания курса общей физики. В результате опроса выяснилось, что некоторые студенты 4-5 курсов...»

«Пиролизные котлы ASTRA G 40 MES и ASTRA G 40 MS Подробные технические характеристики. Рекомендуемое топливо. Подключение к отопительной системе. Требования к дымовой трубе и тяге. Подробные технические характеристики Модель газогенераторного (пиролизного) котла Astra G-40 MES и Astra G-40 MS Твердотопливный газогенераторный Тип котла котел центрального отопления Мощность, кВт 40 Электронное (MES) или Тип управления котла терморегуляторное (MS) Тип вентилятора котла Вдувной Коэффициент полезного...»

«КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н. ТУПОЛЕВА (КНИТУ-КАИ) ИНСТИТУТ РАДИОЭЛЕКТРОНИКИ И ТЕЛЕКОММУНИКАЦИЙ ИРЭТ Кафедра Конструирования и технологии производства электронных средств КитПЭС Заведующий кафедрой: Карамов Фидус Ахмадиевич, д.т.н., профессор Общее количество преподавателей: 17 из них профессоров: 3 доцентов: 9 старших преподавателей:4 ассистентов: 1 УВП: 7 Общая информация Кафедра реорганизована из кафедр ИРЭТ “Конструирование и производство...»

«УТВЕРЖДАЮ Проректор по научной работе ФГБОУ ВПО «Самарский государственный технический университет», д.т.н., проф. Ненашев М.В. 28 января 2015 г. ОТЗЫВ ВЕДУЩЕЙ ОРГАНИЗАЦИИ ФГБОУ ВПО «Самарский государственный технический университет» на диссертацию Глушак Елены Владимировны «Исследование и разработка математических моделей распределенных центров обслуживания вызовов» на соискание ученой степени кандидата технических наук по специальности 05.12.13 – Системы, сети и устройства телекоммуникаций...»

«И. В. Зубрилина, учитель английского языка, ГУО «Гимназия №1 г. Дятлово», Гродненская область ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ СЕРВИСОВ WEB 2.0. В ОРГАНИЗАЦИИ ПРАКТИКИ УПРАВЛЕНИЯ УЧЕБНОЙ ДЕЯТЕЛЬНОСТЬЮ УЧАЩИХСЯ Важность общения и социального взаимодействия в процессе обучения бесспорна, поэтому неудивительно, что в связи с переходом к компетентностному подходу в современной образовательной практике все большее распространение получают и используются в преподавании различных учебных предметов интернет...»

«Научный потенциал регионов на службу модернизации. Астрахань: АИСИ, 2011. 290 с. ТЕОРИЯ РОСКОШИ ВЕРНЕРА ЗОМБАРТА Е. Г. Ефимов Волгоградский государственный технический университет г. Волгоград, Россия В апреле 2009 г. спикер Совета Федераций Сергей Миронов выступил с инициативой введения в России налога на роскошь. Законопроект был отклонен, однако это событие в очередной раз заставило говорить о феномене роскоши в жизни современного общества и последствиях этого явления. Как следует из анализа...»

«Электронный архив УГЛТУ 179 ЭКО-ПОТЕНЦИАЛ № 3 (7), 2014 УДК 72.03 Л.И. Аткина, А.И Григорьева Уральский государственный лесотехнический университет, г. Екатеринбург ВЕХИ ИСТОРИИ ЕКАТЕРИНБУРГА (НА ПРИМЕРЕ «ЗЕЛЕНОЙ РОЩИ») В Екатеринбурге, который приближается к своему 300-летию, осталось совсем немного уголков, которые сохранились к настоящему времени, и один из них – парк Зеленая роща. История парка тесно связана с созданием Ново-Тихвинского женского монастыря (рис. 1 и 2). В 1772 г. в...»

«РЕЗЕРВИРОВАННЫЙ ИСТОЧНИК ПИТАНИЯ РИП-12 RS Этикетка АЦДР.436534.004 ЭТ 1 ОСНОВНЫЕ ТЕХНИЧЕСКИЕ ДАННЫЕ 1.1 Общие сведения 1.1.1 Резервированный источник питания РИП-12 RS (далее – РИП) предназначен для группового питания средств пожарной автоматики, извещателей и приёмноконтрольных приборов охранно-пожарной сигнализации, систем контроля доступа и других устройств, требующих резервного электропитания с напряжением 12 В постоянного тока. 1.1.2 РИП рассчитан на непрерывный круглосуточный режим...»

«Наука и Образование: научно-техническое издание: Модель представления знаний при создании адаптивной информационной системы Эл № ФС 77 30569. Государственная регистрация №0420900025. ISSN 1994-0408 Модель представления знаний при создании адаптивной информационной системы # 03, март 2010 Архив автор: Елисеев Д. В. ФОТОРЕПОРТАЖИ Первые УДК. 004.82 публикации Программы и МГТУ имени Н.Э. Баумана программные d-eli@mail.ru системы Учебные Введение программы Большинство автоматизированных...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ НАЦИОНАЛЬНЫЙ СТАНДАРТ ГОСТ Р РОССИЙСКОЙ ХХХХ ХХ ФЕДЕРАЦИИ СИСТЕМА ЗАЩИТЫ ОТ ФАЛЬСИФИКАЦИЙ И КОНТРАФАКТА. ПРОДУКЦИЯ ВЫСОКОТЕХНОЛОГИЧНЫХ ОТРАСЛЕЙ ПРОМЫШЛЕННОСТИ. Требования к качеству символов Data Matrix для маркирования изделий SAE AS9132-2015 Data Matrix quality requirements for parts marking (IDT) Москва Стандартинформ 20 ГОСТ Р (проект, первая редакция) Предисловие Цели и принципы стандартизации в Российской Федерации...»

«Вестник МГТУ, том 13, №1, 2010 г. стр.37-40 УДК 33 : [001.3+008]+330.13(045) Экономика научно-технического прогресса: ретроспективный анализ Ф.Ф. Рыбаков Экономический факультет СПбГУ, кафедра экономической теории и экономической политики Аннотация. Статья посвящена ретроспективному анализу путей становления экономики научнотехнического прогресса. Рассмотрены проблемы, которые возникли при изучении экономических закономерностей развития науки и техники, особое внимание уделяется проблеме...»

«Российская Академия Естествознания Издательский дом Академии Естествознания Ж.Е. Фирилёва АДАПТИВНЫЙ ФИТНЕС В НЕЙРОМОТОРНОЙ РЕАБИЛИТАЦИИ ЧЕЛОВЕКА Монография Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности: 49.03.02 – «Физическая культура для лиц с отклонениями в состоянии здоровья (адаптивная физическая культура)» по профилю «Адаптивный спорт» Москва УДК 615 851 83...»

«Общество с ограниченной ответственностью «Строй-ТК» структурированные кабельные системы Проектирование электроснабжение и электроосвещение видеонаблюдение контроль доступа Доставка охранно-пожарная сигнализация системы оповещения кондиционирование, вентиляция Монтаж отопление электроизмерительная лаборатория системы молниезащиты и заземления Ремонт системы для медицинских учреждений ISO 9001:2000 SERTIFIED системы часофикации Модернизация коллективного приема телевидения умный дом ремонт офисов...»

«ОГАОУ СПО «Алексеевский агротехнический техникум» Обеспечение образовательного процесса электронными информационными ресурсами и средствами обеспечения образовательного процесса (по состоянию на 1апреля 2015 года) № Дисциплина, ФИО преподавателя Наименование и краткая характеристика библиотечноКоличество п/п информационных ресурсов и средств обеспечения экземпляров, образовательного процесса, в том числе электронноточек доступа библиотечных систем и электронных образовательных ресурсов...»





Загрузка...


 
2016 www.os.x-pdf.ru - «Бесплатная электронная библиотека - Научные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.