Помогите в решение задачи #349199

Есть болванка длинной L Из нее пилятся детали длинной (A1, A2, A3, ..... An) Максимальное количество каждой детали (B1, B2, B3, .....Bn) Сколько видов деталей не известно (n - переменная, нужено общее решение) При этом болванки на все детали не хватает. Нужно определить как оптимально распилить болванку так, чтобы остаток от распилки был наименьшим. Хочу понять принцип решения этой задачи. если кто-нибудь кинет ссылку с примером, буду весьма благодарен.

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

Не генетические, а эмпирические

да хрен его разберет, как они называются - не помню, короче суть этих алгоритмов в том, чтобы заранее отбросить варианты, которые в некую... ОДЗ, чтоли?... не входят.

А точное название алгоритма который здесь приемлим не подскажите? Я его погуглю может соображу чего...

Если не ошибаюсь, то оно:

Вопрос 1 - можно ли с одной болванки выпилить разные детали ?? Если да то ты получиш следуе тебе надо найти минимально значение из следующих уравнений L - B1*A1 - B2*A2* - .... - Bn*An = Ost (где Ost - это остаток от болванки - причем он должен быть больше или равен нулю)

Перебором могу, но в некоторых случаях может очень долго считаться.

детали можно пилить разные сколько каких угодно в пределах их максимального количества.

В екселе есть сервис-поиск решения. Если в сервисе его нет, надо в сервис-надстройки его добавить. Там такая задача за 5 мин при владении этим инструментом.

+6 Это все понятно. Непонятно как это решить :)

а все комбинации перебирать смысл есть? если остается огрызок в сантиметр, с самая малая деталь - 10 см?

по этому я про "нечестный" вариант и упомянул

Про ексель знаю. Пробовал. Правда нифега не получилось, он мне дробные значения выдавал. Как ему указать что решения должны быть целыми? Да и не совсем мне решение в екселе подходит, мне нужно алгоритм в 1Ске реализовать.

нормальные люди, всмысле технологи не занимаются этим... каждую заготовку режут на одинаковые части, это технологически проще

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

Там ограничения есть в поиске решений. Выбираешь ячейку, ставишь целое.

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

А чем вариант перебора не нравится, не такие-то и большие данные, чтобы изощряться?

Если я не ошибаюсь, это вариация задачи о рюкзаке. Решений этой задачи можно нагуглить массу.

Сколько заготовок разных размеров?

+

задача о распилке рюкзака? О_о

Ну, собственно, распил, это процесс обратный укладыванию.

не оптимальный, но шустрый  и достаточно экономичный метод 1. отсортировать отрезки по убыванию 2. пилить сначала самые большие, потом меньше и так до тех пор пока остаток болванки не меньше самого мелкого отрезка.

Очень не оптимальный ...

хм, есть практика применения или сравнения?

Перебор если деталей мало. Другие методы если перебор не подходит.

Ну, вообще от частного случая зависит, конечно. Вредставь себе ситуацию: балка 5 метров, А1 = 3м, А2 = 3 см. В1,В2 = очень много.

+ Хотя нет, вру, здесь как раз все хорошо будет. Плохо будет если, скажем, А2 = 2.4 м.

Ну и получишь на каждую балку 1 шт. А1 + 66 шт. А2 потом пойдут либо все по А1, либо все по А2

Тоже не айс вариант :) думай дальше

Написал уже в , что соврал. В общем, такой алгоритм не очень хорош, когда длины всех деталей до порядка сравнимы с длиной балки. Но, с другой стороны, в этом случае легко полный пербор сделать.

Что не айс то? В случае твой алгоритм дает остаток 2 м., против 0.2 для оптимального решения.

а если не торопиться с выводами?

Брррр ... поясни? Может и правда туплю под вечер?

разбери на примерах 2 А1 + 5 А2 3 А1 + 2 А2

А причем тут эти примеры? Я привел пример L = 5, А1 = 3, А2 = 2.4, на котором твой алгоритм дает решение десятикратно хуже оптимального. Что в ЭТОМ примере не айс?

Э, может я не догоняю. Но разве заранее не известно, что нужно столько-то деталей длиной А1 и столько-то деталей А2?

Не столько-то и столько-то, а не более стольки-то и не более стольки-то.

+ По крайней мере автор так сформулировал.

Тогда какая-то неформализованная задачка получается количество болванок - ограниченно?

"количество болванок - ограниченно?" По условию вроде как одна ...

ндя, я тогда вообще мимо :)

Всем спасибо за ответы. Моя задача, насколько я понял, действительно похожа на задачу про укладку рюкзака, если ценность предметов укладываемых в рюкзак приравнять к размеру детали (вес и ценность будут одинаковыми), но в по условиям задачи "Каждый предмет из множества можно выбирать бесконечное кол-во раз" а у меня максимальное количество деталей одного вида ограничено. Не совсем подходит... буду дальше искать. Зарание неизвестно, может быть и 1 (тогда собственно и нечего было бы заморачиваться, а может быть и 10 и 15) Верно.

Это классическая задача по расиливанию бюджета, решается интуитивно, а если не в целых числах то симплекс методом

. Используй вариацию задачи о рюкзаке с возможностью единичного выбора предмета (см. ). В твоем случае возможность выбора не более B1 штук детали А1 надо просто контролировать тем, что в общем наборе находится ровно В1 как бы РАЗНЫХ (а на самом деле просто дубликатов) деталей А1.

Это задача о одномерном раскрое, вроде решается методом ветвей и границ, я даже как то лабораторные делал по ней (не себе)...

Благодарю, попробую попробую этим методом порешать, пример вроде нашел...

1. Аналог задачи о рюкзаке. В подавляющем числе случаев неплохо решается "жадным" алгоритмом (см.24). 2. Метод ветвей и границ не даст сокращения перебора, т.к. коэффициенты целевой функции и ограничения (по длине) совпадают. 3. Можно попробовать решать с помощью производящей функции: f(x) = ПРОИЗВЕДЕНИЕ(1+x^Ai+x^2Ai+...+x^Bi*Ai) Если раскрыть скобки и привести подобные члены, то коэффициент при x^L даст число решений уравнения: СУММА(Ai*xi)=L при ограничениях 0<=xi<=Bi, xi - целое. Может быть работоспособен, когда Ai - соизмеримые, не слишком большие числа. 4. Занимался раскроем рулонов металла на продольно-поперечных станках. Есть соображения по вашей задаче (метод ветвей и границ после некоторого препроцессинга), немного в иной постановке, а именно: минимизировать количество болванок при условии выполнения задания (B1,В2,...,Bn). На реальных задачах раскроя выход был около 98%. Если дело стоящее, готов обсудить (тел. 980-2417) и поднять (если удастся) метод (писал на Паскале под ДОС).

Спасибо за предложение. Задача уже решена. Работает вполне приемлемо :)

Написали бы хоть, как решаете.