Задача о линейном раскрое

Различные математические алгоритмы.
Joo
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 762
Зарегистрирован: 14.08.2008 (Чт) 11:55
Откуда: Казахстан

Задача о линейном раскрое

Сообщение Joo » 25.03.2012 (Вс) 14:21

Привет! Подходящего раздела не нашел, напишу здесь.
Есть следующая задача:
Имеем D-деталей различной длины, большое кол-во. Имеем набор упаковок с заготовками. В каждой упаковке по N-штук заготовок длиной L, заготовки в каждой упаковки равной длины, но в разных упаковках длины могут различаться.
Необходимо выполнить раскрой с минимальными отходами. По условию, все неиспользованные заготовки из распечатанной упаковки так-же считаются отходами.

У меня есть несколько вариантов.
1. Полный перебор вариантов кроя и выбор наилучшего. Дает 100% оптимальный результат, но не пригоден при большом кол-ве деталей.
2. Жадный алгоритм, когда сортируем детали от большей к меньшей и каждую деталь отрезаем от заготовки минимальной длины на которую он помещается. Часто результат не совсем хороший, скорость работы очень высокая.
3. Еще вариант, тасовать порядок деталей как в картах, чем больше деталей тем больше вариантов растасовки. В подавляющем числе случаев дает более чем хороший результат, скорость работы высокая, но медленнее чем во втором случае.

Возможно кто-то сталкивался с подобной задачей, хотелось бы услышать, как вы справились с ней?
"Им будет не просто, тем кто полагается на истину авторитета, вместо того чтобы полагаться на авторитет Истины"
Джеральд Месси, Египтолог

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Задача о линейном раскрое

Сообщение Хакер » 25.03.2012 (Вс) 14:36

Все задачи раскроя решаются перебором. Но простой перебор занимает невероятно много времени и малоэффективен, поэтому рационально вычислять «подсказчки» и «ограничения» для алгоритма.

Найди книжки Э. А. Мухачёвой, там целая научная работа на эту тему.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Joo
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 762
Зарегистрирован: 14.08.2008 (Чт) 11:55
Откуда: Казахстан

Re: Задача о линейном раскрое

Сообщение Joo » 25.03.2012 (Вс) 14:40

Хакер писал(а):Найди книжки Э. А. Мухачёвой, там целая научная работа на эту тему.

Спасибо! Сейчас поищу.
"Им будет не просто, тем кто полагается на истину авторитета, вместо того чтобы полагаться на авторитет Истины"
Джеральд Месси, Египтолог

Sam777e
Продвинутый пользователь
Продвинутый пользователь
 
Сообщения: 157
Зарегистрирован: 16.09.2010 (Чт) 4:33

Re: Задача о линейном раскрое

Сообщение Sam777e » 25.03.2012 (Вс) 17:29

Посмотри стандартную схему Линейного программирования и иже с ним . . .
http://eqworld.ipmnet.ru/ru/library/boo ... 968ru.djvu
Здоровья и удачи

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 25.03.2012 (Вс) 17:47

Joo писал(а):В каждой упаковке по N-штук заготовок длиной L

Т. е. N одинаковое во всех коробках?

Joo
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 762
Зарегистрирован: 14.08.2008 (Чт) 11:55
Откуда: Казахстан

Re: Задача о линейном раскрое

Сообщение Joo » 25.03.2012 (Вс) 18:34

Qwertiy писал(а):Т. е. N одинаковое во всех коробках?

нет, может и разное быть
"Им будет не просто, тем кто полагается на истину авторитета, вместо того чтобы полагаться на авторитет Истины"
Джеральд Месси, Египтолог

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 25.03.2012 (Вс) 21:25

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

Необходимо выполнить означает именно выполнить или только найти объём отходов?

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 25.03.2012 (Вс) 21:35

Вообще, дай целое условие со всеми ограничениями.

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Задача о линейном раскрое

Сообщение Proxy » 25.03.2012 (Вс) 22:42

И описания не очень понял про упаковки и заготовки (как соотносятся и что есть отходы: все неиспользованные заготовки по количеству / по суммарной длине или "огрызки" заготовок в т.ч), можешь изобразить схематически процесс получения деталей из заготовок+упаковок?
Ну и из вариантов имхо нужно развивать первый, чтобы он стал в итоге пригодным (из условий может быть возможно найти полезные закономерности, но пока я не совсем однозначно понял условия).
Задача немного похожа на олимпиадную, т.к. упаковки одинаковых по размеру заготовок, одномерные размерности — это какой-то сферический конь в вакууме. Даже кажется, что нечто подобное встречал (хотя это какой-то ад, даже походу при таких условиях сложнее, чем задача с вычислением количества 3D шаров в ёмкости заданной формы, там хотя бы не тупо перебор, который проваливается на большом количестве). Если действительно олимпиадная, то стало быть надо смотреть прошлогодние/аналогичные демонстрационные, т.к. у организаторов вечно свои тараканы в голове и своё представление о верном решении (и корректности и однозначности условий). И в этом случае некоторые неявные условия могут подразумеваться, хотя не описаны.
Ну а в сторону эвристики двигаться как минимум не интересно, это чаще всего богомерзкие полумеры, весь выигрыш от которых сводится на нет количеством промахов. Эвристика имеет смысл только там, где что-либо мешает провести детальный анализ области и создать адекватный алгоритм (ограничение мат.обеспечения, ограничение вычислительных ресурсов и т.д, хотя второе тоже как бы не повод, т.к. в том же классическом "коммивояжере" эвристику использовали только потому, что сложно иной алгоритм придумать).
Follow the white rabbit.

