Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Число сочетаний с поиском максимально близкого к определённому значению
 
#1
21.03.2022 20:17:55
Общий смысл:
Необходимо изготовить 100 деталей различной длинны. Длинна заготовки 6000 мм. необходимо оптимально разложить детали, что бы получить минимальный отход. Оставшиеся детали оптимально разложить на следующей заготовке и т.д.

Конкретнее:
Есть 100 различных значений (могут повторяться).
Необходимо найти значения, сумма которых, будет максимально близка к определённому значению. Выписать все значения и удалить их из общего списка.
С оставшимися значениями проделать процедуру описанную выше.

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

Пример приложил.
Изменено: Лилиенталь - 21.03.2022 20:22:32
 
 
 
#2
21.03.2022 22:19:25
Тоже интересует, смотрю за веткой.
У меня по аналогии схема распиловки деревянных балок для стропильной системы скатной кровли.
Обычными формулами даже мысли нет как делать.
Пока понятен только результат:

Доска 1, 6000мм = 3700мм+1200мм+1100мм+ Отход 0мм
Доска 2, 6000мм = 3700мм + 2200мм + отход 100мм
Доска 3, 6000мм = 2500мм+2500мм + 800мм + отход 200мм
и т.д. пока не будут задействованы все размеры

при Этом, если в стране пропала доска 6м (или доску 3м предлагают в 2 раза дешевле) - то нужно быстро сориентироваться сколько нужно доски 3м (и сколько элементов длиннее 3м, чтобы по ним заложить еще доски на сращивание + вытекающие расходы на крепеж, работу и тп

в прикладном плане так: в расчете получилось что достаточно N досок и есть таблица раскроя. Затем доски приезжают на стройку и нумеруются. Рабочий смотрит на таблицу, ищет номер доски и размечает. другой рабочий пилит и складирует по типоразмеру + подписывает. Кровельщик по месту пилит только примыкания от углов
Изменено: Констатин Л - 21.03.2022 22:30:58
Лучше пишите на почту)
 
 
 
#3
21.03.2022 22:52:06
Цитата
Констатин Л написал:
Доска 1, 6000мм = 3700мм+1200мм+1100мм+ Отход 0мм
а толщину пропила учитывать не нужно? а то детали окажутся коротковатыми
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#4
21.03.2022 22:53:45
нужно, еще и угол спила. сейчас схему вытащу из ревита.
ТС тоже учитывает. 2мм как понял судя по размерам  
Изменено: Констатин Л - 21.03.2022 22:55:51
Лучше пишите на почту)
 
 
 
