Конференция VBStreets

**Joo** » 25.03.2012 (Вс) 14:21

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

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

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

**Хакер** » 25.03.2012 (Вс) 14:36

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

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

**Joo** » 25.03.2012 (Вс) 14:40

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

Спасибо! Сейчас поищу.

**Sam777e** » 25.03.2012 (Вс) 17:29

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

**Qwertiy** » 25.03.2012 (Вс) 17:47

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

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

**Joo** » 25.03.2012 (Вс) 18:34

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

нет, может и разное быть

**Qwertiy** » 25.03.2012 (Вс) 21:25

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

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

**Qwertiy** » 25.03.2012 (Вс) 21:35

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

**Proxy** » 25.03.2012 (Вс) 22:42

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

**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** » 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** » 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 так-же считать бесконечным.

Конференция VBStreets

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

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

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

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

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

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

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

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

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

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