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

РГВ ом 2 2 ДЕК 2190

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

ВАСИЛЬЕВА Лидия ИЛЬЯ СО В ПА

АЛГОРИТМЫ УПАКОВКИ й-МЕРНЫХ ГОФРОВ НА БАЗЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

УФА 2000

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

Научный руководитель -Официальные оппоненты:

Ведущая организация -

доктор технических наук, профессор Мухачева Э.А.

доктор технических наук, доцент Мартынов В.В.; кандидат технических наук, доцент Григорчук Т.И.

ИМ с ВЦ УфНЦ РАН

# а>

Защита состоится «¿2» ^ееаЗ2000 г. в № часов на заседании Диссертационного Совета К-063.17.01 при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К.Маркса, 12.

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

Автореферат разослан «Н,кал^Л-гт \

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

Л.М. Бакусов

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

М

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

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

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

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

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

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

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

а) б) с)

Рис. 1. Двумерные гофры.

Диссертационная работа посвяшена разработке и исследованию математи-| ческих моделей и алгоритмов решения и-мерной задачи раскроя-упаковки гоф-; ров в условиях массового производства.

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

Для этого были поставлены и решены следующие задачи: I 1. Разработка математических моделей задачи планирования п-мерных упако-' вок гофров и задачи генерации способа упаковки;

2. Представление гофра в виде совокупности блок-структур по каждой координатной оси и сведение задачи упаковки гофра к решению п задач размещения его блок-структур;

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

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

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

2. Представление задачи упаковки гофров в условиях массового производства

в виде задачи линейного программирования;

3. Представление гофра в виде совокупности п блок-структур;

4. Алгоритм случайной выборки для генерации допустимого способа упаковки,

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

5. Алгоритм расчета плана задачи, основанный на симплекс-методе с предвари-

тельно сгенерированной матрицей ограничений, и его программная реализация;

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

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

• Обобщен класс многоугольников-гофров; предложено представление гофра в виде совокупности блок-структур, исследованы возможности покоординатной укладки гофров путем размещения блок-структур;

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

• Предложенные алгоритмы решения поставленной проблемы разработаны и реализованы для решения и-мерной задачи Р-У гофров.

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

Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались: на международной молодежной научно-технической конференции «Интеллектуальные системы управления и обработки информации» (1999г., г. Уфа); на Республиканской научно-технической конференции «Интеллектуальное управление в сложных системах-99» (1999г., г. Уфа); на V международной научной конференции «Методы кибернетики химико-технологических процессов» (1999г., г. Уфа); на конференции «Математическое программирование и приложения» (1999 г., г. Екатеринбург); на международной научной конференции «Моделирование, вычисления, проектирование в

условиях неопределенности-2000» (г. Уфа, 2000г.); на международной конференции «Распределительные системы: оптимизация и приложения в экономике и науках об окружающей среде» (2000г., г. Екатеринбург); на международной конференции «Дискретный анализ и исследование операций» (2000г., г. Новосибирск); на международной конференции INFORMS (San Antonio, 2000г.). Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы и приложений. Общий объем работы - 119 с. и два приложения. Библиография включает 97 наименований.

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

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

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

В основу классификации моделей положены известные работы Л.В.Канторовича и В.А.Залгаллера, Э.А.Мухачевой, И.Терно и Х.Дикхофа.

Во второй главе изложен анализ постановки и методов решения задачи

I

\1 упаковки гофров с позиций общей теории проблемы оптимального размещения геометрических объектов (ГО).

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

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

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

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

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

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

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

Задача л-мерной упаковки гофров заключается в следующем: имеются т видов и-мерных гофров заданной комплектности bj,i~\,...,m, и конгруэнтные л-мерные прямоугольные объекты, однонаправленные с гофрами; требуется

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

Гофр задается параметрами каждого входящего /7-мерного параллелепипеда, а именно: размерами по каждому направлению и координатами их начальной точки (относительно начальной точки гофра).

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

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

1) грани гофра параллельны граням объекта;

2) взаимное непересечение размещенных в объекте гофров;

