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

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

Литература

1. Osherove R. The Art of Unit Testing with Examples in .NET. - Greenwich: Manning, 2009. - 324 c.

2. Meszaros G. xUnit Test Patterns. Refactoring Test Patterns. - Boston: Addison-Wesley, 2007. - 948 c.

3. СиманМ. Внедрение зависимостей в .NET. - Спб.: Питер, 2013. - 464 с.

4. ФаулерМ. Шаблоны корпоративных приложений. - М.: Вильямс, 2011. - 544 с.

5. Фаулер М. Рефакторинг. Улучшение существующего кода. - СПб.: Символ-плюс, 2010. - 432 с.

6. Бек К. Экстремальное программирование. Библиотека программиста. - СПб.: Питер, 2003. - 212 с.

7. Мартин Р.С. Принципы, паттерны и методики гибкой разработки на языке C#. - СПб.: Символ, 2012. - 768 с.

8. Приёмы объектно-ориентированного проектирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон и др. - СПб.: Питер, 2012. - 368 c.

9. Кожевников Д. О., Рудакова Г.М. Обобщение инфраструктурного дизайна корпоративных приложений на основе классов доменной модели на платформе .Net // Информатизация и связь. 2013. № 2. С. 31-35.

Actual problems of the organization of unit testing of classes.

Dmitry Olegovich Kozhevnikov, postgraduate

Siberian State Technological University, Chair of Informational Technologies

This work is devoted to description and the analysis of some problems of development of unit tests which are connected with shortcomings of a tested code. Distinguishing attainment suitability to unit testing and obtaining short and clear unit tests, the material of work concentrates on the description of design decisions which lead to emergence of unit tests bulky and difficult for reading. Symptoms and signs of such decisions in a tested code of the program are analyzed.

Key words: unit testing, refactoring, low coupling, dependency injection, test double, constructor, inversion of control container.

УДК 519.8

РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОГО РАСКРОЯ-УПАКОВКИ НА ОСНОВЕ КОНСТРУКТИВНЫХ И НЕЙРОСЕТЕВЫХ ПОДХОДОВ

Оксана Валерьевна Корчевская, к.т.н, доцент Тел 8 906 9713576,е-mail: okfait@gmail.com ФГБОУ ВПО «Сибирский государственный технологический университет»

www.kit-stu

Представлена постановка задачи п-мерной упаковки(п = 1, 2, 3). Приведено описание метода плоскостей для решения задачи трёхмерной упаковки. Приведена композиция этого метода для задачи двухмерной упаковки. Для определения нижних границ решения задач раскроя-упаковки применён аппарат нейронных сетей. Разработаны высокоэффективные алгоритмы решения задач двух и трёхмерного раскроя-упаковки, позволяющие быстро строить карты раскроя с коэффициентом раскроя, в среднем, от 85%. Достоверность полученных результатов диссертации подтверждается сравнительным анализом существующих подходов к решению поставленной задачи и результатами экспериментальных данных.

Ключевые слова: задачи раскроя упаковки, оптимизационные задачи, ЫР-трудные задачи комбинаторной оптимизации.

Введение

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

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

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

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

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

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

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

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

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

Постановка задачи п-мерной упаковки

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

<Ж, Ь, Н, к, и, М, w, I, И, т, Ь, 8, у, g, У>,

где W= (Wi, W2,..., Wk) - ширина,L= (Li, L2,..., Lk) - длина, H= (Hi, H2,..., Hk) - высота параллелепипедов; k - количество типов параллелепипедов; u = (u1, u2,..., uk) - количество параллелепипедов определённого вида; М = (М1, М2, ..., Mk) - предельно допустимая масса параллелепипедов; w = (w1, w2,..., wm) - ширина,/= (l1, l2,..., lm) - длина^ = (h1, h2,..., hm) - высота коробок;т - количество типов коробок^ = (b1, b2, ...,bm) -количество коробок определённого типа;е- признак направления: 8 = 1, если объекты можно поворачивать, 8 = 0 в противном случае; у - признак гильотинности: у= 1, если задачу решают с учётом признака гильотинности, и полагают равным 0 в противном случае; g = (g1, g2, ..., gm) - масса объектов; V- набор технологических ограничений;

k m

с = ^uk - общее количество параллелепипедов; n = ^ bi - общее количество коробок. j=1 i=1 Выходной информацией (в общем виде) является карта раскроя, представленная в виде следующего набора:

