Исследование операций, задача bin packing.

[_Student]

Доброй ночи всем!

Подскажите, пожалуйста, где можно почитать про задачу bin packing. Имеются бревна длины $l$, надо выпилить $a_i$ кусков длины $l_i$, используя наименьшее количество бревен.

Желательно пошаговый алгоритм для последующей реализации.
Спасибо!

[Rasool]

Задачей одномерной упаковки (bin packing problem) активно занимались на нашей кафедре, в частности, научная школа Элиты Александровны Мухачевой. Есть подход с точки зрения линейного программирования (симплекс-метод), про него можно прочитать в книге "Математическое программирование" авторов Мухачева, Рубинштейн.
Википедия дает следующую ссылку по Bin Packing Problem с алгоритмом "первый подходящий":
http://en.wikipedia.org/wiki/Bin_packing

[Rasool]

Есть монография "Задачи двумерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / А.С.Мухачева, А.Ф.Валеева, В.М. Картак, Москва, МАИ, 2004. 193 с. ISBN 5-7035-1413-4. Там рассматривается и случай одномерной упаковки.

[_Student]

Мне нужен тот алгоритм, где с помощью симплекс-метода считается, находится решение, но если оно не целое, то рассматривается два случая (округление вверх, округление вниз) и т.д. до того, как найдётся целое решение. Это, видимо, можно прочитать в книге "Математическое программирование" авторов Мухачева, Рубинштейн, да? А Вы, Rasool, могли кинуть ссылку на эту книгу?

[mserg]

В задаче нужно указать, от какого бревна нужно отпиливать конкретный кусок.
Прямая постановка такой проблемы как задачи линейного программирования – очень плохая идея. Задача становится очень громоздкой и возникает множество симметричных решений, а оптимум обычно вообще не находится.

Поэтому используется метод генерации столбца, который использует понятия варианта разрезания. Это особая разновидность симплекс-метода, которая дает нецелые решения. (См. в интернете «метод генерации столбца»). Методом ветвей и границ можно его доработать до нужного Вам решения.

[_Student]

mserg, мне как раз-таки нужен тот алгоритм, который Вы описали. Но хотелось бы почитать про него что-нибудь очень подробное, потому что я плохо представляю, как его реализовать.

[mserg]

Можно еще поискать Column Generation – должно найтись.
Но, честно говоря, эта тема больше подходит для кандидатской работы. Существование пошагового описания решения этой задачи крайне маловероятно. Надо что-то упростить. Например, если куски соразмерны размеру бревна, то можно перечислить все возможные варианты разрезания и составить задачу линейного программирования. Если таких вариантов не велико (скажем, не более 10000), то вряд ли будут проблемы. Потом воспользоваться готовым пакетом, например lp_solve или Excel (там есть численные методы, в том числе линейное программирование). Пакет сам, используя метод ветвей и границ, найдет оптимальное решение.