Модели раскроя хлыстов

Быков Даниил Юрьевич

Модели раскроя хлыстов

Быков Даниил Юрьевич. Модели раскроя хлыстов. Научный руководитель профессор И. В. Романовский. Направление математика, механика, кафедра исследования операций. Использовано 7 источников. В работе рассмотрена задача оптимизации заготовки леса с учётом качественных признаков. Разработано программное обеспечение, позволяющее произвести оценку ещё стоящего дерева на выход продукции заданного качества. Основная программа написана на языке C#, вспомогательные — на языке C# и в MATLAB. Быков, Д. Ю. Методы раскроя хлыстов: выпускная квалификационная работа бакалавра. / Быков Даниил Юрьевич. — СПБ., 2016. — 20 с. — Библиогр.: с. 20.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36515f1be77c40d58c7d

UUID: 839fd474-a621-4c5a-95a4-3396123541d3

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 66

Быков Даниил Юрьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 601850 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Прикладная математика и информатика Исследование операций и принятие решений в задачах оптимизации, управления и экономики Быков Даниил Юрьевич Модели раскроя хлыстов Бакалаврская работа Научный руководитель: д. ф.-м. н., профессор Романовский И. В. Рецензент: к. т. н., доцент Тамби А. А. Санкт-Петербург 2016

SAINT PETERSBURG STATE UNIVERSITY Applied Mathematics and Computer Science Operation Research and Decision Making in Optimisation, Control and Economics Problems Bykov Daniil Models of wood stem cutting Bachelor’s Thesis Scientific supervisor: Professor Romanovsky J. V. Reviewer: Associate professor Tambi A. A. Saint Petersburg 2016

Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Математическая часть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Программная часть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 Входные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Работа программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3

Введение На текущий момент при лесозаготовительных работах из всевозможных свойств древесины учитывается только объём и форма. Целью данной работы была разработка программного обеспечения, позволяющего производить оценку ещё растущих деревьев по различным внутренним свойствам. Такая оценка позволит рациональнее использовать природный ресурс, уменьшая выработку побочных продуктов лесопильными предприятиями. В книге [1] описано много способов вычисления раскроя, но к данной задаче они не применимы из-за сложных ограничений. Поэтому задача решалась перебором по возможным размерам пиломатериалов. Поскольку всевозможных сочетаний порядка 100, на скорости работы программы это не сказалось. 4

Глава 1 Постановка задачи 1.1 Определения Используемые определения: Хлыст — ствол дерева, очищенный от корней и кроны (веток). Круглые лесоматериалы — брёвна заданной длины, определённой стандартами. В России применяются длины 4 и 6 метров. Лесозаготовительное предприятие — предприятие, производящее круглые лесоматериалы из деревьев и поставляющее их в лесопильные предприятия. Лесопильное предприятие — предприятие, перерабатывающее круглые лесоматериалы на пиломатериалы для дальнейшей продажи. Лесосека — участок леса, предназначенный для вырубки. 1.2 Задача Рассмотрим общую схему работы лесозаготовительного предприятия. Для упрощения сделаем это на примере одного дерева: ∙ Сначала дерево нужно спилить; ∙ Затем очистить его от корней и кроны, получив хлыст; ∙ После чего получить из хлыста круглые лесоматериалы, распилив его на части; 5

∙ И в итоге доставить круглые лесоматериалы заказчику; Как правило, заказчиком является лесопильный завод, на котором установлено современное оборудование, позволяющее изучить каждое бревно и применить индивидуальный подход. Существует множество видов продукции, получаемой из круглых пиломатериалов: доски, брусья, шпалы, щепа и пр. В зависимости от назначения готовой продукции, к ней предъявляются различные требования. В связи с неоднородностью древесины, круглые лесоматериалы, полученные из одного хлыста, могут значительно отличаться по физико-механическим свойствам. В настоящее время круглые лесоматериалы сортируются лесозаготовительным предприятием только по размерам, из-за чего к заказчику доставляются брёвна сильно отличающиеся своими внутренними свойствами. Если работа заказчика нацелена на изготовление пиломатериалов определённого назначения, то у него получается высокая доля отходов или продуктов, изготовление которых не является приоритетной задачей. В этой связи экспертами в области свойств древесины были проведены исследования и установлены некоторые средние данные по деревьям вида ель и сосна. Имея средние данные, можно оценивать внутренние свойства ещё не спиленного дерева до начала лесозаготовительных работ. Более того, взяв пробу одного дерева, можно оценить свойства всего участка леса, который планируется спилить. Для упрощения процесса получения такой оценки целесообразно составить программу, что и являлось задачей данной работы. 1.3 Математическая часть Пусть имеется модельный хлыст. Пусть задана система координат 𝑥, 𝑦, 𝑧, в которой хлыст расположен вертикально, его нижняя граница находится в плоскости 𝑧 = 0, его высота равна 𝐻, а максимальный радиус — 𝑅. Пусть задано множество возможных длин пиломатериалов 𝐿. Пусть также имеется набор из 𝑁 физико-механических свойств хлыста, которые мы упорядочим по номерам 1, 2, . . . , 𝑁 . Предположим, что нам даны функции 𝑓𝑖 (𝑥, 𝑦, 𝑧) : [0, 𝑅] × [0, 𝑅] × [0, 𝐻] → R, 6 𝑖 ∈ {1, 2, . . . , 𝑁 },