3) непересечение гофра с границами объекта.

План рассматриваемой задачи упаковки представляет собой совокупность карт (способов) упаковки с указанием интенсивностей их применения. Каждая упаковка г характеризуется вектором аг -(ап,аГ2,—,вГт), компоненты

ап которого указывают количество гофров /-го типа (/'=!,.получаемых по карте г.

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

Для применения методов ЛП при решении данной задачи основной проблемой является нахождение множества векторов ^а(г^), * = характеризующих карту Р-У и определяющих матрицу ограничений.

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

Пусть задано множество заготовок Р, их требуемое количество Б = Кроме того, пусть сгенерировано некоторое множество карт

упаковок {«(г,),г =!,...,£), (к<Ь, А- число всевозможных карт Р-У). Тогда за-

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

1. к -количество сгенерированных карт упаковок;

2. |агГ( =(ап1,аГ12,-,аГ(т ), / = ] - векторы, характеризующие карты Р-У;

3. вектор 5 = -заданные комплектности заготовок.

Требуется найти совокупность реализуемых упаковок г^го,...,^ и вектор интенсивностей их применения х - ,х2 ,.,.,хк ), удовлетворяющие следующим условиям:

х, >0,* = 1,...,&; (1)

к Т

¿1х,ап=Б = (ЬиЬ2,...,Ьт)-; (2)

(=1

к

/¿(г,*) = 2>,->тш. (3)

1=1

Целевая функция (3) имеет смысл суммарного количества объектов, затраченных в процессе упаковки комплекта Р,В. Условия (1), (2) являются условиями реализуемости плана раскроя-упаковки: условие (1) соответствует требованию неотрицательности переменных х,, I = \,...,к, а условие (2) - выполнение плана по заданным комплектностям заготовок.

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

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

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

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

Математическую модель задачи генерации способа упаковки можно сформулировать следующим образом: Дано:

1. Натуральное число п> 2; (мерность задачи)

2. Натуральное число /(? е {1,...,£}) - номер рассматриваемой последовательности заготовок и / с {1,...,/«} - множество номеров гофров, входящих в / -ю последовательность;

3. Набор заготовок, представленных в виде векторов:

={р'и,р'25,...,р'т),(х1ъ,х'2*,.~,х'п*)\1е1, /с{!,...,«},^ = 1,я,, где gi-количество п -мерных прямоугольников в г -ом гофре.

4. Вектор $ = (<?},#2,- размеры объекта размещения;

Требуется найти вектор аг< -(аГ/ 1гаг 2,—?аг,т)> характеризующий упаковку ги совокупность векторов 0 = |э' :(г{,г2,...,г^)| - координаты начальной точки 1 -го гофра в объекте, (г е I), удовлетворяющие условиям размещения, при которых суммарная мера размещенных гофров максимальна.

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

Пусть теперь /-номер рассматриваемой последовательности заготовок (I е {!,...,£}). Генерация способа размещения гофров, входящих в рассматриваемую последовательность, включает два этапа: на первом происходит подго-

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

Представление гофра в виде совокупности блок-структур. Подготовка гофра к размещению подразумевает сопоставление ему п последовательностей блоков (назовем их блок-структурами) по каждой координатной оси.

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

У

Л-К

Т

I

.Г,

п ±.

Т"

?

1 I

т

I I

I . 1Г4

1 1 I

X,-

У>Уг

К' = У,+(Уз-У:)

Уг

7Г

у/

/

г

у; =х4

V у = *1 +(*4 ~Х3)

VI

а)

у:

У, У 2 б)

У

Рис. 3.1. Представление двумерного гофра в виде двух блок-структур: а) по оси Ох; б) по оси Оу.

О

ляющего гофр п -мерного прямоугольного параллелепипеда, проводятся сече-

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

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

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

Для решения у - ой задачи размещения блок-структур определена операция их сложения как сложение ширины блоков на каждом участке у - й координатной оси (у = 1,я). Первый блок размещаемой блок-структуры по у'-му направлению может бить расположен либо с координаты, определяющей "начало" координатной оси по данному направлению, либо с координаты, соответствующей началу или концу блока уже расположенной блок-структуры. Результатом сложения двух блок-структур является блок-структура.

