Страницы: 1
RSS
Равномерное распределение по столбцам количества по весу
 
Добрый день.

Следующая задача встала передо мной:
Условно имеется 125 товаров, их нужно распределить по 3 столбцам максимально равномерно. Казалось бы все просто, каждый столбец получит по ~42 товара. Однако у товара есть вес, на который необходимо обратить внимание.
  • 25 товаров имеют вес 1 кг каждый
  • 25 товаров имеют вес 2 кг каждый
  • 25 товаров имеют вес 5 кг каждый
  • 25 товаров имеют вес 10 кг каждый
  • 25 товаров имеют вес 15 кг каждый
Нужно максимально равномерно распределить 5 видов товаров общим весом в 825 килограмм между 3 столбцами по весу.
При том, 1 вид товара не может быть сразу в двух столбцах, а только в одном. т.е. все товары весом 1кг могут быть только в одном столбце.

Задачка заумная и я уверен, что реализовать её на VB можно было бы быстрее, но я в нём дуб дубом, прошу вашей помощи, эксперты.
Изменено: Delta-Dude - 24.10.2016 21:32:30
 
Цитата
Условно имеется 100 товаров
А перечислили 125
 
Был вариант при большом количестве видов товара (а их более 1000) расположить их по весу по возрастанию и делать выборку:

1 ряд товары 1 4 7 10 ...
2 ряд товары 2 5 8 11 ...
3 ряд товары 3 6 9 12 ...

более менее равномерно выйдет, но это значит, что при добавлении нового товара с новым весом - съезжает весь список и перераспределять нужно весь товар, да и вариант чопорный. Каждый день жалею, что не учился на программиста =P ведь даже в школе на VB смог бы такое сделать, а сейчас уже все забыл..
 
Если вас устраивает фильтрация с сортировкой, но нет обновления, то может сводные таблицы подойдут?
Приложите файл примера, проще будет думать
 
Пример файла - 21 товар, 3 ряда, распределение по сортировке от большего к меньшему
В этом случае все равно получается сильная разница. К примеру, товар №19 весом 100 единиц можно было бы перенести из 1-ого ряда в 3-ий.
Изменено: Delta-Dude - 24.10.2016 21:33:12
 
в топике было 5 весов, а тут все разные?
 
В целом, количество не имеет особого значения, т.к. артикулов по факту более 1000, количество столбцов может быть от 3 до 10, главное найти способ оперативно их распихать по столбцам равномерно по весу.

Допустим у нас есть 1000 артикулов. У каждого артикула свой вес, всего 5 столбцов. Вес каждого артикула нам известен. Нужно, чтобы в каждом столбце общий вес был приблизительно одинаков. Т.е. если взять 1 товар каждого артикула, суммировать их вес, получить, к примеру 10000 кг, то в каждом столбце должно быть по ~2000 кг. При том, нужно разбить по столбцам именно артикула, а не количество общего товара.
 
Наконец сообразил, что же вы хотите на самом деле.
Есть одинаковые фуры, вагоны и т.п., грузоподъемность известна, надо их равномерно загружать. Единственное условие - чтобы одно наименование товара ехало в одной фуре. Так бы и написали сразу...
Это частный случай типичной "транспортной задачи" http://exceltable.com/otchety/reshenie-transportnoy-zadachi
но надо думать, как задать граничные условия
см. http://www.cyberforum.ru/ms-excel/thread1370738.html
 
Доброе время суток
Delta-Dude, что-то в вашем файле артикулов ограничений не нашёл, а так можно простейшим "жадным" алгоритмом реализовать.
Успехов.
 
Добрый день, Андрей. Благодарю, бегло посмотрел, вроде все как задумано, но толком не успел разобраться (сложновато пока для меня)

Обязательно детально изучу чуть позже, большое спасибо!
Изменено: Delta-Dude - 25.10.2016 11:06:27
 
Цитата
Андрей VG написал: "жадным" алгоритмом
Андрей, у тебя шибко жадный алгоритм. Товара всего 10500, а ты распределил аж 154000.
Может что-то не так понял?
"..Сладку ягоду рвали вместе, горьку ягоду я одна."
 
Доброе время суток
Цитата
Владимир написал:
а ты распределил аж 154000.
Распределение идёт по каждой строке. Алгоритм, добавляем товар в ряд у которого предыдущая накопленная сумма наименьшая. Таким образом, для каждой строки товара имеем сумму весов товаров на текущий момент. Если выделить последнюю строчку по рядам, то получим сумму 10500 - как и должно быть :)
 
Андрей VG, ознакомился с Вашим вариантом, спасибо, выручили! Разобрался как работает, правда не без помощи Вашего комментария

Цитата
Андрей VG написал:
Распределение идёт по каждой строке. Алгоритм, добавляем товар в ряд у которого предыдущая накопленная сумма наименьшая. Таким образом, для каждой строки товара имеем сумму весов товаров на текущий момент. Если выделить последнюю строчку по рядам, то получим сумму 10500 - как и должно быть

