Алгоритм оптимального разреза пиломатериалов

← →
Ky3bka (2004-06-28 15:24) [0]

Привет, мастера.

Нужно решить следующую задачу:
Есть склад с кучей досок разной длины (100-200шт).
Нужно отрезать от них N кусков длиной X[1]...X[N].
При этом должны соблюдатся условия:
1. Как можно больше было остатков длиной < XMin.
2. Крайне не желательны остатки < XMax.
3. Среди остатков > XMax приоритет имеют те, первоначальные заготовки которых были минимальной длины.

Как реализовать такой алгоритм?

← →
nejest (2004-06-28 16:21) [1]

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

← →
Рамиль © (2004-06-28 16:32) [2]

Вы это... в институте учились?..
Простенькая задача оптимизации за второй курс.

← →
Внук © (2004-06-28 16:46) [3]

>>Рамиль © (28.06.04 16:32) [2]
А нетрудно поподробнее про простоту? Или это закос под Ферма? :)
>>Ky3bka (28.06.04 15:24)
Попробуй сходить сюда http://www.orioncutting.narod.ru/ или сюда http://www.cuttinghome.com/indexr.htm. Дальше по яндексу.
Правда, алгоритма там нет.

← →
BillyJeans (2004-06-28 16:59) [4]

Типовая задачка, даже в 1С её задают ;)

← →
Внук © (2004-06-28 17:10) [5]

Тогда киньте линк на теорию, серьезно. Я что-то не припомню такого в стандартном курсе методов оптимизации, да и книжки на эту тему в пару страниц не влезают. Может, дело в том, что я изначально на двумерную задачу нацелился - стекла, ткань, древесные плиты...
А программы есть - это да. Программы для составления расписания тоже есть, и курсовые такие даются. Только вот точного решения задачи пока нету :)

← →
BillyJeans (2004-06-28 17:31) [6]

вторая же ссылка в яндексе!

http://algolist.manual.ru/maths/combinat/payment1.php

← →
GEN++ © (2004-06-28 20:02) [7]

По раскрою плит Вы голову сломаете. Однозначного оптимального
раскроя для массива типоразмеров заготовок и массива типорамеров
исходных листов просто не существует - много импирического.
А вообще существуют готовые программы раскроя: Cutting, Best
Раскрой 2000, Базис конструктор мебельщик, By CAD, Bars - все
работают с прямоугольными листами/деталями, но если хотите
сломать голову гарантировано, то попробуйте прямоугольные листы
с фигурными деталями.
Сам алгоритм можно поискать в Лестехе - если они его не закрыли.

← →
TUser © (2004-06-28 20:12) [8]

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

← →
KilkennyCat © (2004-06-29 01:03) [9]

Блин, я на днях хотел такую прогу сбацать... по оптимальному распилу плит. В том числе и не прямоугольные куски. Однако, потом пришел к выводу, что это слишком просто и таких прог - куча. Спасибо - порадовали, обязательно попробую.

← →
Внук © (2004-06-29 09:18) [10]

>>GEN++ © (28.06.04 20:02) [7]
Вот и я о том же. Хотя, может быть, отстал от жизни.

Если доска одна и ее нужно распилить на части оптимальным образом - это, я так понимаю, стандартная "задача о ранце" из курса методов оптимизации. А вот когда досок несколько, тут не все так просто, imho.

← →
GEN (2004-06-29 14:10) [11]

>KilkennyCat ©
Будете делать - не забудьте о технологии распиловки
(вдоль/поперек текстуры, гильотонный рез, удержание материала руками и еще пуру десятков требований), кроме того заложитесь хотя бы на 1000 деталей
Удачи

← →
kudatsky (2004-06-29 17:52) [12]

>Ky3bka
Всё делается элементарно.
Возьми одну доску, и
реши задачу для неё.
Для остальных досок - так же.

>>kudatsky (29.06.04 17:52) [12]
Говорю же, не все так просто. Пусть есть 2 доски длиной 10м каждая. И надо напилить кусков: один 5м, второй 4м, и 3 куска по 3 м.
Вот первый вариант распила: первая доска 5+4м, остаток 1 м, вторая доска 3+3+3м, остаток 1 м.
Второй вариант: первая доска 5+3м, остаток 2м, вторая доска 4+3+3м, остатка нет.
Какой вариант лучше? В первом два маленьких остатка, во втором одна из досок израсходована полностью, но непрерывный остаток 2м.
Добавьте сюда
"При этом должны соблюдатся условия:
1. Как можно больше было остатков длиной < XMin.
2. Крайне не желательны остатки < XMax.
3. Среди остатков > XMax приоритет имеют те, первоначальные заготовки которых были минимальной длины."
Это я к тому, что решение последовательно для каждой доски не пройдет.
Задачка, на мой взгляд, скорее не оптимизационная, а комбинаторная.

Задачка, на мой взгляд, скорее не оптимизационная, а комбинаторная.

Оптимизационная. Потому как даже перебор методом ветвей и границ относится к задачам оптимизации. А полный перебор тут неприемлем ввиду количества вариантов.

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

← →
Ky3bka (2004-06-30 23:42) [15]

Вот надумал кое-что. Пришлось смухлевать малость.
Затея такая:
1. Составляются всевозможные комбинации из требуемых деталей (1, 1+2 ...). (можно по макс. длине ограничить) /*далее слепки*/
2. Для каждого "слепка" находится та заготовка на складе, отрезая от которой, можно получить самый выгодный вариант.
3. Оцениваются все соотношения "слепка-заготовка" и начиная с самой приемлимой начинаем резать.
Естественно детали в слепках повторяются, но отрезаются только один (первый) раз.
4. Так до тех пор, пока не получим все нужные детали.

Дело в том, что изделия для производства к-х нужны детали постоянны. Поэтому в данном случае получается, что распиловка идет "с учетом на будущее" и приемлима (хотя не факт, что оптимальна).
Может присоветуете что к этому?

Алгоритм оптимального разреза пиломатериалов Найти похожие ветки