автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Численные методы плотной упаковки плоских геометрических объектов на базе интерпретации оценок Л. В. Канторовича

Р Г Б ОД

о 6 янв 1998

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

СЕРГЕЕВА Оксана Юрьевна

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

05.13.16 — Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

УФА 1997

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

Научный руководитель - доктор технических наук, профессор Мухачева Э.А.

Официальные оппоненты - доктор физико-математических наук, профессор Спивак С.И., кандидат физико-математических наук, доцент Курмангалеева A.M.

Ведущая организация - Уфимский государственный нефтяной ; технический университет.

Защита состоится " /3 " Q(_1998 г. в/£час. на

заседании диссертационного совета Д-064.13.02 при Башкирском государственном университете по адресу : 450074, г. Уфа, ул. Фрунзе, 32, математический факультет.

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

Автореферат разослан "_"_;_1997 г.

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

Ученый секретарь диссертационного совета Д-064.13.02

Морозкин Н.Д.

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

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

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

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

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

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

Цель и задачи работы : Разработка методов и алгоритмов решения задачи плотной упаковки плоских геометрических объектов с применением "псевдо"-оценок, близких по смыслу к оценкам JI.B. Канторовича и создание на их основе программного обеспечения. Достижение цели потребовало решения следующих задач: ,

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

2) разработка эвристических алгоритмов моделирования плотного движения геометрических объектов на основе дискретно-логического описания форм объектов и раскройной области;

3) разработка метода оптимизации размещения геометрических объектов на основе интерпретации оценок Л.В. Канторовича;

4) разработка серии эвристических алгоритмов на базе общей схемы метода оценок;

5) исследование эффективности алгоритмов.

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

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

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

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

- на основе метода оценок разработана серия эвристических алгоритмов;

- получены предварительные выводы о поведении метода оценок.

Практическая ценность. Предложенные в диссертации методы упаковки

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

На защиту выносятся : ,7 " ;<

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

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

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

- эвристические алгоритмы метода оценок; -

- программное обеспечение.'■ • .г .

Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались : на всероссийской молодежной научно-технической конференции "Технология и оборудование современного машиностроения" (1994, г.Уфа), на международной научно-технической конференции "Ленинские горы-95" (1995, г. Москва), на всероссийской конференции "Математическое программирование и приложения"(1995, г.Екатеринбург), на конференции 10-й Байкальской школы-семинара "Методы оптимизации и их приложения"(1995, г.Иркутск), на семинарах института вычислительной математики Дрезденского технического университета(1997, г.Дрезден, ФРГ), на семииаре Немецкого национального исследовательского центра компьютерных технологий (1997, г.Бонн), на семинарах кафедры ВМиК УГ'АТУ.

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

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

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

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

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

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

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

Рис.1

Положение геометрического объекта в пространстве Л2 определяется тремя параметрами (рис. 2):

А у' ^ Л Ч ®

-5»

X

Рис.2

У А А X, У - координаты полюса,

& - угол поворота объекта относительно оси абсцисс области размещения. Геометрические

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

Необходимо разместить т объектов в области £2 пространства Я2 так, чтобы минимизировать функцию 2г, ..., 2„} при выполнении следующих условий:

т, г2.....гу >= о, ]■ = л 2, ...„ К

где 2, = {Х„ У,, &,} - вектор параметров размещения ¡' - го объекта,

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

/■ - ограничения на параметры размещения, включающие условия

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

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

Теория оптимального раскроя была основана в 50-х годах Л.В.Канторовичем и В.А. Залгаллером. Дальнейшее развитие в России она получила в работах И.В. Романовского, Э.А. Мухачевой и Л.Б. Беляковой.

Теоретические основы расчета упаковки геометрических объектов были разработаны в харьковской школе под руководством Ю.Г. Стояна. Большинство численных методов, применяемых для решения исследуемой задачи в настоящее время, основаны на разработанном в этой школе принципе последовательно-одиночного размещения (ПОР), при котором все заготовки размещаются последовательно одна за другой и ранее размещенные заготовки считаются неподвижными. Методы, основанные на принципе ПОР, отличаются способами моделирования движения заготовок в раскройной области и определения порядка заготовок при размещении. Среди последних наиболее известны эвристический прием первоочередного размещения более крупных по площади заготовок и метод асимптотического перебора локальных экстремумов. Большинство методов моделирования движения геометрических объектов основаны на вычислении годографа функций плотного размещения.

Другой класс методов для рациональной упаковки 2-мерных геометрических объектов основан на безусловной оптимизации (Г. А. Иванов). Базовым методом в этом классе является метод штрафных функций.

