Вход | Регистрация
    1  2   
1С:Предприятие :: 1С:Предприятие 8 общая

Оптимальное размещение на поддоне или задача о раскрое

Оптимальное размещение на поддоне или задача о раскрое
Я
   MistaEr
 
10.02.19 - 09:09
Всем доброго времени! Ко нибудь решал такую задачу? На поддон нужно разложить коробки оптимальным образом. коробки будут только в один ряд, т.е. нам важно только двумерное расположение.
 
 
   ДенисЧ
 
1 - 10.02.19 - 09:28
google://задача+о+рюкзаке
   Garykom
 
2 - 10.02.19 - 09:54
(0) Сколько платишь?
   MistaEr
 
3 - 10.02.19 - 10:23
(2) Мне не готовый код нужен, а хотя бы идея
   Михаил Козлов
 
4 - 10.02.19 - 10:23
(1) О рюкзаке не подойдет.
Поддоны разные, сколько типоразмеров?
Сколько типоразмеров коробок?
Коробки можно переворачивать, или низ определен?
   Garykom
 
5 - 10.02.19 - 10:34
(3) Дам даже две идеи:
1. Изучить и написать самому
2. Нанять кто уже изучил, за денежку
   MistaEr
 
6 - 10.02.19 - 10:36
(4) Поддоны одинаковые. Высота коробок всегда одинакова, поэтому высоту не рассматриваем. Встречаются одинаковые коробки.Попробую объяснить так. Коробки это слова, разного шрифта и разной длины, на строчке желательно писать слова одного шрифта, максимальное количество слов на строчку. Лист куда пишем может быть или альбомной ориентации или портретом
   Garykom
 
7 - 10.02.19 - 10:37
(6) Таблички/вывески делаете?
   Garykom
 
8 - 10.02.19 - 10:40
Начни с тупого полного перебора всех вариантов.
Если "коробок" на "поддоне" меньше ста это вполне вменяемое время.
   MistaEr
 
9 - 10.02.19 - 10:41
(7) нет, именно поддоны
   MistaEr
 
10 - 10.02.19 - 10:44
Длина в степени ширина?
 
 Рекламное место пустует
   Garykom
 
11 - 10.02.19 - 10:45
КоличествоКоробок!
   Garykom
 
12 - 10.02.19 - 10:45
   Михаил Козлов
 
13 - 10.02.19 - 10:47
(6) Если правильно понял, набор "коробок" неизвестен.В каждом случае свои.
Пробовал давно (лет 25 назад) аналогичное делать для раскроя металла, результат был так себе (средний выход был примерно 80%).
Да и идеи особой не было: какая-то реализация схемы ветвей и границ.
Обычно оператор с этим справляется неплохо: что-то типа тетриса.
   Garykom
 
14 - 10.02.19 - 10:48
Сорри я ошибся с "меньше ста", там уже после 10 коробок цифры не вменяемые количество вариантов для полного перебора.
   Garykom
 
15 - 10.02.19 - 10:49
(13) Тут как понял упрощение есть что часть коробок одинаковые
   MistaEr
 
16 - 10.02.19 - 10:55
(15) Но есть усложнение, желательно в одну строчку одинакового шрифта
   Garykom
 
17 - 10.02.19 - 10:57
(16) Это еще упрощение же, меньше вариантов.
   Mikeware
 
18 - 10.02.19 - 11:08
"коробки это слова"©
Да, алкоголь - действительно зло
..
   MistaEr
 
19 - 10.02.19 - 11:09
(18) Не пью, а может стоит начать) Я уж пытался оъяснить как мог
   Mikeware
 
20 - 10.02.19 - 11:11
(19) ну так критерий оптимизации - какой?
   Михаил Козлов
 
21 - 10.02.19 - 11:14
Есть классическая работа Канторовича по раскрою фанеры.
Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов.
https://www.studmed.ru/kantorovich-lv-zalgaller-va-racionalnyy-raskroy-promyshlennyh-materialov_a38c352d1f8.html
но мне кажется там другая задача, т.к дело сводится к задаче линейного программирования.
В любом случае нужно в Инете поискать.
   MistaEr
 
22 - 10.02.19 - 11:19
(14) Да, немало
Факториал = 1;
    Для а = 1 По 10 Цикл
        
        Факториал = Факториал*а;
        
    КонецЦикла;
   MistaEr
 
23 - 10.02.19 - 11:28
Если даже пользователь будет готов подождать, понятия не имею как обходить свой ТЗ