Задачка несколько усложнилась, после детальной проработки, а именно:

Есть 4 (либо другое значение, заданное заранее) столбца, в каждому может быть не более 6 артикулов (либо другое значение, заданное заранее). У каждого артикула есть вес. Суммарный вес всех артикулов каждого столбца должен быть более или менее равен. (это Вы уже помогли реализовать)

В любой момент может быть добавлен новый артикул. Необходимо определить в какой столбец его следует разместить, чтобы вес между столбцами был более менее равен, при условии, что все артикула перераспределять нельзя, максимум можно переместить между столбцами 3 артикула (либо другое значение, заданное заранее). Либо может измениться вес текущих артикулов, для каких-то незначительно (в 0.1-0.5 раза), для каких-то значительно (в 2-3 раза), тогда необходимо понять как перераспределить артикула наилучшим способом между столбцами, для уравнивая веса, при том же условии, что все артикула перераспределять нельзя, максимум 3 артикула (либо другое значение, заданное заранее).

Подскажите, пожалуйста, есть ли какие-либо варианты это выполнить, не прибегая к VB? возможно кто-то другой также знает решение, обращаюсь к Вам, господа, мои познания Excel пока чуть выше базовых и оперируя теми формулами и инструментами, с которыми я уже работал, не могу придумать способа решения вопрос без привлечения VB (с которым также знаком несильно)
Изменено: Delta-Dude - 26.10.2016 17:29:09 (Уточнение и добавление файла)
 
Я в задачу не вникал. Помощники, вопрос по теме?
 
Какова конечная цель?
Задача похожа на задачу упаковки в контейнеры/задачу о рюкзаке и т.п.
Самый простой способ (жадный алгоритм) уже предложили, но можно более глобально и качественно решить задачу если понять ее суть.
 
Цитата
Delta-Dude написал:
Допустим у нас есть 1000 артикулов.
Можете привести пример реальных данных на 1000 артикулов?
 
MCH, прикрепляю пример: 1000 артикулов, у каждого свой вес. Всего 25 столбцов (на практике, количество столбцов может быть разным, но обычно не более 50 артикулов в одном столбце)

В данном примере получается, что если распределять просто по количеству, то в каждом столбце может быть 40 артикулов и 10 свободных ячеек под артикула. В остальном все также. Безболезненно, без остановки бизнес-процесса, мы можем перемещать не более 10 артикулов между ячейками, в случае, если вес артикула изменяется в течении нескольких часов.

Т.е. к примеру, если мы имеем 2 столбца всего и их нужно уровнять. В них по 40 (из 50) артикулов, мы можем 10 артикулов одного, перенести в другой столбец и получится в одном столбце 30, в другом 50. Либо перенести 7 артикулов в один столбец, а из другого перенести 3, получится, что в первом 36, а в другом 43.

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

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

Настраиваемые параметры (в идеале): Количество столбцов, максимальная вместимость столбцов, желательная вместимость столбцов (чтобы один не был забит под завязку, а другой почти пустой), максимальное количество перемещений.
Изменено: Delta-Dude - 27.10.2016 12:18:43
 
Под понятием "конечная цель" я имел в виду, для чего это нужно, какой физический смысл у задачи? (распределение грузов или что-то другое)

Какой можно предложить алгоритм:
Если Вас устраивает качество распределение, которое дает "жадный" алгоритм, то вначале распределяем веса "жадным" алгоритмом
(на этих исходных данных он дает хорошее распределение, т.к. очень много величин малого веса)

Далее при добавлении нового элемента, добавляем его в столбец имеющий наименьший суммарный вес либо где меньше всего элементов (при равных весах).

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

Лучше все это сделать с помощью макросов.
 
MCH, конечная цель распределение веса продукции между секциями сборки товаров. Если в одной секции на линии сборщик собирает товары с большим весом - устает быстрее и замедляет работу, тем самым тормозит общую сборку. Поэтому ищу способ руками распределить нагрузку между сборщиками, чтобы все были в равных условиях.
 
Цитата
Delta-Dude написал:
устает быстрее и замедляет работу, тем самым тормозит общую сборку
Тогда чем плох "жадный" алгоритм? Как раз с утра пока в силе - самые тяжёлые, а потом всё легче и легче :)
 
Андрей VG, товар идет непрерывно на протяжении всей смены. Товар идет по артикулам, но в первой партии артикул 0001 может весить 20кг, а во второй партии 30кг. За время смены партий может проходить много и вес может меняться, поэтому заранее распределить вес и работать не выходит, т.к. он постоянно изменятся и нужно корректировать без массовых перемещений.
Изменено: Delta-Dude - 02.11.2016 10:42:25
Страницы: 1
Наверх