Аппроксимационный подход предложен и развит в работах

A.И.Липовецкого и М.Н. Корницкой.

Среди зарубежных работ следует отметить эксперименты с методом "Simulated Annealing" ("Смоделированный отжиг"). Метод моделирует физические процессы охлаждения твердого тела.

Исследованием задачи упаковки геометрических объектов занимаются также М.А. Верхотуров, В.В. Мартынов, А. А. Петунии (Россия),

B.Миленковик, К. Даниэльс, Ж. Ли (США), К. и У. Доусланд (Великобритания), Т. Ленгауэр, Р. Хекманн (ФРГ) и др.

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

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

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

При решении задачи упаковки плоских геометрических объектов в общем случае возникают 3 подзадачи :

- описание геометрических форм заготовок и раскройной области;

- моделирование плотного движения геометрических объектов в раскройной области с целью определения для них рационального положения;

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

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

О

Кусочно-линейная я, аппроксимация

1

Целочисленная >

аппроксимация 1

V

многоугольника

> |

1

Г

• Аппроксимация целочисленного многоугольника последовательностью цепных кодов

1

=3! -

? а га

V к!

г к

\ 1 \г

■ г £ 1

>- / * > 4 *

* С 1 4

восьмисвязная область четырехсвязная область

Рис.3

В итоге контур геометрического объекта описывается последовательностью цепных кодов. Цепной код - это число, характеризующее направление вектора. Направлений может быть 8 (рис .4а) или 4 (рис.4б) для восьми- и четырехсвязной 'областей соответственно. В 'диссертации использована четырехсвязная область.

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

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

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

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

Рассмотрим постановку задачи планирования раскроя : Задача ПР. Требуется найти совокупность раскроев г;, г2,...,гр...,г„ , их количество п и вектор интенсивностей их применения х = (х/ ,х2 ,...,х„ ), удовлетворяющих условиям х, >0,]= 77г; (1)

^х,а(г{) = Р (2)

и обеспечивающих минимум функции

<"(*>> = 2>у. (3)

где Р = ,...,6^) - вектор, характеризующий требуемое число заготовок каждого вида,

а ~ (ач - вектор, характеризующий раскрой,

а у - количество заготовок 1 -го вида в раскрое ].

Раскройный план определяется набором некоторых раскроев (векторов) а(г, ). а (г2 ),...,а (г„), а также вектором х = (х/ ,хг ,...,х} ,...,х„ ), где х} -интенсивность применения у -го раскроя. Раскройный план называется допустимым, если он удовлетворяет условиям (1), (2), а допустимый план, минимизирующий функцию (3) - оптимальным.

Задача ПР является достаточно общей и не зависит явно от конфигурации заготовок. Она является задачей ЛП с неявно заданными векторами, характеризующими раскрой. Из общей теории ЛП вытекает следующий признак оптимальности :

Теорема. Для оптимальности допустимого плана, удовлетворяющего условиям (1), (2), необходимо и достаточно существования т -мерного вектора

У ~ (уI ,У2 , -;Ут), (4)

удовлетворяющего условиям

(а(^,у)<1, } = Тп\ (5)

(а (г^, у) = 1, если Xj> 0. (б)

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

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

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

оптимальный план. Такой процесс реализует численный метод ЛП - метод последовательного улучшения. Общая схема метода следующая :

1. Составляется некоторый план.

2. Находятся оценки из условия равенства сумм оценок в примененных

раскроях.

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

4. Если найден раскрой, лучший чем использованные ранее, то

определяется какой из раскроев следует им заменить.

5. Составляется улучшенный раскройный план, и действия повторяются.

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

В классе задач раскроя-упаковки принципиально различаются задачи массового и единичного производства. Описанная выше задача ПР является моделью массового производства. Для задач единичного производства вводится дополнительное ограничение на целочисленность компонентов вектора л. В этом случае для использования метода последовательного улучшения можно воспользоваться физическим смыслом оценок. А именно, на основе некоторого допустимого раскройного плана для каждой заготовки предлагается рассчитывать нормы расхода материала и принимать их в качестве "псевдо"-оценок. Роль "псевдо"-оценок аналогична роли двойственных переменных в задачах ЛП : с их помощью допустимый план раскроя проверяется на оптимальность и генерируются новые способы раскроя. Предложенный метод представляет собой итерационный процесс, на каждом шаге которого "псевдо"-оценки пересчитываются и отвечают новому раскройному плану. Оценки позволяют определить порядок перебора комбинаций заготовок; перебор осуществляется согласно приоритетному списку, в котором заготовки ранжированы по убыванию удельных оценок у,*=у,- / г, . При генерировании карты раскроя пытаются найти раскрой с достаточно большой суммарной оценкой. Этот метод был разработан в школе профессора Э.А. Мухачевой и использован для оптимизации гильотинного раскроя (Т.Д. Тарасова, Л.Ф. Розанова). В 9 случаях из 10 он позволяет получить оптимальное решение.

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

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

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

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

Рис.5

Пусть дана произвольная упаковка Р с длиной Ь=ЦР) (рис.5). Эта упаковка содержит определенное число п незаполненных областей Я;,#2,.,.,Я„ (Если п -О, то упаковка - безотходная). Обозначим через ак и ди соответственно площадь и,периметр области к, Ъ =1Для упрощения будем рассматривать край. раскраиваемого листа (полосы) как уже размещенную заготовку с индексом 0- Пусть Л с/и.{0} -.множество заготовок, определяющих область к, а 1,), - часть периметра области Ъ, которая принадлежит 1-му объекту, 1 б Д. Тогда "псевдо"-оценка уь ¿е./, определяется согласно следующей формуле :

