Задача оптимального раскроя

@Mikhaylo · Регистрация: 20.09.2014

Студворк — интернет-сервис помощи студентам

У меня возникла реальная задача - написать программу для станка раскроя ткани. Ткань в рулоне ширины W, рулон разматывают на стол длины H в несколько заходов. Нужно оптимальным образом нарезать ортогональными резами N прямоугольных кусков размером (w_i, h_i). Особенность ножа в том, что он не совсем аккуратно режет углы, т.е. каждый разрез делается с запасом на небольшое расстояние d=5...8 мм в начале реза и на расстояние d в конце реза. Поэтому между прямоугольниками по обоим сторонам делается зазор величиной d и в результате сетка из полосок ткани толщиной d выбрасывается.
Чтобы не мучаться с этим дополнительным усложнением (d) будем считать, что нож все-таки режет идеально и зазоры между кусками не делаются, а все размеры кусков увеличиваются на величину d, прогоняются через оптимизационный алгоритм, а затем несложным алгоритмом результат оптимальной раскройки преобразуется в раскрой с зазорами.

Итак, фактически прямоугольники w_i, h_i нужно уложить в неограниченное количество рюкзаков размерами W, H. При этом нужно минимизировать потери ткани. При этом у последнего "рюкзака" часть неразрезанной (неиспорченной разрезами) ткани, оставшейся с рулоном, не является потерей. Станок отрезает эту часть ткани поперек и она сматывается обратно в рулон.

Добавлено через 1 час 35 минут
Два варианта алгоритма:
1. прямоугольники можно поворачивать на 90 градусов
2. нельзя поворачивать (направленный рисунок на ткани)

@m-ch · 13.01.2022, 07:11

Вы можете приложить несколько примеров реальных данных для раскроя? Попробую прогнать своим алгоритмом. Есть некоторые идеи по задаче 2DSP, нужно наработать статистику, потому что некоторые наборы алгоритм плохо раскраивает

@Mikhaylo · 13.01.2022, 07:31 **[ТС]**

Ширина полосы 3000 мм
Первая строчка: 4 шт. изделий 1900х2468. Высота 1900, ширина 2468.
Размер "Высота" должна быть вдоль полосы, поворачивать нельзя.

@Mikhaylo · 13.01.2022, 07:34 **[ТС]**

Но это неинтересный пример. Увеличьте ширину ткани до 3400 мм.

@m-ch · 13.01.2022, 08:43

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

Посмотрите, на сколько получился нормальным раскрой?

@Mikhaylo · 13.01.2022, 08:49 **[ТС]**

3400-90: хороший алгоритм! С ним можно ознакомиться?

@m-ch · 13.01.2022, 08:54

Сообщение от Mikhaylo

3400-90: хороший алгоритм! С ним можно ознакомиться?

Прямую ссылку не даю, запрещено правилами форума, можно найти в поисковике
рабочий файл с открытым кодом и описание есть на форуме excelworld
поиск по фразе: Двумерный раскрой / Двумерная упаковка, 2DSP

@m-ch · 13.01.2022, 09:12

Рабочий файл с указанным набором данных

@m-ch · 13.01.2022, 10:28

Если установить ширину рулона - 4000 и указать возможность вращать детали, то раскраивается даже очень неплохо, заполнение более 96%

@m-ch · 23.01.2022, 21:44

Mikhaylo, удалось посмотреть мою реализацию раскроя?
Алгоритм нормально раскраивает реальные данные?

@Mikhaylo · 24.01.2022, 11:51 **[ТС]**

Пока не дошли руки

@m-ch · 24.01.2022, 12:09

Mikhaylo, приложите еще несколько наборов реальных данных для раскроя

Новые блоги и статьи Все статьи Все блоги /
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .	21 мат мед. Планы на развитие модели здравоСохранения anaschu 01.06.2026 AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .	20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .	Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,778

	Задача оптимального раскроя 17.07.2021, 13:10. Показов 12644. Ответов 30 Метки вариант задачи о рюкзаке (Все метки) У меня возникла реальная задача - написать программу для станка раскроя ткани. Ткань в рулоне ширины W, рулон разматывают на стол длины H в несколько заходов. Нужно оптимальным образом нарезать ортогональными резами N прямоугольных кусков размером (w_i, h_i). Особенность ножа в том, что он не совсем аккуратно режет углы, т.е. каждый разрез делается с запасом на небольшое расстояние d=5...8 мм в начале реза и на расстояние d в конце реза. Поэтому между прямоугольниками по обоим сторонам делается зазор величиной d и в результате сетка из полосок ткани толщиной d выбрасывается. Чтобы не мучаться с этим дополнительным усложнением (d) будем считать, что нож все-таки режет идеально и зазоры между кусками не делаются, а все размеры кусков увеличиваются на величину d, прогоняются через оптимизационный алгоритм, а затем несложным алгоритмом результат оптимальной раскройки преобразуется в раскрой с зазорами. Итак, фактически прямоугольники w_i, h_i нужно уложить в неограниченное количество рюкзаков размерами W, H. При этом нужно минимизировать потери ткани. При этом у последнего "рюкзака" часть неразрезанной (неиспорченной разрезами) ткани, оставшейся с рулоном, не является потерей. Станок отрезает эту часть ткани поперек и она сматывается обратно в рулон. Добавлено через 1 час 35 минут Два варианта алгоритма: 1. прямоугольники можно поворачивать на 90 градусов 2. нельзя поворачивать (направленный рисунок на ткани) 0

@m-ch 6180 / 945 / 313 Регистрация: 25.02.2011 Сообщений: 1,381 Записей в блоге: 1
	13.01.2022, 07:11
	Вы можете приложить несколько примеров реальных данных для раскроя? Попробую прогнать своим алгоритмом. Есть некоторые идеи по задаче 2DSP, нужно наработать статистику, потому что некоторые наборы алгоритм плохо раскраивает 0

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,778
	13.01.2022, 07:31 [ТС]
	Ширина полосы 3000 мм Первая строчка: 4 шт. изделий 1900х2468. Высота 1900, ширина 2468. Размер "Высота" должна быть вдоль полосы, поворачивать нельзя. 0

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,778
	13.01.2022, 07:34 [ТС]
	Но это неинтересный пример. Увеличьте ширину ткани до 3400 мм. 0

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,778
	13.01.2022, 08:49 [ТС]
	3400-90: хороший алгоритм! С ним можно ознакомиться? 0

@m-ch 6180 / 945 / 313 Регистрация: 25.02.2011 Сообщений: 1,381 Записей в блоге: 1
	23.01.2022, 21:44
	Mikhaylo, удалось посмотреть мою реализацию раскроя? Алгоритм нормально раскраивает реальные данные? 0

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,778
	24.01.2022, 11:51 [ТС]
	Пока не дошли руки 0

@m-ch 6180 / 945 / 313 Регистрация: 25.02.2011 Сообщений: 1,381 Записей в блоге: 1
	24.01.2022, 12:09
	Mikhaylo, приложите еще несколько наборов реальных данных для раскроя 0