Страницы: 1
RSS
Упрощенная задача о рюкзаке (оптимальная загрузка транспорта)
 
Доброго времени суток!
Помогите пожалуйста решить упрощённую задачу о рюкзаке.
Есть 139 единиц груза массой (количество единиц может быть увеличено до 150) от 5.49 до 9.9 тонн, которое надо оптимально загрузить в два вида контейнеров - 27 тонные  и 20 тонные(количество контейнеров неограниченно).  Объём груза не учитывается, но в 27 тонный контейнер можно загрузить 3 единицы груза, а в 20 тонный - 2 единицы груза.
Оптимальным будет считаться решение, при котором будет использоваться наименьшее число контейнеров.
В прикрепленном файле вы можете увидеть вводные данные и желаемый результат.

Изначально писал на питоне алгоритм, который брал бы самое большое значение, прибавлял к нему самое маленькое и подбирал наибольшее, которое в сумме давало бы около 27, но понял, что это - неоптимальный вариант.

Заранее благодарю за помощь!  
Изменено: IN16 - 23.09.2021 15:46:54
 
нужно 60 контейнеров
19 27-тонных
41 20-тонных
Изменено: Ігор Гончаренко - 23.09.2021 16:03:32
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Доброе время суток.
Игорь Нехороших, подскажите пожалуйста, на основании чего вами было сделано заключение, что ваша задача - это упрощённая задача о рюкзаке?
 
Андрей VG, здравствуйте. На основании того, что здесь нет такой переменной как ценность. Возможно, я ошибаюсь, т.к. к программированию имею лишь косвенное отношение. Буду благодарен, если поправите меня.  
 
Андрей VG,
на основании того что в задаче всего два рюкзака
один грузоподъемностью 27 тонн, а второй - 20 тонн)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Ігор Гончаренко написал:
нужно 60 контейнеров
Игорь, если жадненьким алгоритмом, то можно и в 54 штуки уместить. 23 двадцати тонных и 31 двадцати семи тонных. Хотя соглашусь - к решению упрощённому рюкзаком это имеет слабое отношение.
 
У меня получилось 49 контейнеров: 42*27 + 7*20
Изменено: MCH - 24.09.2021 08:05:57
 
Спасибо, очень здорово! А как вы это сделали? Научите меня так же.
Изменено: vikttur - 23.09.2021 22:41:06
 
чтобы так же...
учиться нужно будет лет тридцать (понятно что речь не об этой конкретной задаче, тут достаточно получить код, подготовить данные и научиться нажимать кнопку запуска макроса)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
Цитата
Игорь написал:
А как вы это сделали?
Использовал свои алгоритмы для задачи линейного раскроя/упаковки в контейнеры, отсюда: http://www.excelworld.ru/forum/3-21304-1
Плюс немного ручной работы.
Даже получилось найти решение в 48 контейнера: 43*27 + 5*20
Раскладка во вложении

PS:
получить решение в 49 контейнеров для этого набора данных не сложно, значительно труднее найти решение в 48 контейноеров
Изменено: MCH - 24.09.2021 08:33:47
 
Попробовал формульное решение. Нашёл решение 48 контейнеров. Хотя пришлось немного вручную поработать. Решение зависит от последовательности исходных данных, так как формула заполняет контейнеры последовательно и каждый следующий зависит от уже заполненных.
Первая формула выбирает тройки, но очень долго считает. Вторая подбирает второй и третий к выбранному грузу. Выбирать первый пробовал разными способами. В прямом порядке, обратном, ближайшие значения к среднему и медиане, а также к максимальному, минимальному, среднему и медиане среди нераспределённых. Стабильного эффекта не даёт.
Прикинул, сколько теоретически может быть 20 и 27 тонных контейнеров, чтобы всё разместить. Получилось как у MCH.Вручную задал первые 5 контейнеров на 20 тонн, а потом вручную выбирал комбинацию грузов в первом контейнере на 27 тонн, пока не получил оптимальный вариант полных раскладок.
 
Светлый, спасибо! Интересный подход.
Страницы: 1
Наверх