Длина|Ширина|Количество
   Mikeware
 
24 - 10.02.19 - 11:34
(21) у Канторовича понятен критерий оптимизации. Что является критерием у ТС - неизвестно.
   Garykom
 
25 - 10.02.19 - 11:35
Сначала сгруппируй свои коробки в три вида групп:
1. Одинаковые
2. Одной длины
3. Одной ширины

Затем отсортируй внутри групп и начинай перебирать, укладывая в прямоугольник.
Укладка это записи в новую ТЗ, где координаты верхнего-левого угла каждой коробки и ссылка на описание коробки (номер из первой ТЗ)
   Garykom
 
26 - 10.02.19 - 11:37
(24) Угу одно дело засунуть в стандартные размеры (максимум коробок или их веса) и совсем другое засунуть все в минимальную площадь.
   Михаил Козлов
 
27 - 10.02.19 - 11:50
(24) Так же: минимум отходов. Если правильно понял задачу.
   MistaEr
 
28 - 10.02.19 - 11:56
(25)
Первая группа
h1 X a1 - 5шт
h2 X a2 - 8шт
h3 X a1 - 4шт

Вторая группа
h1 X a1 - 5шт
h1 X a2 - 3шт
h1 X a3 - 9шт

Третья группа
h1 X a1 - 5шт
h2 X a1 - 2шт
h3 X a1 - 4шт

НовСтр = ТЗ_Укладка.Добавить();
НовСтр.Коробка = ?

Ссылок у меня нет, работа только цифрами
   Mikeware
 
29 - 10.02.19 - 11:57
(27) далеко не факт. Кроме "расположить оптимальным образом" - критериев нет
   Mikeware
 
30 - 10.02.19 - 11:58
+(29) равно как нет и явно описанных ограничений ..
   MistaEr
 
31 - 10.02.19 - 12:09
(25) Не догоняю
   Mikeware
 
32 - 10.02.19 - 12:21
(31) ставь любые и хоть как - любое расположение будет оптимальным
   novichok79
 
33 - 10.02.19 - 12:23
 
 
   Злопчинский
 
34 - 10.02.19 - 12:27
http://www.packer3d.ru/online/pal-by-box

3д пакер

на ИС - у Ильдаровича есть решение задачи запросом.
я с ним контачил, оптимальности при укладке нескольких слоев даже в простом варианте не давала, но в один слой возможно разложит
   Злопчинский
 
35 - 10.02.19 - 12:29
да, вот она в 33 упомянута
   shotsdv2008
 
36 - 10.02.19 - 14:21
В экселе есть метод решения подобных задач, называется симплекс-метод
   ЕщеОдинПрограммист
 
37 - 10.02.19 - 15:58
Я подобные задачи решал перебором. Но тупо перебор это очень много, и там идут большие отсеивания вариантов, которые заведомо дальше не приведут к решению или к улучшению того что уже найдено. Для примера, исходное множество элементов сортируется по возрастанию размеров, и начинаем перебор. Если после заполнения некоторого объема следующий не влезает, значит все последующие то же не влезут. И лучше такое делать на компилируемом языке, а не на 1С, на порядки больше вариантом перебрать можно. И еще, если кол-во растановок больше чем можно перебрать, то можно делать перебор случайных вариантов и выбирать лучший из тех, что перебрались за отведенное время.
   ProxyInspector
 
38 - 10.02.19 - 16:38
В данных задачах нельзя искать самый лучший вариант. Достаточно найти не плохой вариант, который полностью определяется выбранным алгоритмом. К примеру разница в эфективности подбора варианта будет 1%, но улучшение на эти 1% потребует увеличение затрат на рассчет в 1000 раз. Смысла в этом нет.
   ProxyInspector
 
39 - 10.02.19 - 16:39
Я в свое время решал задачу оптимального бронирования гостинничного фонда. Достаточно простая задача
   ProxyInspector
 
40 - 10.02.19 - 16:43
Потом решал задачу оптимального размещения упаковок с водой на паллете при сборке розничных заказов. С учетос того, что имеется штук 30 типоразмеров упаковок с различной жесткостью и размерами. В результате алгоритм собирал паллеты на уровне лучших сборщиков. И никакого тупого перебора.
   ЕщеОдинПрограммист
 
