Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1 2 След.
RSS
Распределение ящиков по заданному числу машин с минимальным перемешиванием товаров
 
#1
10.11.2020 20:29:25
Всем привет.
Пытаюсь решить следующую задачу. Есть несколько разных товаров. По каждому товару известно кол-во ящиков. Их надо распределить по машинам. Все машины имеют одинаковую вместимость (55 ящиков). Кол-во машин ограничено (это минимальное кол-во, достаточное для перевозки всех ящиков).
Необходимо распределить ящики по машинам так, чтобы каждый товар находился в наименьшем количестве различных машин. Для товара с 30 ящиками идеально разместиться в 1 машине. Для товара с 60 ящиками - в 2 и т.д.

Не могу придумать, как это решить средствами Excel (как, впрочем, и любыми другими)
Изменено: Volounteer - 10.11.2020 21:31:41
 
 
 
#2
10.11.2020 21:24:05
Доброе время суток
Цитата
Volounteer написал:
Не могу придумать, как это решить средствами Excel.
Тогда хотя бы поделитесь сокровенным знанием - как это решать, например, на листе бумаги ручкой.
 
 
 
#3
10.11.2020 21:31:22
Андрей VG, к сожалению, не знаю. Наверное стоило уточнить это в стартовом посте
 
 
 
#4
10.11.2020 22:17:53
Цитата
Volounteer написал:
к сожалению, не знаю
Вариант на листе бумаги нарисовал. Варианта формулами в Excel нет.
 
 
 
#5
10.11.2020 22:34:11
gling, спасибо.
Видимо, придётся так и распределять вручную.
 
 
 
#6
10.11.2020 22:52:20
формулА отсутствует, формулЫ,  да простят меня гуру, есть  :)
Изменено: buchlotnik - 10.11.2020 22:55:56
Соблюдение правил форума не освобождает от модераторского произвола
 
 
 
#7
10.11.2020 22:59:07
buchlotnik, спасибо!
С ходу не осилить, буду разбираться)
 
 
 
#8
10.11.2020 23:03:53
есть формула, нашел у себя в гараже между пустыми банками от масла, еще немного и выкинул бы
Код
=ЕСЛИ(СЧЁТЕСЛИ($B$7:$B$28;">" & $B$1)>=C$5;ЕСЛИ(И($B7>=$B$1;СЧЁТЕСЛИ($B$7:$B7;">" & $B$1)=C$5);$B$1;);МИН($B7-СУММ(B7:$C7);$B$1-СУММ(C$6:C6)))
см.вложение
Изменено: Ігор Гончаренко - 10.11.2020 23:04:44
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#9
10.11.2020 23:16:56
Ігор Гончаренко, не - так бьёт не оптимально из условия
Цитата
Volounteer написал:
каждый товар находился в наименьшем количестве различных машин
Соблюдение правил форума не освобождает от модераторского произвола
 
 
 
#10
10.11.2020 23:41:21
ок добавил 1 ЕСЛИ
все, что помещается в одну машину, уедет одной машиной (или может в конце не поместиться, если количество коробок довольно близко к количеству мест в машинах)
Код
=ЕСЛИ(СЧЁТЕСЛИ($B$7:$B$28;">"&$B$1)>=P$5;ЕСЛИ(И($B20>=$B$1;СЧЁТЕСЛИ($B$7:$B20;">"&$B$1)=P$5);$B$1;);ЕСЛИ($B20-СУММ($C20:O20)<$B$1-СУММ(P$6:P19);$B20-СУММ($C20:O20;)))
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#11
10.11.2020 23:57:51
del
Изменено: buchlotnik - 23.08.2021 17:50:41
Соблюдение правил форума не освобождает от модераторского произвола
 
 
 
#12
11.11.2020 00:38:03
Цитата
buchlotnik написал:
до кучи жадный PQ
Привет, Михаил.
Не лучшая реализация, если вот так, то всё же нужно соблюсти и вот этот пункт, если быть пунктуальным :)
Цитата
Volounteer написал:
Кол-во машин ограничено (это минимальное кол-во, достаточное для перевозки всех ящиков).
 
 
 
#13
11.11.2020 00:54:23
Цитата
Андрей VG написал:
Не лучшая реализация
а пример лучшей реализации будет?  :)
Соблюдение правил форума не освобождает от модераторского произвола
 
 
 
#14
11.11.2020 07:51:30
Цитата
buchlotnik написал:
а пример лучшей реализации будет?
Ну, я думал, что ваш тёзка MCH откликнется - был ведь. Вечерком набросаю несколько более продвинутую версию "жадности", но в VBA :)
Изменено: Андрей VG - 11.11.2020 07:51:45
 
 
 
