Введение к работе
Актуальность темы исследования. Необходимость создания ресурсосберегающих технологий в современных условиях не вызывает сомнения. Проблема ресурсосбережения бьша и остается чрезвычайно важной. Поэтому представляет большой интерес расчет планов рационального раскроя материалов. Актуальность проблемы оптимального раскроя объясняется не только очевидной эффективностью использования рациональных планов раскроя на производстве, но и многообразием постановок задач раскроя, трудностью создания совершенных математических моделей и выбора методов их решения.
Проблема оптимального раскроя объединяет различные по математической постановке задачи. В литературе они встречаются под названиями : задачи раскроя, упаковки, размещения, загрузки, распределения и т. д. Общим для них является наличие двух групп объектов. К первой группе откосятся большие объекты ^именуемые раскройными областями), ко второй -малые. Требуется установить соответствие и порядок назначений между объектами и раскройными областями.
Диссертационная работа посвящена задаче плотной упаковки плоских геометрических объектов, которая является одной из наименее изученных и формализованных плоских задач раскроя-упаковки. Она имеет широкое применение практически во всех отраслях промышленности. Кроме того, к ней можно свести некоторые другие оптимизационные задачи.
Задача упаковки плоских геометрических объектов относится к классу NP - трудных задач, поскольку, как было установлено Гэри и Джонсоном, даже частный случай негильотинного прямоугольного раскроя - размещение в вертикальной полуполосе набора прямоугольников одинаковой ширины с различными высотами является NP - полной задачей. А так как заготовки имеют сложную геометрическую форму, кроме комбинаторной сложности, для рассматриваемой задачи характерна еще сложность моделирования геометрических форм заготовок. Все это и ряд других особенностей задачи объясняют отсутствие в этом классе точных методов полиномиальной сложности для получения глобального оптимума. Большинство разработанных методов являются эвристическими. А при разработке ПО широко используется интерактивный подход. Применение на практике точных методов поиска локальных опгимумов в настоящее время ограничено размерами задачи. Поэтому, остается актуальной разработка эффективных быстродействующих алгоритмов.
Новым квази-оптимизацнонным аппаратом являются "псевдо"- оценки, близкие по смыслу к оценкам Л.В. Канторовича. Методы, основанные на оценках, оказались эффективными для задач прямолинейного раскроя и параллелепипедной упаковки. В данной работе впервые проведено исследование применимости "псевдо"-оценок для общей задачи упаковки плоских геометрических объектов.
Цель и задачи работы : Разработка методов и алгоритмов решения задачи
плотной упаковки плоских геометрических объектов с применением "псевдо"-
оценок, близких по смыслу к оценкам Л.В. Канторовича и создание на их
основе программного обеспечения. Достижение цели потребовало решения
следующих задач: ,
-
построение двухуровневой схемы решения поставленной задачи, в которой на первом уровне решается подзадача моделирования плотного движения геометрических объектов в раскройной области, на втором -подзадача упорядочивания геометрических объектов при размещении (подзадача оптимизации);
-
разработка эвристических алгоритмов моделирования плотного движения геометрических объектов на основе дискретно-логического описания форм объектов и раскройной области;
-
разработка метода оптимизации размещения геометрических объектов на основе интерпретации оценок Л.В. Канторовича;
-
разработка серии эвристических алгоритмов на базе общей схемы метода оценок;
-
исследование эффективности алгоритмов.
Методы исследования базируются на основных положениях математического программирования, вычислительной геометрии, машинной графики, объектно-ориентированного программирования. Использованы методы проведеній вычислительного эксперимента для исследования эффективности алгоритмов.
Научная новизна работы заключается в следующем :
разработаны эффективные алгоритмы моделирования геометрических преобразований на базе дискретно-логического представления информации;
исследован подход к решению задачи упаковки плоских геометрических объектов на базе основного понятия линейного программирования (ЛП)- оценок (двойственных переменных), предложены формулы подсчета оценок для геометрических объектов произвольной конфигурации;
на основе метода оценок разработана серия эвристических алгоритмов;
- получены предварительные выводы о поведении метода оценок.
Практическая ценность. Предложенные в диссертации методы упаковки
плоских геометрических объектов расширяют возможности численного моделирования задач раскроя-упаковки. Разработанный пакет программ может быть использован как автономно, так и в составе комплекса программных средств "CUT-CAD", предназначенного для проектирования раскроя материала на заготовки линейной, фигурной и прямоугольной форм. Результаты эксперимента могут быть положены в основу будущей экспертной системы для выбора подходящего программного модуля в системах автоматизированного проектирования. Важной областью применения программ является также учебный процесс.
На защиту выносятся : "' ,7 ;. ' ;<
методы и алгоритмы '; моделирования плотного движения геометрических объектов в раскройной области;
формулы оценок для плоских геометрических объектов произвольной конфигурации;
метод оценок для задачи упаковки плоских геометрических объектов;
эвристические алгоритмы метода оценок; у. -'
программное обеспечение.1' '' -?Л'
Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались : на всероссийской молодежной научно-технической конференции "Технология и оборудование современного машиностроения" (1994, г.Уфа), на международной научно-технической конференции "Ленинские горы-95" (1995, г. Москва), на всероссийской конференции "Математическое программирование и приложения"(1995, г.Екатеринбург), на конференции 10-й Байкальской школы-семинара "Методы оптимизации и их приложения"(1995, г.Иркутск), на семинарах института вычислительной математики Дрезденского технического университета(1997, г.Дрезден, ФРГ), на семинаре Немецкого национального исследовательского центра компьютерных технологий (1997, г.Боїш), на семинарах кафедры ВМиК УГ'АТУ.
Публикации. По теме диссертации опубликовано 7 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 97 названий. Общий объем работы -121 страница, 5 приложений.