41 - 10.02.19 - 17:11
(40) А какой перебор был? Без перебора? Т.е. существует алгоритм который может решать такие вещи без факториальной составляющей? Будет интересно почитать. 1%, или 5%, или 0.01% - где критерий, что именно этот процент будет проблемным? Все зависит от задачи, от критерия отбора вариантов, от реализации. Если комп может перебрать все варианты за 0.5 секунды, то зачем ему мешать и ограничивать? А если не может за час, то просто определяем, сколько ему позволительно считать, и вмещаем в это время все что сможем без оглядки на оставшиеся варианты. Если при этом отбирать без условно случайной выборки, то может оказаться, что перебор все это время перебирал область, где нет решений, а решения сидели группой где-то рядом.
   ЕщеОдинПрограммист
 
42 - 10.02.19 - 17:23
(40) тут даже может, что сделал этот алгоритм для одной организации. А потом приходиш в другую, той же фигней занимающеся. И эти новые говорят, а вот мы организация по крупней, у нас паллеты покрупней, и на них на пять коробочек больше помещается. И прежний алгоритм сядет в лужу, т.к. факториал от дополнительных пяти коробочек уже может оказаться не перебираемым.
   Михаил Козлов
 
43 - 10.02.19 - 18:46
(36) Симплекс-метод - один из методов решения задачи линейного программирования.
У автора другая задача.
   MistaEr
 
44 - 11.02.19 - 08:24
Я смотрю, задача многим понравилась, но никто или не решал или не подсказал как решать. Перебор не могу осуществить, для начала пусть даже он будет долгим.
   Mikeware
 
45 - 11.02.19 - 08:58
(44) чем размещение "3*4" будет оптимальней размещения "2*6"?
   MistaEr
 
46 - 11.02.19 - 09:20
(45) Больше площади займет на поддоне
   MistaEr
 
47 - 11.02.19 - 09:21
Теперь я уже просто хочу оптимальный ряд построить. т.е. одномерно.
   RomanYS
 
48 - 11.02.19 - 09:23
(44) Может для начала приведёшь входные условия(поддоны одинаковые?) и критерии оптимальности(минимальное количество поддонов для заданного набора коробок?)
   MistaEr
 
49 - 11.02.19 - 09:24
От меня до двери 12 метров. У меня есть палочки 
2м-3шт
4м-1шт
1.5м-2шт
2.5м-1шт

Какие выбрать палочки и расставить на эти 12м, чтоб расстояние без палочек осталось минимальным?
 
 Рекламное место пустует
   MistaEr
 
50 - 11.02.19 - 09:26
Ух пропустил я занятия про рекурсию)  так и не умею использовать
   MistaEr
 
51 - 11.02.19 - 09:49
ВЫБРАТЬ
    ВТ.Ширина
ПОМЕСТИТЬ ВТ
ИЗ
    &ВТ КАК ВТ
;

////////////////////////////////////////////////////////////////////////////////

ВЫБРАТЬ
    ВТ.Ширина,
    ВТ1.Ширина КАК Ширина1,
    ВТ2.Ширина КАК Ширина2,
    ВТ3.Ширина КАК Ширина3,
    ВТ4.Ширина КАК Ширина4,
    ВТ.Ширина + ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина + ВТ4.Ширина КАК Сумма
ПОМЕСТИТЬ ВТ_Рез
ИЗ
    ВТ КАК ВТ,
    ВТ КАК ВТ1,
    ВТ КАК ВТ2,
    ВТ КАК ВТ3,
    ВТ КАК ВТ4
ГДЕ
    ВТ.Ширина + ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина + ВТ4.Ширина <= 12
;

////////////////////////////////////////////////////////////////////////////////

ВЫБРАТЬ
    ВТ_Рез.Ширина,
    ВТ_Рез.Ширина1,
    ВТ_Рез.Ширина2,
    ВТ_Рез.Ширина3,
    ВТ_Рез.Ширина4,
    МАКСИМУМ(ВТ_Рез.Сумма) КАК Сумма
ИЗ
    ВТ_Рез КАК ВТ_Рез

СГРУППИРОВАТЬ ПО
    ВТ_Рез.Ширина,
    ВТ_Рез.Ширина1,
    ВТ_Рез.Ширина2,
    ВТ_Рез.Ширина3,
    ВТ_Рез.Ширина4

А здесь уже отбирать по количествам вхождений
   Михаил Козлов
 
52 - 11.02.19 - 10:01
(49) Это классическая задача о ранце (правда коэффициенты в критерии совпадают с коэффициентами в ограничении).
   Mikeware
 
53 - 11.02.19 - 10:04
(46) т.е. площадь суммы не равна сумме площадей? у вас какая-то отдельная математика?
   ProxyInspector
 