#15
11.11.2020 08:01:35
спасибо, буду ждать, но потом все равно на PQ перепишу  :)
Соблюдение правил форума не освобождает от модераторского произвола
 
 
 
#16
11.11.2020 08:47:12
Цитата
Андрей VG написал:
Ну, я думал, что ваш тёзка  MCH  откликнется
Для меня тема интересная.
Алгоритм решения задачи вижу такой:
Определяем минимальное количество машин: округлвверх(суммарное количество/вместимость)
Груз, который больше вместимости в одну машины разделяем, 60 ящиков это 55+5 (но можно разделить и 50+10 или 45+15 и т.п.)
Далее задачу сводим к задаче раскроя (упаковки в контейнеры) любым из алгоритмов.

В данном случае 718 ящиков очень легко распределить на 14 машин, подойдет и жадный алгоритм
Если  не получается распределить груз на 14 машин, то нужно принимать  решения, какой груз разделяем по машинам и какое решением будет  приемлемым.
(например если весь товар по 30 ящиков, то невозможно его без разделения упаковывать в машины вместимостью 55)

Во вложении пример полуручного  распределения груза по 14 машинам, в первом варианте распределяем по  максимуму первые 13 машин, остаток в 14ю
во втором варианте распределяем груз равномерно, 4 машины по 52 ящика и 10 машин по 51 ящику
 
 
 
#17
11.11.2020 11:10:02
Цитата
Андрей VG написал:
Не лучшая реализация, если вот так
По данному примеру данных приходится распределять груз между машинами, чтобы все убралось в 14 машин
То, как я распределил - во вложении
 
 
 
#18
11.11.2020 21:25:36
Всем, кто откликнулся - большое спасибо!

Цитата
MCH написал:
Далее задачу сводим к задаче раскроя (упаковки в контейнеры) любым из алгоритмов.
В этом слабо разбираюсь, прошу подсказки. Мне же нужно не упаковать остаток коробок в наименьшее возможное число машин, а распределить по имеющемуся числу авто таким образом, чтобы минимизировать "разрывы" одного товара между машинами. Кажется, что это разные вещи. И алгоритмы для раскроя решают первую, а не вторую. Хотя может я не понимаю, как одно свести к другому (нет навыка решения таких задач).
 
 
 
#19
11.11.2020 22:06:22
Цитата
Volounteer написал:
Кажется, что это разные вещи. И алгоритмы для раскроя решают первую, а не вторую.
Примеры распределения, которые я привел не оптимальны?
Они как раз и получены алгоритмом раскроя + небольшая эвристика когда необходимо распределять один товар по разным машинам
Цитата
Volounteer написал:
Мне же нужно не упаковать остаток коробок в наименьшее возможное число машин, а распределить по имеющемуся числу авто таким образом, чтобы минимизировать "разрывы" одного товара между машинами.
У Вас уже задано - наименьшее возможное число машин.
Если товары распределяются в указанные машины алгоритмом раскроя - то решение найдено
Если не распределяется, то необходимо разделять товар между машинами.
Минимальное количество распределяемого товара - это тот товар, количество которого больше вместимости машины
Далее пытаемся минимизировать количество разделяемого товара, здесь уже нужно думать над алгоритмом поиска оптимального (или приемлемого) решения
Изменено: MCH - 11.11.2020 22:15:49
 
 
 
#20
11.11.2020 22:54:41
MCH, спасибо, кажется сообразил про раскрой и дальнейшую эвристику.

Цитата
MCH написал:
Примеры распределения, которые я привел не оптимальны?
С примерами всё ок, они удовлетворяют условиям, спасибо.

Не подскажите какую-нибудь литературу, чтобы подтянуть теорию для решения подобных задач?
 
 
 
#21
12.11.2020 00:23:43
Цитата
MCH написал:
То, как я распределил - во вложении
Михаил, спасибо.
Криво - косонько, вариант альфа. Падает на 770 :)  Но худо-бедно что-то считает. И естественно, есть куда оптимизировать.
Цитата
MCH написал:
здесь уже нужно думать над алгоритмом поиска оптимального
А тут-то над чем думать? N! по остаткам и товарам, число ящиков которых, меньше меньше вместимости машины,- и решение будет найдено.
 
 
 
