Задачи упаковки и раскроя: проблема рюкзака и метод генерации столбцов

Математическим атомом для задач раскроя является классическая задача о рюкзаке (Knapsack Problem). Представьте, что у нас есть один стандартный рулон бумаги шириной 5 метров (это наш рюкзак). Нам заказали нарезать из него рулоны шириной 1 метр, 2 метра и 3 метра (каждый из которых имеет свою ценность для выполнения плана). Какие рулоны отрезать, чтобы максимизировать полезное использование 5-метрового куска? Эта задача формулируется как целочисленное линейное программирование. Несмотря на экспоненциальную сложность полного перебора, одномерная задача о рюкзаке феноменально быстро решается методами динамического программирования или алгоритмами ветвей и границ, что позволяет компьютеру за миллисекунды генерировать оптимальные схемы нарезки (паттерны) для одного отдельного рулона.

Однако реальный заводской заказ требует нарезать не один, а тысячи рулонов, удовлетворяя спрос на десятки различных размеров. Прямая формулировка такой задачи в виде целочисленной матрицы приводит к астрономическому числу переменных, так как количество возможных уникальных схем нарезки (паттернов) для длинных рулонов исчисляется миллионами. Классический симплекс-метод просто не поместится в оперативную память суперкомпьютера. В 1961 году Пол Гилмор и Ральф Гомори совершили революцию в дискретной оптимизации, предложив метод генерации столбцов (Column Generation), который позволил обходить эту проблему, не записывая все миллионы вариантов в память.

Алгоритм Гилмора-Гомори стартует с крошечного, искусственного набора самых простых паттернов (например, нарезать рулон только на куски одного размера). Симплекс-метод решает эту усеченную задачу и вычисляет так называемые теневые цены (двойственные оценки) для каждого размера заказанных деталей. Эти теневые цены показывают, насколько выгодно производить ту или иную деталь в текущий момент. Затем наступает магия: вместо перебора оставшихся миллионов паттернов алгоритм запускает вспомогательную подзадачу (ту самую задачу о рюкзаке!), где весами выступают длины деталей, а ценностями — их текущие теневые цены. Если алгоритм рюкзака находит новый паттерн нарезки, ценность которого превышает затраты на один рулон, этот новый паттерн (новый столбец) добавляется в главную симплекс-матрицу.

Процесс итеративно повторяется: симплекс-метод пересчитывает план и обновляет теневые цены, а задача о рюкзаке генерирует под эти цены новые, все более эффективные паттерны нарезки. Когда задача о рюкзаке больше не может найти ни одного выгодного паттерна, математика строго гарантирует, что найденный план раскроя является глобально оптимальным для всей фабрики, даже если алгоритм реально рассмотрел лишь крошечную долю из миллионов возможных вариантов. Сегодня метод генерации столбцов (интегрированный в алгоритмы Branch-and-Price) применяется не только на сталелитейных заводах, но и при составлении расписаний экипажей авиакомпаний (Crew Rostering), где маршруты пилотов генерируются на лету, соблюдая строгие законы трудового кодекса и минимизируя корпоративные издержки.