54 - 11.02.19 - 10:11
(49) В такой постановке задача совсем детская.
  Берешь самую длинную палку, потом самую длинную из тех которые помещаются и дальше по кругу.
   Вот и весь алгоритм.
Я уверен на для большого набора возможных палок в 99% случаев решение будет оптимальным. Особенно если рядов будет больше 2-х
   ProxyInspector
 
55 - 11.02.19 - 10:16
По поводу оптимального раскроя в 2D задача более интересная. Но и она в определенных приближениях решается в 30 строк кода. В этих приближениях 3х4 лучше чем 2х6
   MistaEr
 
56 - 11.02.19 - 10:48
(53) Не совсем понимаю, может на примерах?
   MistaEr
 
57 - 11.02.19 - 10:59
(54) согласен что в начале большие брать, но это не всегда оптимально. первый всегда самый длинный
   Вафель
 
58 - 11.02.19 - 11:00
(54) Это называется жадный алгоритм
   Mikeware
 
59 - 11.02.19 - 11:04
(56) есть 12 коробок, площадью 100 кв.см.
расположив эти 12 коробок в 3 ряда по 4 штуки это займет площадь 1200 кв см.
расположив 12 коробок в 2 ряда по 6 штук они займут площадь в 1200 кв.см.
почему какой-то вариант "больше площади займет на поддоне"?
-------------
впрочем,Ю критерии оптимальности у вас все-таки вытащили - минимальная незанятая плошадь.
и ограничения тоже - все коробки равноценные.
нет еще одного ограничения - количества коробок...
   Вафель
 
60 - 11.02.19 - 11:05
говорят задачу расположения коробок можно даже на скл решить
   Mikeware
 
61 - 11.02.19 - 11:08
(54) далеко не всегда.
представь для паллета 10*10 набор из одной коробки 9*9, и двадцати коробок 1*5.
   MistaEr
 
62 - 11.02.19 - 11:33
(59) а у меня то коробки разные. например поставил на поддон 2 самые большие коробки, туда ничего уже не поставишь. все маленькие на второй поддон и еще немного на третий поддон. А можно сделать так: на поддон только одну большую коробку, остальное место мелким коробками. Второй поддон так же, глядишь, третий поддон и не понадобится
   Mikeware
 
63 - 11.02.19 - 11:40
(62) я тебе пример приводил для 12 одинаковых коробок.  Именно чтоб вытянуть критерий оптимальности.
-------
"глядишь, третий поддон и не понадобится" -
следовательно, у тебя критерий - количество поддонов, а не свободное место на поддоне.
   Михаил Козлов
 
64 - 11.02.19 - 11:45
(54) Жадный алгоритм в задаче о ранце не всегда дает оптимальное решение.
Пример: 5,4,3,2. Нужно набрать для 10.
Жадный: 5+4. Оптимально: 5+3+2.
   Лодырь
 
65 - 11.02.19 - 11:47
(60) Можно, но лучше не решать. Поскольку размер матрицы вариантов поражает воображение при более менее серьезной размерности задачи.
   Mikeware
 
66 - 11.02.19 - 11:49
(64) у жадного алгоритма первый выбор де должен отсекать оптимальные решения. а у ранца это не всегда так.
   Лодырь
 
67 - 11.02.19 - 11:54
(44) Задача то стандартная, но точного решения не имеет.
   Mikeware
 
68 - 11.02.19 - 12:20
(67) точное  и не обязательно. и точных можнт быть множество, или не быть вообще
   Лодырь
 
69 - 11.02.19 - 13:04
(68) Мне это прекрасно понятно, писал топикстартеру в ответ на его удивление, почему никто еще не подсказал "правильное решения" )
   MistaEr
 
70 - 11.02.19 - 13:19
(51) А это почему никто не заценил?)
   Михаил Козлов
 
71 - 11.02.19 - 13:40
(70) Вы бы содержательно объяснили, как собираетесь решать.
   Garykom
 
72 - 11.02.19 - 13:48
(70) Потому что решать подобные задачи запросами могут только "Ильдаровичи"
   Garykom
 
73 - 11.02.19 - 13:50
(72)+ Имхо это "через задницу" - вроде как и да оно может и работает.... Но в реальных условиях такое можно применять только если нет другого выхода.

Если у тебя клиента/сервера 1С совсем дохлая например и приходится все на sql сервер отправлять для вычислений, который супер-пупер крутой и мощный.
   MistaEr
 
