Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Двумерный раскрой / Двумерная упаковка, 2DSP - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, китин  
Мир MS Excel » Вопросы и решения » Готовые решения » Двумерный раскрой / Двумерная упаковка, 2DSP (Excel)
Двумерный раскрой / Двумерная упаковка, 2DSP
MCH Дата: Пятница, 08.10.2021, 20:15 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Тема является продолжением линейного раскроя и задачи о рюкзаке
Задачу двумерной упаковки в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP) можно сформулировать так:
Имеем набор из N прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон.
Подробное описание задачи и варианты жадных алгоритмов есть здесь

Мной реализован совершенно другой алгоритм, основанный на линейном программировании
В отличие от условий в статье на habr прямоугольники можно поворачивать на 90 градусов (либо отключать эту возможность)

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

Применяется гильотинный раскрой, т.е. от края до края, так режется, например, стекло.
При этом алгоритм не предназначен для раскроя листового материала, когда заданы размеры листов и нужно раскроить все прямоугольники используя наименьшее количество листов (ДСП или стекло), только для полуограниченной полосы
Ширина реза не используется, при резке стекла или пленки ширина реза равна нулю (но если очень нужно использовать ширину реза, то ее можно добавить к размерам прямоугольников).

Примеры получаемых раскроев во вложении
Рабочую программу можно скачать здесь: https://disk.yandex.ru/d/-ZbzYEJ2kdPLag
Файл cbc.exe должен находится вместе с файлом xls, в одной папке
Сложные примеры алгоритм может очень долго считать, нужно указывать ограничения (количество различных элементов в ряду и др.)
К сообщению приложен файл: 2DSP.xlsx (254.6 Kb)
 
Ответить
СообщениеТема является продолжением линейного раскроя и задачи о рюкзаке
Задачу двумерной упаковки в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP) можно сформулировать так:
Имеем набор из N прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон.
Подробное описание задачи и варианты жадных алгоритмов есть здесь

Мной реализован совершенно другой алгоритм, основанный на линейном программировании
В отличие от условий в статье на habr прямоугольники можно поворачивать на 90 градусов (либо отключать эту возможность)

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

Применяется гильотинный раскрой, т.е. от края до края, так режется, например, стекло.
При этом алгоритм не предназначен для раскроя листового материала, когда заданы размеры листов и нужно раскроить все прямоугольники используя наименьшее количество листов (ДСП или стекло), только для полуограниченной полосы
Ширина реза не используется, при резке стекла или пленки ширина реза равна нулю (но если очень нужно использовать ширину реза, то ее можно добавить к размерам прямоугольников).

Примеры получаемых раскроев во вложении
Рабочую программу можно скачать здесь: https://disk.yandex.ru/d/-ZbzYEJ2kdPLag
Файл cbc.exe должен находится вместе с файлом xls, в одной папке
Сложные примеры алгоритм может очень долго считать, нужно указывать ограничения (количество различных элементов в ряду и др.)

Автор - MCH
Дата добавления - 08.10.2021 в 20:15
Мир MS Excel » Вопросы и решения » Готовые решения » Двумерный раскрой / Двумерная упаковка, 2DSP (Excel)
  • Страница 1 из 1
  • 1
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!