Л. В. Канторович и задачи раскроя-упаковки: новые подходы для решения комбинаторных задач линейного раскроя и прямоугольной упаковки

В середине XX века Л. В. Канторовичем и В. А. Залгаллером было предложено решать задачи экономного использования материала при его раскрое с помощью линейного программирования. Это привело к непрерывной релаксации задачи планирования рационального раскроя и по сути закрыло проблему в массовом производстве. В статье кратко изложены пути реализации метода для случая одномерного раскроя. Проблема продолжена на целочисленный случай, характерный для любой задачи раскроя. Для задач двумерного раскроя и упаковки разработана технология блочных структур. Она сводится к решению специальной задачи планирования одномерного раскроя, которая может быть решена с помощью линейного программирования с применением простых эвристик. Приведены некоторые вычислительные схемы и результаты численного эксперимента с безотходными упаковками. Сравнение с другими алгоритмами подтверждает эффективность блочного подхода. Библ. – 22 назв.