Описание Области
подробнее…
Постановка задачи
Задача раскроя – это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце. Задача является задачей целочисленного линейного программирования. Задача возникает во многих областях промышленности. Представим себе, что вы работаете на целлюлозно-бумажном предприятии, и у вас имеется некоторое количество рулонов бумаги фиксированной ширины, но различным заказчикам нужны различные количества рулонов различной ширины. Как разрезать бумагу, чтобы минимизировать отходы?
Дано:
• Некоторое число исходного материала заданного размера, для разрезки на куски.
• Заказы на определенное количество кусков заданного размера.
Требуется:
Разрезать исходный материал таким образом, чтобы выполнить все заказы, минимизируя отходы от раскроя.
кратко