Эта задача как понимаю, впервые поставленная Канторовичем и его школой изучается естественно в приличных ВУЗах
Однако в весьма куцем виде. Варианты постановок -
а) мин количества заготовок б)мин отходов при обеспечении заданных объемов поставок Для сведения ее к стандартной задаче линейного программирования и применения симплекс-метода надо еще решить подзадачу - найти оптимальные. векторы вариантов раскроя. Оптимальные в смысле Парето т.е чтобы при сравнении любых двух не было бы чтобы все компоненты одного меньше всех компонент другого.
Эта часть задачи обычно проглатывается - и это понятно - кому охота заниматься в ВУЗе программированием если
задачу ЛП при известной матрице можно решить в Excel с помощью налстройки Поиск решения
Я восполнил недостающую часть алгоритма- построение набора векторов Парето и вместе с ними матрицы
задачи линейного программирования 1-мерного раскроя
Пусть

длина заготовки

-кол-во типов кусков (разные длины

- массив длин кусков
Задача ставится по известным входным данным найти количество

и набор векторов Парето

и матрицу

задачи ЛП. (столбцы которой составлены из этих векторов)
Эта задача мной решена, т.е. написана программа делающая это.
Но результаты все же удручают. Так если при количестве типов заготовок

и не очень больших длинах скажем

получается набор из 7 векторов (матрица 3x7) то уже при

и

получается 59 векторов и матрица 5x59
Конечно и такую матрицу можно запихнуть в симплекс-метод и получить оптимальное решение, но ясно что здесь висит проблема размерности.
Пример расчета

Вопрос - как повысить эффективность алгоритма решения задачи одномерного раскроя
без перехода к параллельным вычислениям?