= (7)

Вторая формула является модификацией первой :

Ьш/

Ян

- + 0,, ¿е/и{0}

(8)

Для расчета "псевдо"-оценок по третьей формуле сначала определяется а,

величина а,к

Р,

которая имеет смысл части площади геометрического

объекта, пропорциональной: величине /« (р, - периметр фигуры /). .Формула для расчета "псевдо'-оценки ■

= 1*1

I еЮ{0}

(9)

Рассмотрим теперь процедуру определения очередной размещаемой заготовки. Пусть дана частичная упаковка Р(1р) объектов множества /0' (рис.6). Будем считать, что положение в раскройной области каждого размещаемого объекта 1е I \10 (координаты полюса X, Г) с фиксированным углом поворота 61

однозначно определяется процедурой моделирования плотного движения. Для объектов фиксировано число и> допустимых поворотов, кратных величине А <9: 0о = О, <9, = Д<9, <92 = 2Л6>,...,0*./=36Оо-Д6>, . ,

- ~7

2 У

V /н,

4

1 н2

\ 3 Е,

Рис.6

При размещении объекта ie I 110 возникает пи новых незаполненных областей Hh и пЕ краев Ее, которыми объект i касается упакованной части полосы. На рис.6 щ = пЕ = 2. Пусть IH (h) с J0 и {¡,0} - множество объектов, определяющих область h е {1,...,пц } и 1Е(е) с 1„ и {¿,0} - пара объектов, определяющих край ее{1,...,пЕ}. Тогда для того чтобы определить очередную размещаемую заготовку, для всех неразмещенных заготовок iel\l0i.c фиксированным углом поворота <9ь k=0,...,w-l, вычисляется величина:

H'IJeIH{k) Pj , t=lJeIEW Pj h*' где le - длина края е.

Для очередного размещения выбирается заготовка л' с углом 0' , которым отвечает максимальная величина v, (0к).

Vi третьей главе описаны алгоритмы моделирования движения геометрических объектов на основе дискретно-логического представления информации, а также некоторые другие алгоритмы • моделирования геометрических преобразований (алгоритмы поворота объекта; вставки объекта в область, удаления из области и т.д.), разработана схема оптимизации с использованием "псевдо"-оценок, предложена серия эвристических алгоритмов на базе метода оценок.

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

Пусть

сI - направление сдвига :

