Задача раскроя — это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце. Задача является задачей целочисленного линейного программирования. Задача возникает во многих областях промышленности. Представим себе, что вы работаете на целлюлозно-бумажном предприятии, и у вас имеется некоторое количество рулонов бумаги фиксированной ширины, но различным заказчикам нужны различные количества рулонов различной ширины. Как разрезать бумагу, чтобы минимизировать отходы? Согласно данным Конфедерации европейских производителей бумаги, в 2012 году 1331 бумагоделательных машин в регионе производят в среднем отходов на 56 млн евро (примерно 73 млн долларов США) каждая. Экономии даже 1 % будет очень существенной. Формулировка задачи и подходы к решению Стандартная...