Условия получения допустимого размещения гофров учитываются на этапе размещения блок-структур; справедливы следующие утверждения:

Утверждение 1. Для того, чтобы размещение гофра в объекте было допустимым, необходимо выполнение условий:

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

2) ширина блока результирующей блок-структуры по } -му направленгао при добавлении блок-структуры очередного гофра не должна превышать предел по данному направлению.

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

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

Проверка достаточного условия допустимости размещения следует из условий непересечения каждых двух «-мерных прямоугольных параллелепипедов, составляющих размещаемые гофры. Пусть - координаты начальной точки ¡'-го и-мерного прямоугольного параллелепипеда в объекте, а (р\,р2,.-.,р'.;) - его размеры, / = 1,2. Тогда непересечение двух п-мерных прямоугольных параллелепипедов в пространстве означает выполнение хотя бы одного из условий: хУ>х^ + р] или х^ >.*'. + р\, у = 1 ,п.

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

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

1) подготовительный шаг: представление каждого гофра в виде совокупности блок-структур, построенных по каждому направлению;

2) размещение г-го из последовательности гофра {/ е Г): решение п задач размещения его блок-структур с проверкой необходимых условий допустимости; (при нарушении необходимых условий ищется новое размещение блок-структуры);

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

4) если найдено допустимое размещение, формируется вектор, характеризующий полученную карту упаковки.

Приведены пошаговые алгоритмы решения задач генерации и планирования упаковок гофров.

Генерация карты Р-У осуществляется с помощью алгоритма Оеп_каЛ, представляющего собой реализацию АСВ. Пусть - блок-структура по /-му

направлению для ¿-го типа гофров (у = 1,...,//,/ = \,...,т); ¿^-значение предела при укладке блок-структур по направлению ], 0 =1,...,л), величина Qj указывает параметры результирующей блок-структуры по соответствующему направлению, функция SumIXQj,Gplj,Lj) определяет, выполнено ли правило укладки блок-структуры с пределом Ху. Тогда алгоритм генерации карты упаковки выглядит следующим образом:

Алгоритм генерации карты упаковки (ОепкаП) Шаг 0. Строится - блок-структура по } -му направлению для / -го типа гофров (у =1, ...,п,1 = ],...,/»);

¿7 = ~ - определение значений пределов;

1=1..п.у

Шаг 1. Строится последовательность из номеров гофров Р = {РъР2,...,Ркт).

Р5 е {!,...,/»}, где кт - количество гофров в последовательности. 5:= 1.

Шаг 2. <2} = ЗитЦО^Ср^,^), / = 1,.. , п. Если размещение не удалось, то Шаг 5.

Шаг 3. Определение координат начальной точки Р5 -го гофра и проверка на допустимость размещения. Если размещение недопустимо, то Шаг 2. Шаг 4. аг ~аг + } - формирование вектора карты упаковки. Шаг 5. Если в<кт, то х := л +1 и Шаг 2. Шаг.6. Конец.

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

Алгоритм расчета плана упаковки гофров Шаг 1. Задается количество генерируемых карт упаковки к. Шаг 2. Генерируются карты упаковки \хг. | ] = 1 ,...,к по алгоритму Сеп_ка11.

Шаг 3. Решается задача ЛП на множестве векторов . | у = 1 ,...,к и определяется, какие из данных карт войдут в план упаковки, и интенсивности их применения.

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

Л»-' Л к2

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

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

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

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

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

Основные результаты работы:

1. Обобщено введенное ранее понятие «гофр»; в поставленной задаче Р-У в качестве заготовок рассмотрены п -мерные гофры (л -мерность задачи).

2. Разработана математическая модель задачи упаковки и-мерных гофров (п>2) внутри и-мерных прямоугольных объектов: поставленная проблема описана непрерывной моделью линейного программирования.

3. Введено понятие «блок-структура» и предложено представление каждого гофра в виде совокупности блок-структур.

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

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

