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

Суть следующая, есть продукция, весом и объемом на несколько контейнеров, есть ограничение по весу и объему контейнера (26,5 тонн, 65 кубов).  Нужно загрузить их, не превышая ограничений по весу и объему чтобы их стоимость в итоге была максимальной. Общий вес получается на 5 контейнеров, а объем на 8 контейнеров, значит что-то объемное и недорогое нужно оставить. Попробовал для начала просто с условием по весу решить. Первая загвоздка, с которой столкнулся, лимит в 200 переменных, поэтому попытался решить ее хотя бы для двух контейнеров. В результате получилось не совсем то, что я запланировал. Я думал, что он расставит кол-во в ячейках каким-то образом, чтобы было понятно, что осталось, что загрузилось. Предполагаю, что без макроса данную задачу не решить, нарыл на форумах по Excel похожее решение, но не совсем соответствующее моей задаче, однако оно работает очень изящно!

Собственно прикрепляю файл с задачей, и решение на VBA. Очень надеюсь, что наставите на путь истинный в решении данной задачи!
 
так нужно?
Решил с помощью OpenSolver, в нем нет ограничения в 200 ячеек
Изменено: MCH - 25.02.2016 16:31:11
 
спасибо вам! очень близко к тому, что я хотел! вечером обязательно попробую данную надстройку в бою!
на самом деле, есть еще условия, которые хотелось бы добавить в данную задачу (комбинация поставщиков, того или иного продукта, кратность упаковке, MOQ и пр.)
буду пробовать, обязательно поделюсь тем, что получится!
 
ТУТ тоже пытаются
Вполне такой нормальный кинжальчик. Процентов на 100
 
Цитата
китин написал: ТУТ тоже пытаются
это я же и пытаюсь!
 
да  я знаю. Правила форума
Цитата
4. Не рекомендуется
     4.1. Создавать одинаковые темы или сообщения в разных форумах (cross-posting).
Публикуя один и тот же вопрос в разных форумах и на дружественных сайтах
вы заставляете сразу нескольких людей параллельно думать над
вашей задачей и обесцениваете усилия тех, кто даст ответ вторым-третьим и
т.д.
Вполне такой нормальный кинжальчик. Процентов на 100
 
В дисциплине Статистика, есть такая формула - Агрегатное состояние. Если ее использовать как компас, то можно упростить задачу.
Т. е. Имеем три критерия вес, объем, цена. если эти критерии связать зависимостью так, чтобы получился один коэффициент, ну а по величине этого коэф. уже и проводить сортировку
 
Цитата
Александр К написал: Если ее использовать как компас, то можно упростить задачу.
Можете предложить набросок алгоритма? В инете много чего есть по теме, например, Предложен способ решения задачи о многомерном рюкзаке с помощью алгоритмов муравьиных колоний - нового перспективного метода оптимизации.... Только вот тумана много, а хотя бы набросков - увы.
 
Цитата
Андрей VG написал: Можете предложить набросок алгоритма?
Алгоритм сводится к тому, чтобы из трех аргументов вывести один коэффициент или два, т.е. нужно вывести значимую величину, загрузить более дорогие или как можно больше по весу.
если взять коэф. отношения вес/цена, то тут чем меньше коэф тем дороже будет сумма загруженного, аналогично будет и с пропорцией объем/цена. и соответственно комплектовать контейнеры по двум коэф. уже проще, чем по трем.
Провести ранжирование полученных коэф. А затем уже заполнять контейнеры учитывая вес и объем.
На мой взгляд два дополнительных столбца нужно вводить.
 
А чем не устраивает предложенное мной решение с помощью целочисленного линейного программирования?
Целевая функция максимизирована, ограничения по весу и объему учтены.
То что предлагает Александр К напоминает "жадный алгоритм" и в реальности можно не найти оптимального решения.
Изменено: MCH - 25.02.2016 23:47:43
 
Доброе время суток
Цитата
MCH написал:
А чем не устраивает предложенное мной решение с помощью целочисленного линейного программирования?
Почему не устраивает? Михаил, всё устраивает, спасибо вам большое. Просто интересуют иные подходы.
 
В данной задаче лимитирующим является объем, а не вес, поэтому в качестве коэффициента для сортировки можно использовать удельную объемную стоимость каждого продукта (цену поделенную на объем)
Сделал вручную решение данным методом, получилось равномерное заполнение каждого контейнера.
 
Цитата
MCH написал: цену поделенную на объем
Логическая зависимость например  - 3 литра стоит 1 рубль, а что выражает рубль деленный на объем?  - размер купюры? математика вещь точная. Если 5 литров, разделить на 3 литра, будет безразмерный коэф. простое отношение двух событий с одной величиной
Или можно рассмотреть объемно/массовый коэф. 1 литр, весит 1 кг. или один кг занимает один литр.
Но деньги в этой задаче делить нельзя, хотя Бог велит делиться, чему мы и учимся у инфузории - они плодятся когда делются ;)
Изменено: Александр К - 27.02.2016 17:38:07
 
Цитата
Александр К написал:
что выражает рубль деленный на объем?  - размер купюры?
Стоимость единицы объёма, а вы что подразумеваете под размером купюры? Её площадь?
 