задающие значение свойства 𝑖 в точке (𝑥, 𝑦, 𝑧). Для дальнейших вычислений будем считать, что функции 𝑓𝑖 (𝑥, 𝑦, 𝑧) ≡ 𝑐1 при 𝑥2 + 𝑦 2 = 𝑐2 , то есть, что их значение не меняется при вращении вокруг оси 𝑧. При таком предположении достаточно знать значения 𝑓𝑖 (0, 𝑦, 𝑧) разреза хлыста плоскостью 𝑥 = 0 (рис. 1.1). Обладание древесиной определёнными свойствами можно задать системой неравенств 𝑓𝑖 (0, 𝑦, 𝑧) ∈ 𝑇𝑖 , 𝑖 ∈ {1, 2, . . . , N}, (1.1) где 𝑇𝑖 = {[𝑎, 𝑏] : 𝑎 6 𝑏, 𝑎, 𝑏 ∈ R} То есть нужно указать для каждого свойства границы допустимых значений. Пусть Ω𝑖 ⋂︀ — множество точек (𝑦, 𝑧) таких, что выполнено условие 𝑖, и Ω = Ω𝑖 . Тогда можно задать функцию-индикатор множества Ω: ⎧ ⎪ ⎨1, если (𝑦, 𝑧) ∈ Ω 𝑂(𝑦, 𝑧) = ⎪ ⎩0, иначе (1.2) Теперь предположим, что нам известна функция 𝐹 (ℎ1 , ℎ2 , 𝑂), которая по заданным высотам ℎ1 , ℎ2 и функции 𝑂(𝑦, 𝑧) возвращает максимальный объём выходных пиломатериалов, удовлетворяющих заданным свойствам. Имея все указанные выше функции можно поставить задачу. Задача 1. Пусть даны 𝑓𝑖 (𝑦, 𝑧), 𝑂, 𝐿. Найти ℎ𝑖 так, чтобы 𝑚−1 ∑︁ 𝐹 (ℎ𝑖 , ℎ𝑖+1 , 𝑂) → max 𝑖=0 ℎ𝑖+1 − ℎ𝑖 =: 𝑙𝑖 ∈ 𝐿, ℎ0 = 0, ∀𝑖 ∈ {0, 1, . . . , 𝑚 − 1} ℎ𝑚 = 𝐻 − 𝜀, где 𝜀 < 𝑙𝑖 , (1.3) ∀𝑖 Для решения задачи 1 необходимо уметь вычислять 𝐹 (ℎ1 , ℎ2 , 𝑂). Для этого сформулируем следующую задачу. Пусть дана функция 𝑟(ℎ) : [0, 𝐻] → [0, 𝑅], которая сопоставляет высоту хлыста ℎ его радиусу на этой высоте. Тогда сутью функции 𝐹 будет поиск раскроя бревна с заданным положением в хлысте при котором выход пиломатериалов с нужными свойствами будет максимален. Существует множество способов распиловки бревна, на рисунке 1.2 представлены основные из них. 7

18 16 14 12 10 8 6 4 2 0 −0.5 0 Рис. 1.1: Схема сечения хлыста плоскостью 𝑥 = 0. 8 0.5

Рис. 1.2: Способы распиловки брёвен. [2] 9