74 - 11.02.19 - 14:05
(73) Я работаю только с цифрами. Из базы данных ничего не беру, следовательно, я думал запрос в цикле не так страшно
   Вафель
 
75 - 11.02.19 - 14:07
может проще загуглить алгоритм решения задачи раскроя
   Mikeware
 
76 - 11.02.19 - 14:07
(70) потому, что это надо оценивать психиатру?
   Garykom
 
77 - 11.02.19 - 14:09
(74) Как раз если бы много брал из базы - это могло быть обосновано, через запросы.

Но млин нафуй так извращаться с "только цифрами" ?

Вы программировать совсем не умеете на языке 1С? Только запросы и СКД да?
   MistaEr
 
78 - 11.02.19 - 14:12
(77) Возможно да. Но сколько тут пишем, никто еще не предложил, даже неработающий код перебора палок от меня до двери (49)
   MistaEr
 
79 - 11.02.19 - 14:13
(78) А сам я не знаю как его написать, это я честно признаю
   Вафель
 
80 - 11.02.19 - 14:14
(78) полное решение можно сделать только через перебор в глубину (всех вариантов)
   MistaEr
 
81 - 11.02.19 - 14:17
(75) Если даже я найду что то подходящее, там все шаблонно. А свое решение всегда проще дорабатывать. У пользователя аппетит придет во время еды, ни вам ли это знать
   Mikeware
 
82 - 11.02.19 - 14:17
(78) для линейного списка - обычный бэктрекинг.
азбука жеж. а вот для двумерного уже сложнее - объемы растут и не квадратично. а есдли двухмерное с ориентацией - еще хуже
   MistaEr
 
83 - 11.02.19 - 14:27
(82) Ну напиши мне неучу эту азбуку в нескольких строчках. входные данные есть
   Вафель
 
84 - 11.02.19 - 14:40
(83) полный перебор тебе написать?
   MistaEr
 
85 - 11.02.19 - 14:41
(84) да, хотя бы в 3-х строчках
   Mikeware
 
86 - 11.02.19 - 14:42
(83)
Вирт "Алгоритмы + структуры данных = программы."
Глава 3. Рекурсивные алгоритмы
3.4. Алгоритмы с возвратом
   Сияющий в темноте
 
87 - 11.02.19 - 15:00
Коробочки с совпадающим одним размером можно попытаться обьединить в группы,группы также могут быть обьединены в группы.
опять же,ориентация коробочек тоже играет роль,т.к.например,поворот на 30 градусов одной коробочки может давать более оптимальное размещение.
   MistaEr
 
88 - 11.02.19 - 15:06
(87) на 30 нет, только 90
   Mikeware
 
89 - 11.02.19 - 15:36
(87) на 30? оригинально...
   MistaEr
 
90 - 11.02.19 - 15:37
(86) Хотя бы ссылку. Говорите это все просто, ну хотя бы какое то начало дайте
   MistaEr
 
91 - 11.02.19 - 15:38
Запутался в своих запросах
   Лодырь
 
92 - 12.02.19 - 04:43
(89) задумался, вполне применимо ) представьте что есть квадратная дырка и прямоугольная коробка. Теоретически может помочь вращение. Свежий взгляд для меня.
   Mikeware
 
93 - 12.02.19 - 06:38
(92) ну ты ещё в параметры вазелин введи...
ЗЫ. "Дырка бывает только в ***!".
   Лодырь
 
94 - 12.02.19 - 06:39
(93) Про дырки не гоните, есть даже вполне общепринятые термины аля "дырочная проводимость". Не говоря уж о черной дыре.
   Вася Теркин
 
95 - 12.02.19 - 06:40
(87) Интересно, правда есть решения при которых неортогональное размещение плотнее ортогонального?
   Лодырь
 
96 - 12.02.19 - 06:41
(95) Думаю, можно придумать пример. Почему нет?
   Лодырь
 
97 - 12.02.19 - 06:42
(95) Пример: Вырожденный случай 1 поддона и одной узкой длинной коробки.
   Mikeware
 
98 - 12.02.19 - 07:14
(97) порви шаблон - поставь ее вертикально!
   Лодырь
 
99 - 12.02.19 - 07:30
(98) Ок, у нас телевизор ) И вертикально не поможет, тк эта скотина плоская.
   Mikeware
 
100 - 12.02.19 - 07:35
а еще можно разрешить разрезать коробки на более мелкие.
  1  2   

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует