Форум: "Потрепаться";
Текущий архив: 2003.06.05;
Скачать: [xml.tar.bz2];
ВнизАлгоритм оптимального раскроя Найти похожие ветки
← →
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 Программный продукт, предназначенный для оптимального раскроя стекла при производстве
стеклопакетов".
А еще: "Алгоритм уступок А.Бабченко".
← →
MalkoLinge (2003-05-16 17:00) [9]На самом деле это раздел теории линейного программирования.
← →
bosso (2003-05-16 18:38) [10]Спасибо всем, кто отозвался. Насчет Бабченко - готовые программы не подходят, хотелось написать именно свою. Насчет линейного программирования - теперь вспоминается что-то из университетского курса. Надо только учебник найти...
← →
Юрий Зотов (2003-05-16 21:33) [11]Насчет линейного программирования - не все так радужно. Все зависит от конечной цели. Если можно сформулировать целевую функцию, то да, теория дает ответ, как можно найти ее экстремум. А если нельзя - то теория практически бессильна.
Приходилось мне решать задачу оптимального раскроя листа. Есть лист известных размеров (обозначим их 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, с их помощью очень удобно манипулировать со ступенчатыми областями.
Если бы задача была не двумерной (прямоугольники), а одномерной (отрезки) - то тогда да, линейное программирование ее решает. Потому что способ размещения отрезков на прямой искать не надо - он всегда один и тот же, а их порядок значения не имеет. Впрочем, в моем случае (кол-во деталей каждого вида одинаково), такая одномерная задача вообще решается без всякой теории, обыкновенной арифметикой.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.06.05;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.009 c