Оптимальный раскрой(упаковка)

← →
Delf (2003-07-26 15:42) [0]

Может знает кто класный или хоть какой-нибудь алгоритм решения вот такой задачи
Есть набор разных плоских прямоугольных деталей (размеры и количество задаются) уложить эти детали на столах (M x N) так чтобы столов было использовано как можно меньше
Полный перебор дохнет уже при 10-20 дедалях(задача NP-полная)
Я пока накопал только генетический алгоритм но он очень зависит от случайности и далеко ни всегда дает приемлемый результат

← →
Sha (2003-07-26 16:13) [1]

И.В. Романовский "Алгоритмы решения экстремальных задач", "Наука",
М., 1977

← →
Fenik (2003-07-26 19:05) [2]

Вывести функцию и иссследовать на экстремум.

← →
Fenik (2003-07-26 19:23) [3]

А столы все одинакового размера?

← →
uw (2003-07-27 19:34) [4]

Кантарович, когда взялся за задачу "фанерного треста", тоже думал, что легко. Оказалось - трудно. Подумал - получил Нобелевскую премию.

← →
Fenik (2003-07-27 19:38) [5]

Действительно.. Задачка та ещё.

← →
Delf (2003-07-29 10:24) [6]

to Fenik
Да вот как эту функцию вывести ?
Столы одинакового розмера
to uw
раз Канторович занимался этой задачей то алгоритм можно где-то взять или он не является общедоступным

← →
uw (2003-07-29 10:29) [7]

>Delf © (29.07.03 10:24)

Линейное программирование.

← →
Basja (2003-07-29 10:37) [8]

> uw ©

не встречал в линейном программировании ничо подобного.
или ты хочеш это подвести под симплекс метод?

← →
uw (2003-07-29 10:45) [9]

"Серьезные занятия экономикой начались для Кантор овича с того, что в 1938 г. к нему за консультацией обратились несколько инженеров из лаборатории фанерного треста. Смысл их проблемы заключался в том, что при обработке различного сырья на разных лущильных станках получалась различная производительность и стояла задача максимизации выпуска продукции при заданном соотношении между ее видами. В современной терминологии эту проблему можно сформулировать как задачу максимизации линейной функции при наличии линейных ограничений. В простом случае решение легко найти перебором экстремальных точек допустимого множества, однако даже в задаче фанерного треста, при пяти станках и восьми видах сырья, это потребовало бы решения около миллиарда систем линейных уравнений.

Для решения предложенной ему задачи Канторович в январе 1939 г. разработал специальный метод, при котором с каждым ограничением исходной задачи связывалась специальная оценка, называемая разрешающим множителем. Оптимальный план задачи определялся в результате итеративного процесса, в ходе которого происходила последовательная корректировка разрешающих множителей. Таким образом, Канторович открыл новый раздел математики — линейное программирование, изучающий задачи нахождения экстремума линейной функции на допустимом множестве, задаваемом линейными ограничениями и неравенствами, и предложил алгоритм решения таких задач."

← →
uw (2003-07-29 10:49) [10]

Очень занятное продолжение той же статьи:

"Идеи Канторовича долго не признавались экономистами. Когда в 1939 г. он выступал с докладами о своей работе, ему возражали, что она «использует математические методы,

а на Западе математическая школа в экономике — средство апологетики капитализма». Во время одной из дискуссий известный в то время статистик Б.С. Ястремский сказал Канторовичу: «Вы говорите об оптимуме, и Парето говорит об оптимуме. А ведь Парето — фашист!». В связи с этим при написании брошюры Канторович был вынужден максимально избегать экономической терминологии; не удалось также подробно раскрыть экономический смысл разрешающих множителей, в частности проблему их связи с системой цен."

← →
Delf (2003-07-29 14:56) [11]

> uw ©

> В современной терминологии эту проблему можно сформулировать
> как задачу максимизации линейной функции при наличии линейных
> ограничений.

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

← →
uw (2003-07-29 15:10) [12]

>Delf © (29.07.03 14:56)

Честно говоря, я никогда сам не использовал линейное программирование, но изучал его с целью применить. И у меня сложилось представление, что оптимальный раскрой - это то, с чего оно и начиналось. Я бы очень удивился, если бы это было не так. Думаю, в инете можно найти подходящие постановки задач из области линейного программирования.

← →
Всеволод Соловьёв (2003-07-29 15:18) [13]

Лучшие проги для раскроя (лучшие из всех) - Cutting’и, стоят $100-200 и то иногда тупят. http://www.cuttinghome.com

← →
Delf (2003-07-29 19:02) [14]

> Честно говоря, я никогда сам не использовал линейное программирование,
> но изучал его с целью применить. И у меня сложилось представление,
> что оптимальный раскрой - это то, с чего оно и начиналось.

Может быть и так но только с линейного раскроя
Так как метод линейного програмирования дает точный т.е в даном случае оптимальный результат то думаю программы для двумерного раскроя использовали бы этот алгоритм и не тупили бы как сказал
> Всеволод Соловьёв ©

У меня самого есть парочка демо-версий таких програм и все они дают разный результат при одинаковых входных данных
Самого алгоритма их роботы нигде не выложено, значит очень уж хитрые авторские алгоритмы использовались,и програмисты их не обнародуют.
На форуме RSDN.RU мне сказали что на данное время существуют только алгоритмы дающие результат близкий к оптимальному
и я подумал может кто знает парочку таких алгоритмов и поделится идеями

← →
Юрий Зотов (2003-07-29 19:09) [15]

Решал я нечто подобное, правда попроще (количество разложенных прямоугольников всех видов должно было быть строго одинаковым). Тоже сначала думал симплекс-метод применить, а потом понял, что проблема-то не в самом нахождении экстремума, а именно в двумерности задачи (собственно, в моем случае задача к экстремальным и вовсе не относилась, строго говоря).

Сначала нужно было найти алгоритм раскладки - ну, это было сделано довольно легко, через регионы Windows. А вот найти алгоритм поиска оптимальной раскладки так и не удалось, пришлось решать задачу перебором.

Заметьте, что если бы задача была линейной , а не двумерной, то способ раскладки был бы всего один - вот это-то и позволяет решить задачу симплекс-методом. Одно слово - линейное программирование.

← →
Ass (2003-07-30 00:42) [16]

Есть такой метод - Штейнберга. Примерно то, что нужно. Суть метода естественно в критерии, позволяет существенно снизить трудоемкость. Сорри, что одни пустые слова - делал подобное в институте, но ... много воды утекло. Поищи. Может пригодится.

← →
uw (2003-07-30 01:12) [17]

http://www.dvgu.ru/pin/math1/for_students/linpro/tosno/node6.html

← →
Delf (2003-07-30 11:22) [18]

to
> uw ©

Спасибо за ссылку но там описан как раз линейный раскрой:
"Исходная проблема заключается в нахождении оптимального раскроя партии листов (фанеры, бумаги, металла ...) на заготовки заданных размеров: li,i=1,2,...,I. "
(задана только длинна заготовок следовательно ширина подразумевается равной ширине заготовки(рулона))
Двумерный случай же не сводится к линейному
По крайней мере я свести не могу

Оптимальный раскрой(упаковка) Найти похожие ветки