Пример №1 . Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины - по 2 метра. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров приведены в табл.
Ширина рулона(м) | Варианты раскроя рулона | Минимальное количество рулонов | |||||
1 | 2 | 3 | 4 | 5 | 6 | ||
0,5 | 0 | 2 | 2 | 4 | 1 | 0 | 150 |
0,7 | 1 | 1 | 0 | 0 | 2 | 0 | 200 |
0,9 | 1 | 0 | 1 | 0 | 0 | 2 | 300 |
Отходы в м | 0,4 | 0,3 | 0,1 | 0 | 0,1 | 0,2 | - |
Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
0,4Х 1 + 0,3 Х 2 + 0,1 Х 3 + 0,1 Х 5 + 0,2 Х 6 .
Таким образом, математическая модель в общем виде имеет вид
min f(x) = 0,4 X 1 + 0,3Х 2 + 0,1Х 3 + 0,1Х 5 + 0,2Х 6 .
при ограничениях:
2Х 2 + 2 Х 3 + 4 Х 4 + Х 5 = 150
Х 2 + Х 2 + 2 Х 5 = 200
Х 2 + Х 3 + 2 Х 6 = 300
Таблица 3
Виды | План-задание по количеству заготовок (b 1) | Выход заготовок (шт) разных видов |
|||
1 | 2 | 3 | 4 | ||
1 | 240 | 1 | 4 | 0 | 1 |
2 | 200 | 1 | 0 | 4 | 0 |
3 | 120 | 1 | 0 | 0 | 3 |
4 | 140 | 1 | 1 | 0 | 3 |
Площадь отходов, м 2 (c j) | 1,4 | 0,1 | 2,1 | 0,1 |
F=1,4·x 1 +0,1·x 2 +2,1·x 3 +0,1·x 4 →(min)..
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:
Пример №3
. На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b 1 , b 2 ,…,b l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2,…,n) дает a ik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим через x i – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению
F=x→(max),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.
Пример №4
. На предприятии имеются бревна длиной L м, которые необходимо разрезать на заготовки длиной l 1 , l 2 , l 3 м в количестве p 1 , p 2 , p 3 соответственно.
Необходимо составить оптимальный план раскройки материала, который обеспечивает минимальные отходы, при условии выполнения плана по выходу заготовок. Исходные данные приведены в таблице.
Задача | Длина | Размеры заготовок, м | Количество заготовок, шт. | ||||
l 1 | l 2 | l 3 | p 1 | p 2 | p 3 | ||
68 | 6,5 | 2,1 | 2,3 | 1,4 | 600 | 720 | 900 |
Длина заготовки | Варианты раскроя | Количество заготовок | ||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
2,1 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 600 |
2,3 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 720 |
1,4 | 0 | 0 | 1 | 1 | 3 | 1 | 3 | 900 |
Остаток, м | 0,2 | 0 | 0,9 | 0,7 | 0,2 | 0,5 | 0 |
Таким образом, для решения поставленной задачи необходимо найти minZ при ограничениях. Поскольку minZ = -max(-Z(x)), то вместо задачи минимизации функции будем решать задачу максимизации функции:
Z = -(0,2x 1 + 0x 2 + 0,9x 3 + 0,7x 4 + 0,2x 5 + 0,5x 6 + 0x 7)
Пример №5
. Для пошива одного изделия требуется выкроить из ткани 6 деталей. На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м 2 ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м 2 . В ближайший вечер планируется сшить 90 изделий.
Построить математическую модель задачи, позволяющий в ближайший месяц выполнить план по пошиву с минимальным количеством отходов.
Таблица - Характеристики вариантов раскроя отрезков ткани по 10м 2
Вариант раскроя | Количество деталей, шт./отрез | Отходы, м 2 /отрез | |||||
1 | 2 | 3 | 4 | 5 | 6 | ||
1 | 60 | 0 | 90 | 40 | 70 | 90 | 0,5 |
2 | 80 | 35 | 20 | 78 | 15 | 0 | 0,35 |
Комплектность, шт./изделие | 1 | 2 | 2 | 2 | 2 | 2 |
Математическая постановка задачи
Переменные задачи
В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м 2 двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько - вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10м 2 , раскроенных каждым из способов:
x 1 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
x 2 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
Целевая функция
Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м 2) ткани по 1-му варианту получается 0,5м 2 отходов, а по 2-му варианту - 0,35м 2 (см. таблицу 1), то общее количество отходов при крое (ЦФ) имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min,
Ограничения
Количество раскроев ткани различными способами ограничивается следующими условиями:
Математически эти ограничения записываются в виде
:
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;
Ограничение по расходу ткани имеет следующие формы записи:
Содержательную
(общее количество ткани, раскроенной за месяц)≤ (405м 2)
Математическую
x 1 +x 2 ≤405/10
Не отрицательность количества раскроенных отрезков задается в виде
x 1 ≥ 0, x 2 ≥ 0
Таким образом, математическая модель задачи имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min [м 2 отх./мес.],
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;
x 1 +x 2 ≤40,5
x 1 ≥ 0, x 2 ≥ 0
Пример №6 . Имеется 69 труб для отопительной сети по 1070 см каждая. Их необходимо разрезать на трубы по 130, 150 и 310 см. Найти такой вариант раскроя поступивших труб, при котором отходы были бы минимальными.
Этап 1. Определяем варианты оптимального распила труб.
Варианты раскроя | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
310 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
150 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
130 | 1 | 0 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | 7 | 8 |
Остатки | 10 | 0 | 20 | 40 | 60 | 50 | 70 | 90 | 110 | 100 | 120 | 10 | 30 |
Этап 2.
Составим экономико-математическую модель задачи. Обозначим через x j - количество труб, которые необходимо распилить по одному из способов j. Целевая функция сводиться к нахождению минимума отходов при распиле:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min
x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69
Ответ: необходимо использовать только второй вариант распила (нулевые отходы)
Версия: 2.49
Разработчик: Шибаев Юрий Анатольевич Украина, г. Черкассы
Сайт разработчика: http://www.cuttinghome.com/
Разрядность: 32bit
Совместимость с Windows 7: да
Язык интерфейса: Английский + Русский
Таблэтка: Вылечено
Системные требования: Минимальные
Описание: Программа CUTTING предназначена для оптимального раскроя материала на линейные детали. Программа могут быть использованы в деревообрабатывающем производстве, производстве мебели, рубки металла, резки стекла и т.д. В основу программ положен уникальный, высокоскоростной алгоритм, позволяющий быстро произвести раскрой с минимальными отходами.
При разработке алгоритмической части программ основным критерием выбран принцип минимизации отходов, а при разработке интерфейсной части автор стремился сделать программы простыми и удобными в каждодневном пользовании.
В программе реализованы следующие функции и возможности:
. задание произвольного числа раскраиваемых заготовок и отрезков
. задание заготовок и отрезков по определенным признакам, например, названию и цвету
. расчет с учетом типа материала (название материала, цвет)
. задание ширины режущего инструмента
. расчет суммарных длин отрезков и остатков
. задание разных режимов выполнения раскроя
. восстановление предыдущих раскроев текущего сеанса работы
. сохранение заданных заготовок и отрезков как спецификации
. добавление сохраненной спецификации к новому варианту расчета
. сохранение раскроя в файл с возможностью последующего восстановления
. просмотр и печать результатов раскроя, как в графическом, так и в табличном виде
. полная система справочной информации.
"Раскрой", "Утвердить", "Просмотр", "Этикетки", "Справка", "Закрыть"
"Целые хлысты на складе" - позволяет указать склад, с которого будут браться целые хлысты для раскроя.
"Выводить в отчет" - вывод в соответствующий столбец карты раскроя номера армирования (соответствующие номеру основного профиля) или артикул контейнера (в который устанавливается данное армирование).
В таблице отчета по групповому раскрою профилей введен столбец `Арм.№` по номеру элемента каждого изделия (сортировка отрезанных профилей с соответствующей каждому из них арматурой - по номеру элемента в изделии)
Предопределенный отчет по групповому раскрою профилей расширен столбцом высоты ручки к профилям створок (для маркировки для сверления под ручку на профиле створки сразу после проведения раскроя - отреза заготовки)
Программа предназначена для оптимизации раскроя профиля и других длинномерных материалов (брус, бревно, труба, подоконник).
Использован алгоритм "плотной укладки", то есть взятое изделие укладывается на самый короткий остаток заготовки, на который она помещается. Если никуда не помещается, берется новая заготовка. Задачей оптимизации является нахождение последовательности изделий, при которой будет использовано меньше заготовок и будет больше длина деловых обрезков. На первом такте, изделия размещаются на хлыстах в случайном порядке. Возникает "начальная популяция". В процессе решения, популяция мутирует и размножается, неудачные экземпляры погибают, а лучшие продолжают эволюцию. Всё, как в животном и растительном мире + искусственный отбор.
Пример ниже - не статическая картинка, а работоспособное веб - приложение.
Вы можете запустить раскрой профиля кнопкой Старт
, задать свои размеры изделий и заготовок, изменить настройки оптимизации и оценить решение.
Конечно, оптимизатор в браузере работает медленнее, чем нативная программа, но позволяет бесплатно получить пригодные для работы результаты без необходимости что либо скачивать и устанавливать на компьютер.
В окнософт:каттинге использован генетический алгоритм. Суть его вот в чем:
Назовем каждое распределение изделий по хлыстам решением. Определим целевую функцию, позволяющую сравнивать качество решений. Сформируем несколько произвольных решений, назовем их поколением. Определим правила получения следующего поколения. Экземпляры с лучшей целевой функцией передают большую часть своего "генофонда", это наш "искусственный отбор". Теперь остается предоставить систему самой себе, пусть мутирует и оптимизирует результаты раскроя
В процессе разработки испытывался метод "Монте-Карло", когда наши "экземпляры" являются случайными и не зависят друг от друга и "Муравьиные алгоритмы"(ACO- ant colony optimisation). Все методы показали себя вполне работоспособным, но генетический алгоритм оказался чуть более эффективным
Есть два варианта поставки модуля раскроя Окнософт:cutting - в составе комплексного решения Управление позаказным производствм и в виде отдельного исполняемого файла. Взаимодействие с раскройной программой при первом сценарии, полностью скрыто от пользователя. Оператор работает со стандартными документами 1С:
Файл входных данных - setup.ini, помещается в папку с исполняемым файлом.
Файлы выходных данных - result.txt, resultproduct.txt и resultstick.txt - формируются в той же папке.
Скачать файлы с демо-данными Окнософт:cutting можно по ссылке в конце страницы. В файлх используются следующие теги:
Используется при подготовке данных для станков, поддерживающих парный распил. В этом случае, в станок помещают сразу два хлыста профиля и за один такт отрезания, образуется два одинаковых полуфабриката
Задача парного раскроя решается группировкой данных перед их передачей в программу оптимизации и последующего дублирования результатов раскроя на пары изделий и заготовок. При работе раскроя внутри УПзП, система учитывает свойства номенклатуры и использует одиночный или парный раскрой в зависимости от возможностей отрезных станков
С одной стороны, для достижения высокого качества оптимизации, на вход программы должно поступать значительное количество изделий разной длины, чтобы оптимизатору было "что сортировать". С другой, при очень больших партиях, снижается вероятность нахождения максимума при фиксированном числе итераций перебора. Эксперименты показали, что оптимальной является партия в 60 – 120 заготовок (что соответствует такту производства 30-60 изделий при парном раскрое). Если необходимо оптимизировать более 120 заготовок, лучших результатов можно добиться, разделив задачу на N частей и выполнив последовательные оптимизации для каждой части. Обработка формирования пачек заданий на производство умеет группировать продукции по видам профиля и подбирать в сменные задания изделия с максимальной дисперсией, избавляя оператора от рутинной работы по составлению производственных документов
Версия: 2.49
Разработчик: Шибаев Юрий Анатольевич Украина, г. Черкассы
Сайт разработчика: http://www.cuttinghome.com/
Разрядность: 32bit
Совместимость с Windows 7: да
Язык интерфейса: Английский + Русский
Таблэтка: Вылечено
Системные требования: Минимальные
Описание: Программа CUTTING предназначена для оптимального раскроя материала на линейные детали. Программа могут быть использованы в деревообрабатывающем производстве, производстве мебели, рубки металла, резки стекла и т.д. В основу программ положен уникальный, высокоскоростной алгоритм, позволяющий быстро произвести раскрой с минимальными отходами.
При разработке алгоритмической части программ основным критерием выбран принцип минимизации отходов, а при разработке интерфейсной части автор стремился сделать программы простыми и удобными в каждодневном пользовании.
В программе реализованы следующие функции и возможности:
. задание произвольного числа раскраиваемых заготовок и отрезков
. задание заготовок и отрезков по определенным признакам, например, названию и цвету
. расчет с учетом типа материала (название материала, цвет)
. задание ширины режущего инструмента
. расчет суммарных длин отрезков и остатков
. задание разных режимов выполнения раскроя
. восстановление предыдущих раскроев текущего сеанса работы
. сохранение заданных заготовок и отрезков как спецификации
. добавление сохраненной спецификации к новому варианту расчета
. сохранение раскроя в файл с возможностью последующего восстановления
. просмотр и печать результатов раскроя, как в графическом, так и в табличном виде
. полная система справочной информации.