6. Показано сведение задачи упаковки п -мерного гофра в объект к решению п задач размещения блок-структур гофра.

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

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

9. Разработанные алгоритмы программно реализованы. Проведены численные эксперименты, подтверждающие перспективность данного подхода.

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

1. Картак В.М., Васильева Л.И. Точный метод для решения задачи упаковки п-мерных прямоугольных объектов // Информационный бюллетень N8. Конференция Математическое программирование и приложения. -Екатеринбург, 1999. -С. 145.

2. Васильева Л.И., Карамова Л.М., Никульшина Л.М. Задача планирования раскроя в мебельном производстве. // Информационный бюллетень N8. Конференция Математическое программирование и приложения. -Екатеринбург, 1999.-С.59.

3. Васильева Л.И., Карамова Л.М. Свойства ПШР и МПШР для задачи рационального раскроя. // Принятие решений в условиях неопределенности. Межвузовский научный сборник. -Уфа: УГАТУ, 1999. -С. 331-339.

4. Картак В.М., Васильева Л.И. Модели и методы оптимизации упаковки Триерных параллелепипедов. // Деп. в ВИНИТИ. №58-В99 от 14.01.1999.-14 с.

5. Васильева Л.И., Картак В.М., Костригин Е.В. Гибридный алгоритм для поиска оптимального решения в двумерной задаче прямоугольной упаковки. // Республиканская научно-техническая конференция. Интеллектуальное управление о сложных системах-99. -Уфа: УГАТУ, 1999. -С.31-33.

6. Васильева Л.И. Сочетание точного и эвристического методов для нахождения оптимального решения в задаче распределения двухмерного ресурса. // Международная молодежная научно-техническая конференция. Интеллек-туачьные системы управления и обработки информации. —Уфа: УГАТУД999. -С.99.

7. Vasilyeva L.I., Usmanova A.R. The one-dimensional cutting problem: exact and heuristic algorithms. //Problem of Technology Transfer. International Scientific-Technical Workship. Ufa: Patras, 1999.-P.214-216.

8. Васильева Л.И. Раскрой гофр в условиях единичного производства. //Вычислительная техника и новые информационные технологии. Межвузовский научный сборник. Выпуск третий. -Уфа: УГАТУ, 1999.-С. 69-75.

9. Картак В.М., Васильева Л.И. Задача двумерной упаковки гофров. // Принятие решений в условиях неопределенности. Межвузовский научный сборник. -Уфа: УГАТУ, 2000. -С. 108-112.

10. Васильева Л.И., Картак В.М. Двумерная упаковка гофров на листах в условиях непрерывного производства. // Научная конференция. Моделирование, вычисления, проектирование в условиях неопределенности.-Уфа: УГАТУ, 2000.-С. 403-407.

11. Мухачева Э.А., Картак В.М., Васильева Л.И. Задача планирования п-мерных упаковок гофров. //Международная конференция. Распределительные системы: оптимизация и приложения в экономике и науках об окружающей среде.-Екатеринбург: ИММ УрО РАН, 2000.-С. 152-156.

12. Л.И. Васильева, В.М. Картак. Эвристический алгоритм упаковки гофров на листах. // Международная сибирская конференция DAOR'2000. Дискретный анализ и исследование операций,- Новосибирск: изд-во Института математики, 2000. -С. 182.

13. Mukhacheva Е.А., Kartak V.M., Vasilyeva L.I. Exact Algorithms for Solving N-Dimensional Bin-Packing Problems. //Annual Meeting «Informs-2000». - San Antonio, 2000. -P. 38.

ВВЕДЕНИЕ.

Глава 1. Проблема раскроя-упаковки: многообразие задач и методов их решения.

1.1. Постановка задачи раскроя-упаковки.

1.2. Классификация задач раскроя-упаковки.

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

1.4. Задача прямоугольной упаковки.

1.4.1. Постановка задачи прямоугольной упаковки.

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

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

1.5. Задачи фигурного раскроя-упаковки.

1.6. Задачи трехмерной упаковки.