В зависимости от конкретного способа распиловки, алгоритм решения может меняться, но суть одна и та же: вписать в окружность радиуса 𝑟 прямоугольники так, чтобы площадь прямоугольников, подходящих под наши нужды, была максимальна. Поскольку мы считаем все свойства древесины неизменными при повороте относительно оси 𝑧, а раскраиваемая окружность лежит в плоскости 𝑧 = ℎ2 , то достаточно знать функцию 𝑔(𝑟) : [0, 𝑅] → {0, 1}, которая по заданному радиусу 𝑟 возвращает 1, если все точки, лежащие на вертикальном отрезке между точками (𝑟, 0, ℎ1 ) и (𝑟, 0, ℎ2 ), принадлежат Ω, т.е. 𝑔(𝑟) = ⎧ ⎪ ⎨1, если (𝑟, 0, 𝑡) ∈ Ω, ∀𝑡 ∈ [ℎ1 , ℎ2 ] (1.4) ⎪ ⎩0, иначе Зная функцию 𝑔(𝑟), можно определить функцию-индикатор, определяющую, принадлежит ли данный пиломатериал множеству Ω. Положим 𝐺(𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 ) = ⎧ √︀ ⎪ ⎨1, если 𝑔( 𝑡𝑥2 + 𝑡𝑦 2 ) = 1 ∀(𝑡𝑥, 𝑡𝑦) ∈ [𝑥1 , 𝑥2 ] × [𝑦1 , 𝑦2 ] (1.5) ⎪ ⎩0, иначе Такая функция 𝐺 показывает, лежит ли прямоугольник с указанными координатами вершин в «хорошей» зоне (рис. 1.3). ГОСТом [3] установлены номинальные размеры толщины и ширины обрезных пиломатериалов с параллельными кромками. В таблице указаны 16 вариантов допустимой толщины на каждую из которых приходится не более, чем 9 вариантов допустимой ширины. Пусть нам задано отображение 𝑤(𝑑) : 𝐷 → 𝑊 , где 𝐷 — множество возможных толщин, а 𝑊 — множество допустимых значений ширины, для пиломатериала толщиной 𝑑. Рассмотрим случай, когда используется способ распиловки, изображённый на (рис. 1.4). Тогда задачу можно поставить следующим образом. Задача 2. Пусть даны ℎ1 , ℎ2 , известны функции 𝑟(ℎ), 𝑔(𝑟), 𝑤(𝑑). Найти 𝜔 и 𝑑 такие, что 𝐹 = 𝑘−1 ∑︁ 𝜔 · 𝑑 · 𝐺(𝑑 · 𝑖, 0, 𝑑 · (𝑖 + 1), 𝜔) → max (1.6) 𝑖=0 𝜔 ∈ 𝑤(𝑑) Теперь, когда задачи поставлены, можно переходить к составлению программы. 10

𝑦 𝑦 𝜔 𝑥 𝑑 𝑥 Рис. 1.3: «Хорошие» зоны. Рис. 1.4: Способ распиловки. 11 𝑟

Глава 2 Программная часть Для разработки был выбран язык C# , поскольку он приспособлен для разработки приложений под OS Windows. 2.1 Входные данные Для вычислений программе нужны данные по модельным хлыстам. Эти данные должны быть представлены в виде матрицы значений по разрезу хлыста плоскостью 𝑥 = 0, то есть значениями функций 𝑓𝑖 (0, 𝑦, 𝑧) на сетке с шагом 1 см. В таком формате данные не требуют большого объёма памяти и достаточно удобны для получения более мелкой сетки методами интерполирования. Предоставленные мне экспериментальные данные, полученные в [4], имели разный формат. Так, информация о плотности модельных хлыстов хранилась в виде матриц, в которых число строк соответствовало длине хлыста в метрах, а столбцов всегда 6. Строка с номером 𝑖 соответствовала данным на высоте 𝑖 метров, начиная с высоты 1 метр, 𝑖−1 а столбец с номером 𝑗 соответствовал данным, находящимся на удалении × 𝑅𝑖 от 5 центра ствола. Данные о радиусе ствола были так же представлены в виде вектора из значений на высоте 1, 2, . . . , 𝐻 метров. Для приведения этих данных в требуемый вид была написана программа в среде MATLAB, которая интерполировала значения между данными точками и экстраполировала ниже одного метра. Для интерполяции матриц свойств использовался метод кубических сплайнов. При экстраполяции этот метод не давал положительных результатов, поэтому использовался линейный метод. Данные 12

