2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Исследование операций, задача bin packing.
Сообщение12.11.2010, 03:31 


17/10/10
49
Доброй ночи всем!

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

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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение13.11.2010, 12:14 


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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение14.11.2010, 18:08 


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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение14.11.2010, 18:53 


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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение22.11.2010, 14:59 


17/10/08

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

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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение23.11.2010, 23:02 


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

 Профиль  
                  
 
 Re: Исследование операций, задача bin packing.
Сообщение25.11.2010, 09:57 


17/10/08

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group