Joo
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 762
Зарегистрирован: 14.08.2008 (Чт) 11:55
Откуда: Казахстан

Re: Задача о линейном раскрое

Сообщение Joo » 26.03.2012 (Пн) 6:20

Qwertiy писал(а):Необходимо выполнить означает именно выполнить или только найти объём отходов?

Именно выполнить, т.е. получить схему кроя, при минимальном кол-ве отходов (суммарно)
Proxy писал(а):как соотносятся и что есть отходы

Отходы в данном случае, это суммарная длина огрызков + суммарная длина неиспользованных заготовок из распечатанной упаковки.
Proxy писал(а):Задача немного похожа на олимпиадную

Да, задача похожа на олимпиадную, но в данном случае это задача из жизни

Вот пример расчета по третьему варианту:
Код: Выделить всё
Введите необходимые отрезки через запятую в формате Длина[:Кол-во]
:> 300,300,210,150,19,25,152,214,17,188,160,135,250,250,117,222
-----------------------------------------
Введите имеющиеся варианты упаковок через запятую в формате Длина:Кол-во
:> 200:10,250:10,300:10
-----------------------------------------
Кол-во отрезков: 16
Кол-во растасовок: 272
=========================================
Упаковка 300x10 потери 443
-----------------------------------------
Режем от панели 1 отрезок длиной 19
Режем от панели 1 отрезок длиной 25
Режем от панели 1 отрезок длиной 210
Режем от панели 1 отрезок длиной 17
Режем от панели 2 отрезок длиной 150
Режем от панели 2 отрезок длиной 117
Режем от панели 3 отрезок длиной 300
Режем от панели 4 отрезок длиной 300
Режем от панели 5 отрезок длиной 222
Режем от панели 6 отрезок длиной 250
Режем от панели 7 отрезок длиной 250
Режем от панели 8 отрезок длиной 160
Режем от панели 8 отрезок длиной 135
Режем от панели 9 отрезок длиной 188
Режем от панели 10 отрезок длиной 214
-----------------------------------------
Упаковка 200x10 потери 1848
-----------------------------------------
Режем от панели 1 отрезок длиной 152
-----------------------------------------
Кол-во использованных упаковок: 2
Общие потери: 2291
=========================================


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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 26.03.2012 (Пн) 11:11

Joo, давай так:
Код: Выделить всё
unsigned n;         // Количество видов отрезков
unsigned m;         // Количество видов коробок

unsigned d[MAXN];   // Требуемые длины отрезков
unsigned с[MAXN];   // Требуемые количества отрезков

unsigned l[MAXM];   // Длины заготовок в коробках
unsigned k[MAXM];   // Количество коробок данного вида
Ограничения:
Код: Выделить всё
1<=n && n<=MAXN
1<=m && m<=MAXM
ForAll i : 1<=d[i] && d[i]<=MAXD
ForAll i : 1<=c[i] && c[i]<=MAXC
sum {i} of d[i]*c[i] <= MAXSUMD
ForAll i : 1<=l[i] && l[i]<=MAXL
ForAll i : 1<=k[i] && k[i]<=MAXK
sum {i} of l[i]*k[i] <= MAXSUML
Чему равны MAXN, MAXM, MAXD, MAXC, MAXSUMD, MAXL, MAXK, MAXSUML?

Joo
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 762
Зарегистрирован: 14.08.2008 (Чт) 11:55
Откуда: Казахстан

Re: Задача о линейном раскрое

Сообщение Joo » 26.03.2012 (Пн) 11:38

Макс. кол-во видов отрезков MAXN - можно прикинуть, шаг отрезка 0,1см, на данный момент максимальная длина заготовки 300см, а отрезок не может быть длиннее этого значения, значит кол-во видов 3000.
Макс. кол-во видов упаковок MAXM - в данный момент 3 вида, длины заготовок по 200, 250, 300 сантиметров и по 10 штук в каждом типе упаковки.
Макс. длина требуемого отрезка MAXD - 300см.
Макс. кол-во требуемых отрезков для каждого типа отрезка MAXC - теоретически сколько угодно, по факту более 150 не бывало.
Макс. сумма длин отрезков умноженное на кол-во MAXSUMD - 200000см, больше пока не было.
Макс. длина заготовки MAXL - 300см.
Макс. кол-во упаковок каждого вида MAXK - считать бесконечным.
Макс. сумма длин заготовок умноженное на кол-во штук и кол-во упаковок MAXSUML - исходя из MAXK так-же считать бесконечным.
"Им будет не просто, тем кто полагается на истину авторитета, вместо того чтобы полагаться на авторитет Истины"
Джеральд Месси, Египтолог


Вернуться в Математика

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

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

    TopList