- [4- для4-связнойобласти

а — \,п , где п = -

[8-для 8-связной

Сначала находим первоначальные положение объекта на листе и направление сдвига.

Пусть выполнен (к-1) -й шаг алгоритма. Для выполнения к-го шага используются следующие процедуры :

1. Сдвиг объекта по коду и вычисление нового положения.

2. Проверка на окончание движения объекта в области.

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

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

4. Выбор первого возможного направления сдЕига.

Алгоритм "правой руки" используется для моделирования движения каждого отдельного геометрического объекта с конкретным углом поворота. Реализована возможность поворачивать геометрический объект на 90° , т.е. всего рассматриваются 4 возможные ориентации объекта. Из всех возможных положений объекта выбирают такое, которое отвечает локальному критерию оптимальности. За локальный критерий оптимальности был принят минимум абсциссы полюса заготовки (рис.7).

пнп

Рис. 7

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

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

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

Алгоритм оценок осуществляет итеративный поиск рациональной упаковки:

Алгоритм оценок ШагО. Генерация начальной раскройной карты Р\. (Метод ППУ).

k:=\,L'-L(P¡). Шаг 1. Анализ полученной карты раскроя. Шаг 2. П одсчет оценок v,, i е I (7) - (9). Шаг 3. Генерация текущей раскройной карты P^¡. (Алгоритм

упаковки). Шаг 4. k:-k+l.

if L(Pi)<L' then P* - лучшее решение, L*:-L(Pi,). Goto 1. Для генерирования начальной раскройной карты используется эвристика "первый-подходягций с упорядочиванием". Алгоритм упаковки генерирует очередную карту раскроя на основе подсчитанных оценок заготовок :

Алгоритм упаковки 1={1,...,т} - множество заготовок, 10с! • множество размещенных заготовок. Шаг О.1п:=0. Шаг 1. if Iq~1 - stop. Шаг 2. while 1\1ОФ0 do for k :=0 to 3 do begin

Моделирование плотного движения i -й заготовки (алгоритм "правой руки") и определение для нее рационального положения. Вычислить v,(&k) по формуле (10). if v«T < v,(0J then = v,(0k); Г:=»; 6>':= end

ШагЗ. Вставить заготовку i' с углом 0' в область размещения. Шаг 4. h:=Inuf /7. vmax = - оо. Goto 1.

Возможный вариант алгоритма упаковки - это Алгоритм упаковки с возвратом: '

5 ' Алгоритм упаковки с возвратом

Шаг 0. !(,: --'0. ' Шаг \ . \iln-l- stop. " "

Шаг 2. while существует неиспользованная заготовка в I \In do ' begin ' " """

for k :=0 to 3 do begin

Моделирование плотного движения i -й заготовки (алгоритм '"пр^й руки^'и определение для 8'ее рационального положения. ' 'Вставить заготовку/ в область размещения. '

' ' Вычислить v/0J (10). I0:=IoU{ i).

Для всехj еД 10 ик=0,3подсчитать v'j(0k)ц v"j(©k) соответственно в позициях начала и конца вставки заготовки i Vt(0k) + :тах J max__J^(&J} ■

JU\l0,k=0,3 ... - ¡е1М0,ые.! ■

Удалить заготовку / из области. lo~h\{i}-_ _ ' '

if < v,(0k) then »„ /= Vi(0k)-,i': =i; &':= &k\ end

end

Шаг 3. Вставить заготовку' с углом &' в область размещения. Шаг 4. In:=InUf ¡n,'. vmax = - со. Goto 1.

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

Обозначим каждый вариант последовательностью символов : a/b/c/d/e , где а, Ь, с, d,е - множества эвристик :

1 )ае{1,2,3}- множество формул для подсчета оценок (7)-(9). 2) При определении очередной размещаемой заготовки (Алгоритм упаковки), оценки ее положения кажется целесообразным ограничить часть периметра заготовки, которая является внешней относительно упакованной части (рис.8 - пунктирная часть). Практические исследования показали, что внешняя часть периметра должна быть по крайней мере меньше, чем 4/5. Множество Ь содержит два элемента : с ограничением на внешнюю часть периметра (wL) и без ограничения (oL): be{wL,oL}.

^ = / Y 4

1 \ — 3

Рис.8

3) ce{d,a} : ' ' ,."

d - одинаковые заготовки рассматриваются как разные (имеют разные оценки);

а - для одинаковых заготовок находится средняя оценка.

4 )de{la,2a}:

la- алгоритм упаковки ;

2а - алгоритм упаковки с возвратом .

5) Элементы множества dе{А,тА} соответствуют алгоритмам моделирования плотного движения. Второй алгоритм является модификацией для размещения заготовок во внутренних незамкнутых областях.

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

Из 48 возможных вариантов метода оценок для исследования было выбрано и реализовано 30 наиболее перспективных. Для оценки эффективности использовались 35 примеров задач раскроя из литературы и практики. Алгоритмы метода оценок сравнивались друг с другом и с двумя дополнительно реализованными алгоритмами : алгоритмом случайного поиска (HI) и алгоритмом оценок с жестко зафиксированным приоритетным списком (Н2). Исследования проволочись на персональном компьютере IBM PC Pentium, 90 MHz. Результаты были получены : после 100 итераций - для алгоритмов HI и Н2; после 40 итераций - для алгоритмов */*/*/1а/*; после 20 итераций - для алгоритмов */*/*/2а/*. Для сравнения вариантов использовалась таблица следующего вида :

Таблица 1

Var.l Var.2 Var.3 •••

Var.l X tl2 t|3

Var.2 ■ t2i X t23

Var.3 tji t32 X

...

число в таблице 1 (у - это число примеров (из 35), для которых вариант i не хуже, чем вариант].

По результатам эксперимента лучшими вариантами метода оценок

оказались следующие:

}/*/*/*/*■

ЗМЬ/*/1а/тЛ;

