Расчет эффективного использования оконного корпуса (обрезка)

Question

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

Лучший способ объяснить это, чтобы дать пример:

отделка окна приобретается в длину 14 футов (168 дюймов). Скажем, у меня 5 прямоугольных окон разных размеров, все из которых состоят из 4 штук отделки каждого (сверху и снизу, справа и слева). Я пытаюсь построить алгоритм, который определит лучший способ сократить эти части с наименьшим количеством отходов.

Я изучил использование перестановок для расчета каждого возможного результата и отслеживания отходов, но количество перестановок, где за триллионы после того, как я прошёл 5 окон (20 различных частей отделки).

У кого-нибудь есть представление о том, как я могу это сделать.

Спасибо.

Answer 1

Вы смотрите типичный случай cutting stock problem.

Я нахожу this lecture from the University of North Carolina (pdf) довольно ясным. Больше ориентированы на внедрение, с примером во всем и на несколько требований - возможно, просто глядя на несколько аббревиатур. Но есть также 2 hours of video lectures from the university of Madras на эту тему, если вы хотите получить более подробную информацию и в довольно медленном темпе.

Он использует решение the knapsack problem несколько раз, которое вы можете захватить directly from Rosetta Code, если вы не хотите проходить вторую проблему линейной оптимизации.

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

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

Answer 2

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

например, окно 3050 можно обрезать отходами, используя один 8-дюймовый разрез и один 12-образный.