радиуса пришлось приближать линейно в обоих случаях, поскольку при использовании приближения многочленами нередко появлялась ситуация, в которой радиус ствола в некоторых местах увеличивается с увеличением высоты, что не соответствует действительности. Большую трудность представляли данные о ширине годичных слоёв, поскольку исходных данных не сохранилось, а имелись только графики (рис. 2.2). Рис. 2.1: Ширина годичного слоя сосны. Рис. 2.2: Ширина годичного слоя ели. К счастью, была возможность раскрасить линии в красный, что позволило составить программу, которая распознаёт на картинке эти линии и приближает эту функцию многочленом заданной степени. Получились не самые лучшие результаты, но достаточные для начала работы программы. После внедрения данного метода оценки лесосеки можно будет использовать более точные данные с лесопильных предприятий, а текущие нужны скорее для грубой начальной оценки. 13

2.2 Работа программы Для начала работы программе нужно указать вид дерева: ель или сосна. После этого нужно выбрать свойства, которые будут влиять на раскрой. Затем для каждого свойства указать границы, в которых должно лежать значение свойства. Также нужно задать шаг точности, по умолчанию равный 1 мм. Пункт 1. Подготовка данных. Чтобы программе не приходилось много работать с двумерными массивами, делается следующее. ⌊︂ ⌋︂ 𝑅 1. Создаётся массив размера , где 𝑅 — радиус основания хлыста, 𝑠𝑡𝑒𝑝 — шаг 𝑠𝑡𝑒𝑝 точности; 2. Каждый элемент массива — список всех границ, в которых лежат «хорошие» ячейки по высоте с координатой 𝑦 = 𝑖 × 𝑠𝑡𝑒𝑝, где 𝑖 — индекс массива. Пункт 2. Раскрой хлыста. Основной процесс раскроя выглядит так: 1. Начальная высота ℎ = 100 мм; 2. Рассмотрим все возможные длины бревна из заданного массива 𝐿; 3. Если ℎ + 𝑙𝑖 < 𝐻, то есть, если бревно длины 𝑙𝑖 помещается в часть хлыста выше ℎ, находим оптимальный раскрой бревна, расположенного между ℎ и ℎ + 𝑙𝑖 и переходим к пункту 2 с ℎ = ℎ + 𝑙𝑖 ; 4. Если ℎ + 𝑙𝑖 > 𝐻, ∀𝑙𝑖 ∈ 𝐿, то оптимальный раскрой при текущих длинах брёвен найден и он записывается в список всех найденных раскроев. 5. По окончанию перебора всех возможных длин брёвен выбирается раскрой, дающий максимальный объёмный выход. Пункт 3. Раскрой бревна. Раскрой бревна состоит из следующих пунктов: 1. Заданы ℎ1 , ℎ2 — нижняя и верхняя границы бревна и массивы границ «хороших» ячеек; 2. Вычисляем множество границ на отрезке [0, 𝑟(ℎ2 )], в которых все ячейки между ℎ1 и ℎ2 являются «хорошими»; 14

3. Далее рассматриваются все возможные раскрои бревна и из них выбирается лучший; В результате работы программа получает оптимальный раскрой хлыста и выводит его в текстовом и графическом виде (рис. 2.3). Рис. 2.3: Пример графического вывода программы. На рисунках выводятся схемы раскроя хлыста по высоте и схемы раскроя брёвен. Чёрные линии обозначают границу хлыста, зелёные — «хорошие» ячейки. На схеме хлыста красным цветом отображены линии распила на брёвна. Справа от схемы хлыста находятся схемы раскроя бревна с соответствующим номером. Красные линии на схемах брёвен обозначают границы пропилов. В текстовом выводе содержится информация о 15

раскрое хлыста на брёвна и о раскрое каждого бревна на прямоугольные пиломатериалы. Для каждого бревна выводится следующая информация: 1. нижняя и верхняя границы, объём «хороших» пиломатериалов; 2. «основная ширина» — ширина пиломатериалов в средней части; 3. «толщины» — первая толщина соответствует пиломатериалам средней части, вторая — боковых частей; 4. «побочные ширины» — список ширин пиломатериалов в боковых частях бревна в порядке от центра. После вывода информации о брёвнах идёт общая информация о раскрое: 1. выбранные свойства и их границы; 2. стоимость «хороших» пиломатериалов за один кубический метр; 3. стоимость обычных пиломатериалов за один кубический метр; 4. толщина пропила; 5. доля объёма «хороших» пиломатериалов к объёму бревна; 6. доля объёма всех пиломатериалов к объёму бревна; 7. суммарная стоимость «хороших» пиломатериалов. 8. суммарная стоимость всех пиломатериалов. 9. объёмная доля и суммарная стоимость, полученная при раскрое по максимальному объёму без учёта ограничений. В примере полного текстового вывода (2.4) видно, что при указании ширины годичного слоя между 0.7 и 5 мм суммарная стоимость выходит больше, чем при раскрое без учёта ограничений. В примерах с ограничением по ширине годичного слоя (2.5) видно, что суммарная стоимость так же больше при указании границ, чем без. 16