1.7. Постановка задачи исследования.

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

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

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

2.1.1 Основные понятия и постановка задачи.

2.1.2. Классификация методов решения.

2.2. Метод упаковки n-мерных параллелепипедов в полубесконечную область.

2.2.1. Постановка задачи.

2.2.2. Матричная интерпретация упаковки.

2.3. Задачи генерации и планирования раскроя-упаковки.

2.4. Приближенный метод решения задачи планирования п-мерных упаковок гофров.

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

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

3.1. Постановка задачи как задачи ЛП.

3.2. Математическая модель задачи планирования.

3.3. Генерация последовательностей из номеров гофров.

3.4. Алгоритм случайной выборки для генерации способа упаковки.

3.4.1. Математическая модель задачи генерации способа упаковки.

3.4.2. Размещение гофра в объекте.

3.4.2.1. Представление гофра в виде совокупности блок-структур

3.4.2.2. Операция сложения блок-структур.

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

3.4.2.4. Процедура уплотнения.

3.5. Алгоритмы решения.

3.7. Оценка сложности алгоритма генерации карты упаковки.

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

Глава 4. Программная реализация алгоритмов и численный эксперимент .88 4.1. Описание программного обеспечения.

4.1.1. Структура файлов.

4.1.2. Описание модулей программы.

4.2. Подготовка численного эксперимента.

4.3. Численный эксперимент.

4.3.1. Исходные данные эксперимента.

4.3.2. Численный эксперимент №1.

4.3.3. Численный эксперимент №2.

4.3.4. Численный эксперимент №3.

4.4. Развитие методов решения и другие постановки задачи упаковки гофров.

4.4.1. Генерация поворотов гофра.

4.4.2. Другие постановки задачи и развитие методов их решения.

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

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

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

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

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

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

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

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

Понятие «гофр» впервые было введено и рассмотрено Корницкой М.Н. и Липовецким А.И. [72]. В связи с трудностями, возникающими в процессе решения задач фигурного Р-У, ими был предложен подход, связанный с упрощением формы раскраиваемых заготовок путем их аппроксимации фигурами определенных классов и решением указанной задачи для этих классов фигур. Предложенный аппроксимационный подход был разработан для проектирования раскройных карт в единичном производстве путем обобщения эффективных алгоритмов негильотинного раскроя на подкласс л 12-фигур, названных гофрами. Гофром в [72] назван многоугольник, ребра которого можно разбить на две ветви, составленные из ступенчатых ломаных с координатами вершин, монотонно возрастающих по оси абсцисс и монотонно убывающих по оси ординат.

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

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

Рис. 1. Двумерные гофры.

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

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

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

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

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

2. Представление гофра в виде совокупности блок-структур по каждому направлению и сведение задачи упаковки гофра к решению п задач размещения его блок-структур;

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

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

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

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

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

• Предложенные алгоритмы решения разработаны и реализованы для решения п -мерной задачи Р-У гофров ( п > 2).

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

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

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

Работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований, проект 99-01-00937.

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

Основные результаты работы:

1. Обобщено введенное ранее понятие «гофр»; в поставленной задаче планирования упаковок в качестве заготовок рассмотрены «-мерные гофры (п-мерность задачи).

2. Разработана математическая модель задачи упаковки п -мерных гофров (п> 2) внутри п -мерных прямоугольных объектов: поставленная проблема описана непрерывной моделью линейного программирования.

3. Введено понятие «блок-структура» и предложено представление каждого гофра в виде совокупности блок-структур.

4. Определены правила размещения и операция сложения блок-структур; сформулированы необходимые и достаточные условия допустимости размещения.

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

6. Показано сведение задачи упаковки п -мерного гофра в объект к решению п задач размещения блок-структур гофра.

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

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

9. Разработанные алгоритмы программно реализованы. Проведены численные эксперименты, подтверждающие перспективность данного подхода.

ЗАКЛЮЧЕНИЕ

1. Aarts Е., Lenstra J.K. (eds.) Local search in combinatorial optimization. John Wiley & Sons Ltd, 1997. -315p.

2. Abdou, G., Yang, M. A Sistematic Approach for the Three-Dimensional Palletization Problem.//International Journal of Production Research, №10,1994.-P. 381-394.

3. Amaral C., Portugal. Automatic interactive program means for packing.//SICUP-Bulletin №12, November, 1992. -P.2-3.

4. Beasley J.E. An exact two-dimensional non-guillotine cutting tree search procedure. //Operational Research, 1985, vol.33. -P.49-64.

5. Blazewich J., Drozdowski M., Soniewicki В., Walkowiak R., Poland. Systems for figure cutting stock problem fulfillment and experimental comparison.//SICUP-Bulletin №5, November, 1990. -P.3.

6. Blazewich J., Walkowiak R., Poland. Parallel "search of prohibition for two dimensional cutting stock problem. //SICUP-Bulletin №12, November, 1994. -P.5.

7. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. //Annals of OR, №41(1-4), 1993. -P.313-325.

8. Brooks R. L., Smith С. А. В., Stone A. H., Tutte W. T. The dissection of rectangles into squares. //Duke Mathematical Journal, №7, 1940. -P.312-340.

9. Chen, C.S., Lee, S.M., Shen, Q. S. An Analitical Model for the Container Loading Problem.// International Transactions in Operational Research, Vol.80,1995. -P.68-76.

10. Dyckhoff H. A Typology of Cutting and Packing Problems. //European Journal of Operational Research, v.44, 1990. -P. 145-159.

11. Fabian C., Spinulescu E., Rumania. A non-guillotine cutting problem for defecting sheets.//SICUP-Bulletin №7, June, 1993. -P. 13.

12. Fernandes J.L., Bernardo J.C., Portugal. Geometric algorithms and heuristic methods for automatic packing of figures. //SICUP-Bulletin №9, January 1993. -P.20.

13. Fraser, H.J., George, J.A. Integrated Container Loading Software for Pulp and Paper Industry.//EJOR, №77, 1994. -P.466-474.

14. Freeman, H. and Shapira, R. Determining the minimum area encasing rectangle for an arbitrary closed curve. //Comm.ACM. №18(7), 1975. -P.409 - 413.

15. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry.//Annals of OR, №57, 1995. -P. 103133.

16. Galambus G., Van Vliet A. Louwer bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. //Computing vol. 52. -P. 281-297.

17. Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem. // International transactions in operational research, vol.4, № 5/6, 1997.-P. 401-418.

18. George, J.F., New Zealand A Method for Solving Container Packing for a Single Size of Box.//Journal of the Operational Research Soviety,Vol.43,№4,1992.-P.307-312.

19. Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions. //Oper. Res, №14,1966. -P.145-175.

20. Gilmore P.C., Gomory R. E. A linear programming approach to the cutting stock problem (Part I/II). //Oper. Res. №9. -P.849-859, and Oper. Res. №11, 1961/63. -P.863-888.

21. Gilmory P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions. //Oper.Res., №13, 1965. -P.94-120.

22. Haessler R.W., USA. Minimization of counts n-dimensional packing problem. //SICUP-Bulletin №9, January, 1993. -P.20.

23. Haessler, R.W. Cost Minimization of Multiple-Vehicle Shipment./SICUP-Bulletin №9, January 1993. -P.2-3.

24. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor. //The University of Michigan Press, 1975. -96p.

25. Ikonen I.T., Biles W.E. Three dimensional chromosomal representation for a genetic algorithm for packing non-convex parts in 3D. //Proceedings of the 3NWGA. Helsinki, Finland, 1997. -P. 101-119.

26. Ikonen I.T., Biles W.E., et al. Concept for a genetic algorithm for packing three dimensional objects of complex shape. //Proceedings of the first online workshop of soft computing, 1996. -P. 12-24.

27. Martello S., Vigo D., Exact solution of two-dimensional finite bin packing problem. //Management Science, vol. 35, 1997. -P. 68-74.

28. Medetz W., Austria. Package of programs for automatic figure packing. //SICUP-Bulletin №9, January 1993. -P.20.

29. Milencovic V.I., Daniels K., Li Z., USA. Allocation and compacting of non-convex polygons for easy industry. //SICUP-Bulletin №9, January 1993. -P. 15.

30. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.//ITOR special issue with papers from IFORS'96, 1996. -30p.

31. Mohanty, B.B., Mathur, K., Ivancic, N.J. Value Consideration in Three-Dimensional Packing A Heuristic Procedure Using the Fractional Knapsack Problem// EJOR, №74, 1994. -P.143-151.

32. Morabito R., Arenales M., Brazil. Application of AND/OR-graphs to Container Loading Problem. //SICUP-Bulletin №9, January, 1993. -P. 12.

33. Perry E.C., Landon M.D., Balling R.J. Spatial packaging of complex parametric solid objectives via optimization. // Engineering Design Methods Labs, Report 89-9. Bringham University, 1989. -51p.

34. Portmann, M.-C. An Efficient Algoritm for Container Loading.//Working Paper, 1990. -P.23-25.

35. Scheithauer G, Terno J. A heuristic approach for solving the multi-pallet packing problem. //Decision Making under Conditions of Uncertainty (Cutting -Packing Problems). The International Scientific Collection. Ufa, 1997. -P. 140155.

36. Scheithauer G., Germany. Algorithms for solving the Container Loading Problem. //SICUP-Bulletin №9, January, 1993. -P.8.

37. Scheithauer G., Terno J., Germany. Modeling of bin packing problems. //SICUP-Bulletin №9, January, 1993. -P.7.

38. Scheithauer,G. Algoritm for the Container Loading Problem.//Operations Research Proceedings, 1991, Springer-Verlag, Berlin/Heidelberg, 1992 (ISBN 3540-55410-6). -P.445-452.

39. Sha E.L. Area efficient and volume efficient algorithms for loading cargo, master's thesis (unpublished).// US Navy Post-Graduate School, 1970. -188p.

40. Simchi-Levi D. New worst-case results for the bin packing problem. //Naval Res. Log.Quart, vol.41, 1994. -P. 579-585.

41. Terno J., Lindeman R, Scheithauer G. Zuschnitprobleme und ihre prakti-sche Losung. //Leiprig, 1987. -P.207.

42. Tinarelli U., Addonizio M. Un problema di caricamento di containers. //Proc. AIRO congress, 1978. -P.79-91.

43. Udy J.L., Balling R.J., Benzley S.E., Landon M.D. Computation of interferences between three-dimensional objects and the optimal packing problem. // Advances in Engineering Software, Vol.10, №1, 1988. -P.8-14.

44. Valerio de Carvalho J.M., Rodrigues A.J.G., Portugal. Interactive computer's approach to a problem of two-stage cutting stock problem. //SICUP-Bulletin №9, November, 1992. -P.l.

45. Valeyeva A., Totskov I. Development of three-dimensional packing methods. //Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. -Ufa: USATU, 1997. -P. 198207.

46. Аккуратов Г.В., Березнев B.A., Брежнева O.A. О методе решения уравнения с булевыми переменными. //Принятие решений в условиях неопределенности: межвуз. научный сб. Уфа, 1990. -С. 145-146.

47. Белякова Л.Б. Об оптимальном раскрое листового материала. //В кн.: Автоматизация технологического проектирования при помощи ЭЦВМ. -М. : Машиностроение, 1968.-С.21-32.

48. Белякова Л.Б., Орехова О.М., Дмитриевская О.В. Алгоритм рационального раскроя полос на фигурные заготовки. //Труды ОНТИ ПТНИИ Волго-Вятского совнархоза, 1964. -С. 53-65.

49. Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя. //Математическое обеспечение рационального раскроя в системах автоматизированного проектирования. Тезисы докл. всесоюзной конференции.-Уфа, 1987.-С. 16-17.

50. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя//Труды междун. сибир. конф. по прикл. и индустр. математике. СО РАН, т.2, 1995. -С.47-57.

51. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.:Мир,1985. - 509с.

52. Гиль Н.И., Черноморец A.A. Метод построения поверхности 0- уровня Ф-функции. -Харьков, 1992.-29с.-(Препринт/АН Украины, Ин-т пробл. машиностроения: 359).

53. Данциг Д.Б. Линейное программирование, его применение и обобщение. -М.: Прогресс, 1966. -600 с.

54. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования. Автореферат диссертации на соискание ученой степени кандидата технических наук. Йошкар-Ола: МарПИ, 1993 .-16 с.

55. Канторович JI.В. Математические методы в организации и планировании производства. -Л.:ЛГУ,1939. -60 с.

56. Канторович Л.В. Методы рационального раскроя металла// Производственно технический бюллетень. -М., 1942. -35с.

57. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование. -М: Экономика, 1968. -96 с.

58. КантОрович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. -Новосибирск: Наука СО, 1971. -320с.

59. Картак В.М. Модели и методы оптимизации упаковки N-мерных параллелепипедов. //Диссертация на соискание ученой степени кандидата физико-математических наук. -Уфа, 1999г. -90с.

60. Картак В.М., Васильева Л.И. Модели и методы оптимизации упаковки N-мерных параллелепипедов. // Деп. в ВИНИТИ. №58-В99 от 14.01.1999-14с.

61. Кацев C.B. Об одном классе дискретных минимаксных задач. //Кибернетика, №3. -Киев, 1979. -С. 113-118.

62. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя. //Математическое обеспечение рационального раскроя в САПР. Материалы всесоюзной конференции. -Уфа, 1988. -С. 72-79.

63. Липовецкий А.И. К оптимизации свободного размещения прямоугольников. //Автоматизация проектирования в машиностроении. Минск: ИТК АН БССР, 1985.-С. 80-87.

64. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя. -Свердловск: Уро АН СССР, 1988. -50 с.

65. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования. Материалы Всесоюзной конференции 15-17 июня 1987. -Уфа: УАИД988. -159 с.

66. Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. // Рук. Деп. в ВИНИТИ, №53-В99 от 14.01.1999.-18 с.

67. Мухачева Э.А. Рациональный раскрой промышленных материалов: Применение АСУ. -М. Машиностроение, 1984. -176с.

68. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. //Информационные Технологии, N2, 2000. -С. 11-17.

69. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя упаковки геометрических объектов. -Уфа: УГАТУ, 1998. -217с.

70. Пономаренко Л.Д., Туранов И.Н. Оптимальная упаковка параллелепипедов: модель, метод и алгоритм. -Харьков, 1984. -51с. (депон. в ВИНИТИ, №4075-84).

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

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

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

74. Рвачев В.Л., Стоян Ю.Г. К вопросу об оптимальном раскрое материалов.// В кн.: Вопросы теоретической кибернетики. Киев: Изд. института кибернетики АН УССР, 1965. -С.30-42.

75. Рвачев В.Л., Стоян Ю.Г. К задаче об оптимальном размещении круговых выкроек. //Кибернетика, №4, 1965. -С .66-78.

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

77. Стоян Ю.Г., Новожилова М.В., Карташов A.B. Математическая модель и оптимизация линейных Ek(R ) задач размещения. -Харьков, 1991. -44 с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №353).

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

79. Томарченко Л.И. Опыт организации безостаткового раскроя. -М.: Легкая промышленность, №1, 1941. -С. 19-26.

80. Федоров Е.С. Начала учения о фигурах. -Записки Мин. Общества, 2-я серия, №21, 1885.-С. 1-289.

81. Федоров Е.С. Симметрия и структура кристаллов. -М.: Изд-во АН СССР, 1949.-154 с.

82. Шавырин Н.В. Раскрой ткани без остатка. -М.: Швейная промышленность, №2, 1940. -С.49-57.

83. Шехтман Л.И. Линейный алгоритм решения задачи регулярной трехмерной упаковки. //Принятие решений в условиях неопределенности. Межвузовский научный сборник. -Уфа: УГАТУ, 1996. -С.38-40.