В файле заполнение контейнеров выполнилось красиво, а вот как на счет перегруза? его ведь тоже надо проверить, вспоминаем загадку из детства - что тяжелее килограмм ваты или килограмм железа? Вагон ваты и вагон кирпичей не сравнимые веса. а вот отношение объем и вес в данном случае перспективнее выглядит.
Вот задумался если объемно весовой коэф поделить на рубль - корректно ли так будет или нет...
 
Как в Excel прописать формулу Мартинагейла? кто знает подскажите
 
Цитата
Андрей VG написал: Её площадь?
Почему площадь? пачка купюр еще и видимую толщину приобретает 5км/ч это привычно, а вот 1/5 ч/км это уже перемещение во времени?
Рассуждаем вслух - Чайник со свистком занимает объем в коробке  - 6 литров, и стоит он 1500р и весит он 2,5 кг... Чайник без свистка 6 литров, 1100р 2,5 кг сколько чайников поместится в коробку объемом 2 куб. метра (2000 л) цена места в коробке имеет значение.
решение задачи, на поверхности 2000/6=333 чайника, но так как объем чайника и вес одинаков, а цена отличается, то свисток в конкуренции за место выигрывает.
Усложням наглядность - в конкуренцию вмешивается утюг 2 литра, весит 2,5 кг, стоит 2500
1000 утюгов вытесняют чайников. Наглость второе счастье, Нужно противоядие - пропорция значимых предметов, значит в коробку должны попасть например на каждые  6 утюгов, 2 чайника со свистком, и два без свистка
 
Цитата
Александр К написал:
Логическая зависимость например  - 3 литра стоит 1 рубль, а что выражает рубль деленный на объем?  - размер купюры? математика вещь точная.
Что в данном случае Вас смущает? 1руб/3л = 0,333 руб/л, т.е. стоимость одного литра.

По условию задачи мы имеем товаров на сумму 64883 руб (или других денежных единиц), весом 135,6 тонн и объемом 551,58 куб.м
для того чтобы распределить их по контейнерам вместимостью 26,5 тонн и 65 куб.м потребуется 5,2 контейнера если ограничиваться по весу или 8,5 контейнера, если ограничиваться по объему.
Поэтому, если размещать товар в 5 контейнеров, то основным ограничением является  объем товаров, а не их вес.
При необходимости максимизировать стоимость товаров необходимо брать только те товары у которых единица объема имеет максимальную стоимость, поэтому я и предложил сортировать только по коэффициентам стоимости объема.

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

Во вложении немного измененная формула "жадного" алгоритма.

И все же, я бы рекомендовал решение не "жадным" алгоритмом, а линейным программированием, в данном случае можно легко задать нужные ограничения по весу и объему, а также по кратности упаковок.
 
Если уместно, то предыдущие мои рассуждения надо удалить. Озадачился вопросом и нашел вот что: (почерпнул тут)

"Среди основных продуктовых характеристик, влияющих на логистические издержки и процесс принятия логистических ре­шений в производстве и сбыте, необходимо указать на цену, тор­говый ассортимент и номенклатуру, габаритные размеры упа­ковки, вес, подверженность повреждению. Часто логистические издержки анализируют по параметру плотности, определяемой отношением веса готовой продукции в торговой упаковке к объе­му упаковки.  Товары, имеющие высокую плотность, требуют, как правило, меньших затрат на транспортировку и хранение, так как обеспечивают более рациональное использование грузоподъ­емности (грузовместимости) транспортных средств. Тарифы за услуги по транс­портировке  обратно пропорциональны плот­ности готовой продукции, (коэф. жадности), поэтому многие фирмы повышают компактность (плотность) готовой продукции в период транспортировки и хранения (например, мебельные фабрики достав­ляют мебель в магазины в разобранном виде).Еще одной продуктовой характеристикой, влияющей на логис­тические издержки, является отношение «цена/вес» («цена/масса»). Продукция с низким уровнем отношения цены к весу, такая, например, как сырьевые полуфабрикаты, будет иметь сравни­тельно небольшие затраты на хранение, но высокие транспорт­ные расходы в процентах от цены продаж. Это объясняется тем, что главным фактором, влияющим на издержки хранения, явля­ется цена товара. В то же время транспортные издержки зависят в основном от веса перевозимого груза и будут тем больше, чем меньше отношение цены к весу (рис. 9.14 б). Поэтому для фирм, продукция которых имеет низкое соотношение «цена/вес», он сводится к работе по льготным транс­портным тарифам"

Конечно, если озадачиться по-взрослому, то к объемным характеристикам надо добавить не просто абсолютную величину, а габаритные величины длинна/ширина/высота, но это уже совсем другая история, и скорее всего требует создания отдельного программного продукта.
 
Еще раз прочел первый пост, и вот какой алгоритм появился: Если ранжировать по плотности (вес/объем), но при этом условно форматировать цветом по цена/объем...
Что скажете по возможности такой реализации.
Думаю, что могут оказаться пустые (недогруженные) места, если окажется большое количество дешевых объемных предметов
Страницы: 1
Наверх