Высоты распила хлыста: 100, 4100 мм Объём: 0,15 м^3 8107,2, 12107,2 мм Толщины: 22, 25 мм Объём: 0,08 м^3 Основная ширина: 75 Толщины: 19, 25 мм Побочные ширины: Основная ширина: 75 225 мм Побочные ширины: 175 мм 150 мм 100 мм 75 мм ------------------ ------------------ 4103,6, 8103,6 мм 12110,8, 16110,8 мм Объём: 0,12 м^3 Объём: 0,05 м^3 Толщины: 19, 22 мм Толщины: 60, 19 мм Основная ширина: 75 Основная ширина: 75 Побочные ширины: Побочные ширины: 200 мм 100 мм Свойства: Плотность: 400-999 Стоимость 1: 7000 р Стоимость 2: 6000 р Ширина пропила: 3.6 мм Доля объёма "хороших" пм: 54.7% Доля объёма всех пм: 58.7% Цена "хороших" пм: 2825.20 р Цена всех пм: 3001.60 р Без ограничений: Доля объёма пм: 62.4% Цена всех пм: 2763.60 р 150 мм 75 мм Рис. 2.4: Пример полного текстового вывода. 17

Свойства: Свойства: Ширина годичного слоя: 0,7-5 Ширина годичного слоя: 0,9-4 Стоимость 1: 8000 р Стоимость 1: 8000 р Стоимость 2: 6000 р Стоимость 2: 6000 р Ширина пропила: 3,6 мм Ширина пропила: 3,6 мм Доля объёма "хороших" пм: 53,0% Доля объёма "хороших" пм: 51,5% Доля объёма всех пм: 53,0% Доля объёма всех пм: 52,8% Цена "хороших" пм: 3124,80 р Цена "хороших" пм: 3040,00 р Цена всех пм: 3124,80 р Цена всех пм: 3097,60 р Без ограничений: Без ограничений: Доля объёма пм: 61,6% Доля объёма пм: 61,6% Цена всех пм: 2725,20 р Цена всех пм: 2725,20 р Рис. 2.5: Примеры вывода при ограничениях по ширине годичного слоя. 18

Заключение В результате работы было составлено программное обеспечение, позволяющее оценить объём выхода пиломатериалов с требуемыми свойствами и их стоимость. При внедрении данного ПО в работу лесозаготовительных предприятий и получении от них более точных данных, возможно улучшение точности работы программы. Также возможно добавление других типов распиловки брёвен. При написании программ были использованы материалы с сайтов [5] и [6]. 19

Список литературы [1] Канторович Л. В., Залгаллер В. А. Рациональный раскрой промышленных материалов. СПб.: Невский Диалект, 2012. Т. 304. [2] Калитеевский Р. Е., Артеменков А. М., Тамби А. А. Информационные технологии в лесопилении. СПб.: ПРОФИ, 2010. Т. 192. [3] ГОСТ 24454-80. 01.01.1981. URL: http://docs.cntd.ru/document/gost-24454-80. [4] Чубинский А. Н., Кандакова Е. Н., Тамби А. А. Актуальные проблемы технологических процессов лесозаготовительных и деревоперерабатывающих производств. Актуальные проблемы технологических процессов деревоперерабатывающих производств: методические указания по изучению дисциплины для студентов, обучающихся по направлению 35.04.02. СПб.: СПбГЛ-ТУ, 2015. Т. 28. [5] Microsoft. Microsoft Developer Network. 2016. URL: https://msdn.microsoft.com. [6] The MathWorks, Inc. Matlab documentation. 2016. URL: http://www.mathworks.com/ help/matlab/. [7] Калитеевский Р. Е. Лесопиление в 21 веке : технология, оборудование, менеджмент. ПРОФИ-ИНФОРМ, 2008. Т. 505. 20

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв