Алгоритм оптимального раскроя

← →
Bosso (2003-05-16 10:45) [0]

Уважаемые господа! Задача оптимального раскроя прямоугольника
на более мелкие прямоугольники. Может, у кого-то есть алгоритм,
ссылка на статью, а может, кто и код уже писал? plz, отправьте
телеграфом на xavier@mail.nnov.ru!

← →
Vit@ly © (2003-05-16 10:47) [1]

Алгоритм: линейное программироание

← →
evvcom © (2003-05-16 10:47) [2]

А что ты называешь "оптимальным раскроем"? Что-то не встречал такого термина.

← →
Vit@ly © (2003-05-16 10:58) [3]

Это достаточно понятное всем понятие в математике

← →
Dms (2003-05-16 11:07) [4]

> понятное всем понятие
поэтому и куча ответов :)

← →
Sha © (2003-05-16 11:45) [5]

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

← →
MMF © (2003-05-16 12:24) [6]

http://soft.protoplex.ru/cgi-bin/?showid=1005
http://soft.protoplex.ru/cgi-bin/?showid=1006

← →
Calm © (2003-05-16 12:37) [7]

> MMF © (16.05.03 12:24)
> http://soft.protoplex.ru/cgi-bin/?showid=1005
> http://soft.protoplex.ru/cgi-bin/?showid=1006

из заголовка сайта:
На нашем никогда не виснущем сервере Вы найдете море полезной информации.

Мне кажется, что Bosso (16.05.03 10:45) в курсе о том, что в инете море информации.
Думается, что он просил что-то конкретное...

← →
MMF © (2003-05-16 12:44) [8]

:-)) Я просто скопировал ссылки со страницы автора. Не виноват, что они гючные. Имелось ввиду:
"Оптимум Программа “Оптимум” предназначена для построения оптимальных карт раскроя погонных и листовых материалов"
"OptimGlass Программный продукт, предназначенный для оптимального раскроя стекла при производстве
стеклопакетов".
А еще: "Алгоритм уступок А.Бабченко".

На самом деле это раздел теории линейного программирования.

← →
bosso (2003-05-16 18:38) [10]

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

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

Приходилось мне решать задачу оптимального раскроя листа. Есть лист известных размеров (обозначим их A и B). Из него надо раскроить 3 вида прямоугольников. Размеры каждого вида известны (обозначим их x1,y1, x2, y2 и x3, y3), а количество прямоугольников каждого вида должно быть одинаковым (обозначим его N - то есть, всего будет 3*N прямоугольников). Ну, плюс еще некоторые технологические ограничения, которые ради простоты опустим. Задача - найти расположение прямоугольников на листе, при которых N будет максимальным.

Тоже сначала полез в линейное программирование. А потом понял, что оно здесь ни при чем - потому что не дает алгоритма поиска РАЗМЕЩЕНИЯ деталей на листе.

Действительно, ведь математически здесь все очень просто.

1. Берем теоретически максимальное N:
N = INT((A*B)/(x1*y1+x2*y2+x3*y3));

2. Ищем способ расклада N комплектов на листе.

3. Если найти удалось - задача решена. Если нет - уменьшаем N на единицу и повторяем с п. 2.

Все замечательно, только вот п.2 вызывает вопрос - а КАК искать способ расклада? И, к сожалению, на ЭТОТ вопрос никакое линейное программирование ответа не дает. Уж, скорее, комбинаторика. А в итоге делалось, в общем-то, методом перебора (плюс некая логика, дабы сдерать этот перебор все же не совсем тупым). Кстати, для Bosso: могу подкинуть идею - я использовал регионы Windows, с их помощью очень удобно манипулировать со ступенчатыми областями.

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

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