3/о1У*/2а/*.

Не было практически ни одного случая, когда метод оценок не мог улучшить первоначально сгенерированную с помощью метода ППУ раскройную карту.

При сравнении 30 алгоритмов оценок с алгоритмами Н1 и Н2 из таблицы 1 были получены следующие результаты : в 85% примеров метод оценок дает лучшее решение по сравнению с алгоритмом Н1 и в 78 % - по сравнению с алгоритмом Н2. Для 12 наиболее эффективных алгоритмов оценок результаты следующие : метод оценок дает лучшее решение по сравнению с алгоритмом Н1 в 93% случаев и по сравнению с алгоритмом Н2 - в 89 %.

Таблица 2

Tmin на 1 It Тт„ на 1 It Т£р на 1 It fbest

(сек.) (сек.) (сек.) (сек.)

Алгоритмы

"нижний -левый

угол" 1 17 4 430

(100 Итераций)

*/*/*/1а/А 3 200 40 300

*/*/*/2а/тА 6 3200 400 1000

Временные характеристики алгоритмов представлены в Таблице 2. Предложенные алгоритмы программно реализованы на языке С с использованием объектно-ориентированного подхода к программированию.

Базовыми абстрактными типами (классами) пакета программ являются : классы Точка (Р), Фигура (F), Матрица_области(А) и Карта_раскроя (Card).

Разработанное ПО может быть использовано, как автономно, так и в составе программного комплекса "CUT-CAD".

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Исследован подход к решению задачи упаковки плоских геометрических объектов на базе основного понятия ЛП - оценок (двойственных переменных), предложены формулы подсчета оценок для геометрических объектов произвольной конфигурации.

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

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

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

5. Получены результаты, характеризующие поведение метода оценок.

6. Разработано программное обеспечение расчета упаковки плоских геометрических объектов.

Выражаю глубокую благодарность доценту кафедры ВМиК УГАТУ Верхотурову М.А. за консультации и внимание к моей работе.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Сергеева О. Ю. Метод последовательного уточнения оценок для оптимизации нерегулярной укладки геометрических объектов //Технология и оборудование современного машиностроения : Тез. докл. Всероссийской молодежной научно-технической конференции. - Уфа : УГАТУ, 1994. - с. 81.

2. Верхотурова Г. Н., Сергеева О. Ю. Применение оценок в задачах оптимальной упаковки сложных объектов // Математическое моделирование в решении научных и технических задач : Сборник статей. - Уфа : Издательство научно-производственной фирмы "Технология", 1994. - с. 13-16.

3. Верхотуров М. А., Сергеева О. Ю. Применение метода оценок для решения некоторых задач нелинейного программирования // Математическое программирование и приложения : Тез. докл. Всероссийской конференции. -Екатеринбург, 1995. - с. 59.

4. Сергеева О. Ю. Метод оценок для решения задач плотной упаковки объектов произвольной формы // Ленинские горы-95 : Тез. докл. Международной конференции студентов и аспирантов по фундаментальным наукам. - Москва : МГУ, 1995,- с. 23.

5. Верхотуров М. А., Верхотурова Г. Н., Сергеева О. Ю. О решении некоторых прикладных задач нелинейного программирования // Методы оптимизации и их приложения: Тез. докл. 10-й Байкальской школы-семинара. -Иркутск, 1995. - с.45-46.

6. Мухачева Э.А., Сергеева О. Ю., Шабрина Л. И. Теория и методы расчета прямоугольной упаковки // Рук. деп. В ВИНИТИ № 863-В96 от 19.03.96. 25 с.

7. Верхотуров М.А., Сергеева О.Ю. Некоторые особенности реализации упаковки геометрических объектов на базе цепного кодирования // Принятие решений в условиях неопределенности : Межвузовский сборник. - Уфа : УГАТУ, 1996,- с.70-78.

Сергеева Оксана Юрьевна

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

05.13.16- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат

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

ЛБ № 0192 от 16.10.96

Подписано к печати 9.12.97. Формат 60*84/16. Бумага писчая № 1. Печать плоская. Усл. печ.л. 1,0. Уч.-изд.л. 0,9. Тираж 100 экз. Заказ Уфимский государственный авиационный технический университет Уфимская типография № 2 Министерства печати и массовой информации Республики Башкортостан

450000, Уфа-центр, ул. К.Маркса, 12.