#22
12.11.2020 07:04:21
А вот и формульное решение поспело на втором листе:
=ЕСЛИ(И(СУММ(D$6:D6)<$B$1;СУММ($C7:C7)<$B7;МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6))>=ОСТАТ($B7;$B$1));МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6));)
Правда оптимальность зависит от порядка расположения значений. Сортировка по убыванию и по возрастанию даёт не самый оптимальный результат.
Надо немного доработать формулу.
На первом листе неудачные попытки оптимизации.
 
 
 
#23
12.11.2020 08:55:35
Цитата
Андрей VG написал:
А тут-то над чем думать? N! по остаткам и товарам
Ну мы же не знаем масштаб задачи, все что выше 15! уже не поддается перебору
Свое решение на 769 чуть улучшил

Хотелось бы понимать, на сколько велика задача в реальности, количество товара и машин существенно больше чем 22/14 или примерно столько же?
Изменено: MCH - 12.11.2020 10:39:06
 
 
 
#24
12.11.2020 09:02:53
Немного улучшил формулу. Для исходного и сортированного по убыванию даёт оптимальный результат (для имеющимся данных).
Формула массива:
=ЕСЛИ(МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6))=$B7-СУММ($C7:C7);$B7-СУММ($C7:C7);ЕСЛИ(И(СУММ(D$6:D6)<$B$1;СУММ($C7:C7)<$B7;МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6))>=ОСТАТ($B7;$B$1);$B8:$B$28-МУМНОЖ(Ч(+$C8:C$28);ТРАНСП($D$5:D$5^0))<>МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6)));МИН($B7-СУММ($C7:C7);$B$1-СУММ(D$6:D6));))
Изменено: Светлый - 12.11.2020 09:03:22
 
 
 
#25
12.11.2020 09:26:54
Цитата
Светлый написал:
даёт оптимальный результат (для имеющимся данных)
Сергей, исходный набор данных - 718 ящиков на 14 машин достаточно простой в распределении
Значительно сложнее распределить 769 ящиков на 14 машин с наименьшим распределением по различным машинам
Скрытый текст
 
 
 
#26
12.11.2020 09:51:22
Коллеги, а рассматривался ли вариант с поиском решения в несколько итераций?
Сначала раскладываем каждый товар в свою машину(ы), а затем в несколько шагов пытаемся сократить количество машин до минимума, перекладывая самые большие партии товара на свободные места в других машинах... Альтернативный способ: наоборот последовательно разложить весь товар в минимальное суммарное число машин, а затем сортировать его между машинами для достижения более оптимального размещения. А-ля визуализация процесса дефрагментации жесткого диска.
Это также позволяет управлять приоритетами условий в решении задачи: что важнее разложить каждый товар по минимальному числу машин или перевезти весь товар наименьшим количеством машин...  
 
 
 
#27
12.11.2020 11:03:00
Цитата
IKor написал:
Коллеги, а рассматривался ли вариант с поиском решения в несколько итераций?
Я собственно так и решал (в несколько итераций)
1. определяем количество машин
2. определяем, минимальное количество товаров которые нужно распределять (те, что не влезают в одну машину)
3. алгоритмом, подходящим для линейного раскроя пытаемся распределить груз с учетом определенного минимума к разделению груза между машинами
4. если на шаге 3 не удается найти решение, то пытаемся найти решения для разделения товаров в количестве min+1 (и т.д. до получения результата)
 
 
 
#28
12.11.2020 17:09:03
Решил поупражняться на случайных данных, 769 ящиков на 14 машин
Если у кого нибудь получится найти адекватный алгоритм, сравните с найденными мной решениями
Изменено: MCH - 12.11.2020 17:10:07
 
 
 
#29
13.11.2020 09:00:10
Данную задачу можно свести к решению линейным программированием
Где целевой функцией будет минимизация стыков (распределения одного товара по разным автомобилям) при заданном количестве автомобилей.

Пример "ручного" построения модели во вложении, построенную модель решал уже через OpenSolver
Теоретически решение задачи можно полностью автоматизировать и будет гарантированно найден оптимальный вариант (минимизация количества стыков).
Изменено: MCH - 13.11.2020 09:27:39
 
 
 
#30
13.11.2020 10:24:36
Цитата
Ігор Гончаренко написал:
помещается в одну машину
А попробуйте задать ровно 55 ящиков какого-нибудь товара в файле из сообщения #10.
В формуле все ">"&$B$1 надо заменить на ">="&$B$1.
*И что делать, если товара больше, чем на две машины?
Изменено: Светлый - 13.11.2020 10:48:06
 
 
 
Страницы: 1 2 След.
Наверх