#5
21.03.2022 22:55:01
Цитата
Лилиенталь написал:
Есть 100 различных значений (могут повторяться).
если повторяются - уже не различные(((
вы заготовку на детали будете пилить лазерной установкой с нулевой шириной луча или у пропила известна ширина?
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#6
21.03.2022 23:32:58
С учётом пропила. В макросе он учитывается "толщина реза". Пилить пилой. Материал швеллер, труба, профильная труба, пруток. Для лазерного станка используем специальную прогу и получаем лист раскроя.

Предполагаю что с помощью массива скорость обработки данных увеличится, но принцип перебора данных в массиве и выдачи его наилучшего результата мне не ясен.
Изменено: Лилиенталь - 21.03.2022 23:41:37
 
 
 
#7
21.03.2022 23:40:43

Так наглядно в чем дело, но по сути это просто усложнение задачи ТС
Лучше пишите на почту)
 
 
 
#8
21.03.2022 23:59:23
стандартно задача раскроя линейного (арматура, труба, профиль и пр.) материала на детали выглядит так:
есть базовая длина заготовка (часто 6 м)
есть  ширина пропила
есть множество деталей с двумя параметрами длина и количество
задача: определить минимально необходимое количество заготовок для изготовления заданного ассортимента деталей
-------------------
решение делится на 2 части
1. определяются все возможные схемы раскроя (сколько и каких деталей можно сделать из одной заготовки). таких схем может оказаться сотни, тысячи и десятки тысяч (в каждой такой схеме остаток меньше длины самой короткой детали или вообще равен 0)
2. собственно решение: определяется сколько заготовок по какой схеме разрезать чтобы в итоге получить полный набор деталей (а порезанных заготовок минимум)
Изменено: Ігор Гончаренко - 22.03.2022 00:10:20
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#9
22.03.2022 00:40:23
Решение приложено в первом посте. Но там у меня использовано 20 деталей это около миллиона комбинаций. Время работы макроса 13 сек. При большем количестве (нужно до 100 деталей), это мин. 100891344545564193334812497256 комбинаций.

Поэтому я спрашиваю может есть другой способ перебора? Отличного от моего?
 
 
 
#10
22.03.2022 01:06:46
да существует тысячи других способов
обьясните что за задачу с сотней деталей вы решаете
я напишу вам что получилось у меня и сколько времени заняли расчеты
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#11
22.03.2022 07:34:02
Есть конструкция, сборочно-сварная, которое состоит из множества деталей. Материал деталей одинаковый (предположим швеллер). Но материал может меняться. Это необходимо для подсчёта веса.
Размер деталей 1200мм-4шт, 850мм-4шт, 760мм-5шт, 230мм-1шт, 185мм-7шт.
Заготовка 6000 мм или 4000 мм (она должно быть изменяемой)
Задача:
1-посчитать сколько необходимо выдать материала со склада (мин.  кол-во заготовок и общий вес выдаваемого материала) что бы изготовить детали.
2-сообщить сколько останется от каждой заготовки после отрезки деталей (для возможности использовать в дальнейшем).
3-всю информацию вывести на лист, где будет сказано какие детали необходимо отрезать от каждой заготовки, а так же первые 2 пункта.
Изменено: Лилиенталь - 22.03.2022 08:02:29
 
 
 
#12
22.03.2022 08:02:31
Цитата
Лилиенталь написал:
Задача:
По вопросам:
1. 3 - 6ти метровых или 4 - 4х метровых
2. и 3. - см. вложение (ширину реза указал - 3 мм)

Цитата
Лилиенталь написал:
Но там у меня использовано 20 деталей это около миллиона комбинаций. Время работы макроса 13 сек
Данную задачу можно решить за доли секунды: перебрать все комбинации, и выбрать нужные схемы раскроя

Пример работы линейного раскроя, можно посмотреть здесь: http://www.excelworld.ru/forum/3-21304-1

PS: Есть готовые программные решения которые делают линейный раскрой, есть как бесплатные, так и платные
Качество раскроя может быть разным

PPS: Можете приложить свои данные, даже очень сложные, раскрою любой (разумный) набор данных
Варианты используемых алгоритмов: жадный алгоритм, решение задачи о рюкзаке (сумма подмножеств), линейное программирование с перебором всех вариантов раскроя
Совокупное сочетание данных алгоритмов может дать приемлемый результат по скорости решения и качеству раскроя.
Изменено: MCH - 22.03.2022 08:08:29
 
 
 
#13
22.03.2022 08:13:30
Цитата
Констатин Л написал:
при Этом, если в стране пропала доска 6м (или доску 3м предлагают в 2 раза дешевле) - то нужно быстро сориентироваться сколько нужно доски 3м (и сколько элементов длиннее 3м, чтобы по ним заложить еще доски на сращивание + вытекающие расходы на крепеж, работу и тп
Могу помочь с выбором
Приложите реальный набор данных, стыковки углов у меня нет, над этим нужно поработать, а так смогу раскроить даже сложные наборы данных
Изменено: MCH - 22.03.2022 08:14:21
 
 
 
#14
22.03.2022 11:41:11
В #7 пример, а по поводу стыковки - там все просто:
перехлест на стыке 800мм, соотв для доски 8500 нужна целая 6м + обрезанная по типу остальных(2500+800=3300). Это могу просто формулами переводить в длины менее длины заготовки с получением кол-ва целых заготовок
Лучше пишите на почту)
 
 
 
#15
22.03.2022 12:00:18
MCH, спасибо за предоставленную ссылку. То что нужно.

Написал Вам сообщение, в личку, по вопросу доработки Вашего решения моей задачи. Прошу ответить.
Изменено: Лилиенталь - 22.03.2022 14:00:12
 
 
 
#16
23.03.2022 15:15:59
МСН, спасибо за готовое решение по ссылке. работает идеально. лучшее чем мог себе представить.
Варианты оптимизировать остатки (с учетом возможности использовать перехлест и сращивание) буду искать в июле, обязательно обращусь.
Лучше пишите на почту)
 
 
 
Страницы: 1
Наверх