<П, X, Y, Z, Р, E>,

где П - преобразованный список коробок; Х = (х1, х2, ..., xn), Y= (y1, y2, ..., yn), Z= (z1, z2, ..., zn) - векторы минимальных координат коробок; Р - множество исходных параллелепипедов, в которые упакованы некоторые коробки; Е = (е1, е2,..., en) - признаки поворота, значение которых может принимать одно из 6 значений.

Зададим КРА - коэффициент раскроя (процентное отношение суммарного объёма всех упакованных коробок к занятому объёму параллелепипеда), а т - время решения задачи.

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

<ПД Y, Z, E> = fi

L^ min т ^ min

Необходимо найти такое отображение fi, которое преобразует входные данные в выходные, причём соблюдаются следующие условия:

• ортогональное размещение коробок в параллелепипеде;

• неперекрытие коробок между собой;

• неперекрытие коробками граней параллелепипедов.

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

Для задач сфиксированным сторонами параллелепипедов, необходимо найти их минимальное количество

<ПД Y, Z, Р, E> = fi

^min

i

КРА ^ 100% т ^ min

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

Метод плоскостей для решения трёхмерных задач раскроя-упаковки

Особенностями метода являются:

- непосредственное решение задач, а не сведение их к задачам меньшей размерности;

- использование как слойной, так и бесслойной стратегий;

- заполнение по, так называемым, приоритетным осям;

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

- допускается использование не одного, а нескольких параллелепипедов.

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

Для описания размеров пустых областей используются координаты: xj, yjt y2, zj, z2, а также флаг: 0 - область не заполнена; 1 - область полностью заполнена; -1 - игнорировать при заполнении данного слоя; -2 - игнорировать полностью. Запоминать значение координаты x2 не целесообразно, т.к. для случая слойной стратегии она определяется длиной слоя, для бес-слойной - это длина самого параллелепипеда.

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

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

- координаты коробок xh х2, yjt y2, zh z2относительно параллелепипеда;

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

- номер слоя, в котором размещена коробка.

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

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

• метод сортировки: без сортировки; по невозрастанию объема; по невозрастанию ширины; по невозрастанию массы; по невозрастанию удельного веса;

• шесть способов поворота коробок;

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

• использование как слойной, так и бесслойной стратегий.

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

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

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

Для оценки эффективности решения задач двух и трёхмерного ортогонального раскроя-упаковки методом плоскостей проведена серия расчётов на основе методики Г. Вешера и безотходных примеров E. Hopper.

За основу разбиения на различные классы предметов для задачи трёхмерной упаковки взято: нижнее ограничение длины предметов -vj; верхнее ограничение длины предметов v2 (v1 • W < li < v2 • W, i =1,..., n); нижнее ограничение ширины предметов wj

, верхнее ограничение ширины предметов w2 (w1 - W < wt < w2 - W, i=1,..., n); нижнее ограничение высоты предметов щ1, верхнее ограничение высоты предметов щ2 ( П - W <п, <П2 - W, i=1,..., n).

f У

у

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

Серия №1. Целью данного эксперимента была проверка необходимости включения в оптимизацию разбиение на слои для разных групп предметов. Выполнены численные эксперименты, параметрами которых являлись: высота параллелепипеда H = 150, его ширина W = 100; количество предметов n = 50, 100, 200, 250, 500, 1000. Предметы были отсортированы по классам: «мелкие» (v1, = 0.1, v2= 0.2; w1 = 0.1, w2 = 0.2; ц1 = 0.2, П2 = 0.25), «средние» (vi= 0.2, V2= 0.4; wi = 0.2, W2 = 0.4; ni = 0.2, П2 = 0.25) и «разнородные» (v1= 0.1, v2= 0.3; w1 = 0.1, w2 = 0.2; ц1 = 0.2, n2 = 0.25). Для каждого класса задач было сгенерированно по 10 тестовых примеров, усредненные значения коэффициентов раскроя приведены на рис. 2.

Таким образом, при тестировании метода плоскостей для задач трёхмерных упаковок на разной группе предметов было выявлена необходимость совместного использования как процедуры формирования слоя, так и бесслойной процедуры. Это позволяет формировать более плотную упаковку и, следовательно, повышает грузовую стабильность при решении реальных задач. Метод плоскостей показывает лучшие результаты при большом количестве и, в основном, «разнородных» предметов. Время решения задачи на ПК (Celeron (R) CPU 3.2 GHz, 1Гб ОЗУ) от нескольких секунд до двух минут (для n = 1000).

Серия №2. Выполнены численные эксперименты для анализа различных методов решения задач трёхмерной упаковки, параметрами которой являлись: длина параллелепипеда L =

150, его ширина W = 100; количество предметов n = 50, 100, 200, 250.

Предметы были отсортированы по классам: «мелкие» (v1, = 0.1, v2= 0.2; w1 = 0.1, w2 = 0.2; ц1 = 0.1, ц2 = 0.25), «средние» (v1= 0.2, v2= 0.1; w1 = 0.2, w2 = 0.25; щ = 0.2, n2 = 0.25) и «разнородные» (v1, = 0.1, v2= 0.25; w1 = 0.1, w2 = 0.2; ц1 = 0.2, n2 = 0.25).

Значения коэффициентов раскроя приведены в табл. 1.

Таблица 1

Значения коэффициентов раскроя для задач параллелепипедной упаковки при решении

различных классов задач

Методы Мелкие предметы, % Средние предметы, % Разнородные предметы, %

MBA - Метод на основе бесслойного алгоритма 77 79 80

EABD - «Наивный» эволюционный алгоритм 74 78 76

GABD - Классический генетический алгоритм 76 77 75

SABD - Метод случайных перестановок 73 74 76

Метод плоскостей 76 82 83

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

Серия № 3. Метод плоскостей для решения задач двухмерной упаковки был про-

90

80

75

11

В

50

100

200

1

250

500

И

1000

Мелкие

Мелкие

Средние

Средние

Разнородные

Разнородные

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

95

85

70

n

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

Таблица 2

Результаты решения безотходных задач E. Hopper серии N и С

Задачи n Среднее значение КРА, % Задачи n Среднее значение КРА, %

Опт. Изм. Опт. Изм.

N1a - N1e 17 100 92.6 С1 16,17 100 96.0

N2a - N2e 25 100 92.7 С2 25 100 95.4

N3a - N3e 29 100 94.1 С3 28,29 100 93.8

N4a - N4e 49 100 94.0 С4 49 100 95.2

N5a - N5e 73 100 94.9 С5 73 100 97.1

N6a - N6e 97 100 96.7 С6 97 100 96.8

N7a - N7e 197 100 97.0 С7 196,197 100 96.6

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

Серия № 4. Целью данного эксперимента было сравнение метода плоскостей с алгоритмом рандомизированного динамического перебора (Б8Я) для решения задач прямоугольной упаковки. Были сгенерированы следующие классы задач для Ж= 225: «малые» предметы (у], = 0.05, у2= 0.1; w| = 0.1, = 0.15), «средние» предметы (V;, = 0.25, V2= 0.35; w| = 0.35, = 0.45) и «малые и большие» предметы (V;, = 0.05, v2= 0.25; W| = 0.05, w2 = 0.95). Для каждого класса задач сгенерировано по 10 тестовых примеров. Критерием оценок также выступал коэффициент раскроя КРА, значения которого приведены на рис. 3.

Согласно данным, приведённым А.Ф. Валеевой для такого же класса задач, значения коэффициентов раскроя, полученных методом ББЯ, для класса «малых» предметов составляет 92 - 96%; «средних» - 98 - 100%; «малых и больших» - 93 - 95%. Таким образом, метод плоскостей показывает сравнимые результаты для класса «малых» и более лучшие для класса«разнородных» («малых и больших») предметов.

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

На основе тестовых данных, полученных с помощью безотходных двух и трёхмерных алгоритмов, были проведены численные эксперименты по обучению сигмоид-ных нейронных сетей в нейроимитаторе КеигоРго 0.25. Структура нейросети: три слоя,

99,00 98,00 97,00 96,00 95,00 94,00 93,00 92,00 91,00 90,00 89,00

Малые

- - - Средние *— Малые и большие

60 n

120

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

каждый из которых содержал по десять нейронов.

Количество прямоугольников/коробок изменялось в диапазоне от 20 до 100, количество примеров для каждой обучающей выборки было сгенерировано в два раза больше количества объектов. Было произведено обучение нейронных сетей, при этом количество правильно решённых примеров составило 100%. В табл. 3 приведены результаты тестирования для задач двухмерной упаковки.

Была исследована зависимость разброса длины и ширины в обучающих примерах на значение ошибки. Выявлено, что при подборе обучающей выборки следует установить фиксированным значение одной из граней полосы на основе известной, например, Ж, а другое выбрать в диапазоне: Ьтп = Е£г/ Ж; Ьтах = Ьтп + Срзнач(/г), где Е£г- - суммарная площадь всех прямоугольников, Срзнач(/г) - среднее значение длин прямоугольников.

Как обучающие, так и тестовые примеры были сгенерированы на основе безотходных упаковок. Однако известно, что изменение порядка следования прямоугольников приводит, как правило, к получению другой карты раскроя и, соответственно, длины занятой части полосы. В связи с этим для тестовой выборки случайным образом был изменён порядок следования прямоугольников. Было сгенерировано по 10 тестовых примеров для случая п = 20. Среднее значение ошибки составило 4.4 %.

Таблица 3

Кол-во Диапазон Диапазон Средняя Средняя

№ прямоуголь- изменения изменения ошибка, максимальная

ников L W % ошибка, %

1. 20 100-200 100-200 46.3 127.3

2. 20 100-300 100-300 50.5 127.9

3. 20 278-288 278-288 12.1 32.3

4. 10 100-120 100 6.3 16.1

5. 10 400-440 400 14.9 29.9

6. 40 400-440 400 14.0 32.8

7. 100 400-440 400 13.4 30.5

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

Выводы

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

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

Литература

1. Dyckhoff H. Cutting and Packing / H. Dyckhoff, G. Scheithauer, J. Terno // Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F. Maffioli and S.Martello. - John Wiley&Sons, 1997. P. 393-412.

2. Dykhoff H. A typology of cutting and packing problems / H. Dykhoff // Evropean Journal of Operational research. 1990. Vol. 44. P. 145-159.

3. Мухачева А. С. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / А.С. Мухачева, А.Ф. Валеева, В.М. Картак. - М.: МАИ, 2004. - 193 с.

4. Валеева А.Ф. Конструктивные методы решения задач ортогональной упаковки и раскроя : автореф. дис. ... д - р. тех. наук: 28.09.2006 / А.Ф. Валеева. - Уфа, 2006. - 32 с.

5. Moura A. A grasp approach to the container-loading problem / A. Moura, J.F. Oliveira // IEEE Computer Society. July/August. 2005. P. 50-57

6. Pisinger D. Heuristics for the container loading problem / D. Pisinger // European Journal of Operational Research. 2002. № 141. P. 382-392.

7. Корчевская О.В. Получение нижних границ для задач двух и трехмерной ортогональной упаковки с помощью нейронных сетей, используя алгоритм безотходной упаковки / О. В Корчевская, Л.А. Жуков // Электронный журнал «Исследовано в России». 2008. № 62. С. 685694, URL: http: // zhurnal.ape.relarn.ru / articles/ 2008/062.pdf

8. Жуков Л.А. Метод плоскостей: численный эксперимент для задач двух и трехмерной ортогональной упаковки / Л.А.Жуков, О.В. Корчевская // Информационные технологии. 2008. № 11. С. 41-45.

Solutions for bin cutting & packaging problem with a constructive and neural network approach

OksanaValer'evnaKorchevskaya, Candidate of Science, Associate Professor Siberian State Technological University

Formulation of the problem is presented n- dimensional packaging (n = 1, 2 , 3). A description of the method of planes for solving the three-dimensional packaging. Shows the composition of this method for two-dimensional packing problem. To determine the lower limits of problem solving cutting-packing machine used neural networks. Highly efficient algorithms for solving two- and three-dimensional cutting-packing, allowing to quickly build a nesting layout with a coefficient of cutting an average of 85%. The reliability of the results is confirmed by a comparative analysis of the dissertation of the existing approaches to solving the problem and the results of experimental data.

Keywords: cutting tasks packaging optimization problems , NP- hard combinatorial optimization problems

УДК 330.42; 519.86

МОДЕЛИРОВАНИЕ ПАРАМЕТРОВ ПОСРЕДНИЧЕСКОЙ СЕТИ

Ирина Анатольевна Курынова, старший преподаватель E-mail: KuIrina@mail.ru ФГБОУ ВПО «Хакасский государственный университет им. Н. Ф.Катанова»

www.khsu.ru

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

Ключевые слова: торгово-посредническая сеть, спрос и предложение, моделирование, товарный поток

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