Анализ показывает, что искомое решение можно свести к решению задачи о рюкзаке . Напомним ее суть. Собираясь в поход, вы хотели бы взять п предметов, каждый из которых имеет массу а, и ценность в походе С,. Вы можете взять с собой предметов по [c.155]
Решение задачи о рюкзаке можно представить последовательностью [c.156]
В исходной задаче о рюкзаке xt может принимать значение только 0 и 1. Но если допустить, что 0 < х, <11, т. е. если допустить, что грузы сыпучие и можно взять любую часть груза, то задача оказывается легко разрешимой. При таком допущении вводится величина, [c.156]
Проводя аналогию решаемой нами задачи с задачей о рюкзаке, можно заменить значение массы а, каждого предмета / значением того либо иного вида ресурса / ,-, необходимого для каждой г -й задачи, а значение ценности предмета в походе С/ — значением либо годового экономического эффекта, либо годовой экономии, получаемых от эксплуатации каждой t -й задачи. [c.156]
По аналогии с задачей о рюкзаке находим ценность [c.157]
Очевидно, и здесь формирование каждого набора задач любой ветви графа должно сводиться к решению задачи о рюкзаке, т. е. при составлении всех без исключения наборов задач общего графа необходимо руководствоваться правилами, изложенными в пп. 5.2 и 5.2.1 книги. [c.178]
Задача о ранце (или "о рюкзаке") 101 [c.465]
Задача о ранце (или о рюкзаке). Так называется задача о наилучшем выборе предметов из общего их количества, т.е. таким образом, чтобы суммарный вес (или габариты) отобранных предметов не превышал (не превышали) заданную величину, а их суммарная полезность или иная общая оценка (количество калорий, общая стоимость и т.д.) была максимальной. Задача о ранце решается, как задача целочисленного линейного программирования, методами динамического программирования и другими. В частности, эта задача применяется при планировании оптимальной загрузки самолетов, кораблей, складов и др. [c.534]
ЗАДАЧА О РАНЦЕ, задача о рюкзаке (knapsa k problem) — задача программирования целочисленного имеется ранец объема V и неограниченное кол-во каждого из N различных предметов Для каждого предмета [c.69]
В процессе систематической организации строительного производства решаются многообразные задачи с использованием методов теории массового обслуживания, теории игр, математического программирования и других методов. К ним относятся задачи о выборе целесообразного количества погрузочно-разгрузочных средств (например, автосамосвалов, отвозящих грунт от одноковшового экскаватора), обслуживающего персонала (бригад слесарей, занятых обслуживанием и ремонтом строительной техники), численности контролеров ОТК, работников аппарата управления задачи о выборе оптимальных смесей (например, составов бетонов и растворов), оптимальном раскрое длинномерных погонажных, листовых и рулонных материалов (например, металлопроката, лесоматериалов, стекла и т.д.), задача о рюкзаке , состоящая в выборе оптимального набора предметов при загрузке контейнеров, и др. На каждой стадии организации используются свои специфические способы. [c.292]
При соблюдении сроков доставки получаем оптимальные маршруты движения для каждого транспортного средства (двенадцатый блок), позволяющие с наименьшими затратами полностью удовлетворить требования потребителей, для которых решается задача загрузки транспортного средства (тринадцатый блок). Математическая постановка известна только для задачи о рюкзаке или ранце , в которой качество загрузки транспортного средства обычно оценивается таким показателем, как количество транспортных средств, используемых для перевозки заданных объемов грузов, что оправдано при организации массовых перевозок. Перевозка мелкопартионных грузов различного наименования, требующая составления развозочного маршрута, выдвигает новое требование к оценке качества загрузки транспортного средства, а именно рациональная загрузка кузова подвижного состава исходя из порядка объезда пунктов на маршруте. Самое простое решение — сформировать заказ каждого клиента на отдельном поддоне, тогда погрузка транспортного средства начинается с заказа последнего клиента. В большинстве случаев груз у грузоотправителя хранится и загружается в подвижной состав по наименованиям, такая задача в настоящее время решения не имеет. [c.339]
Разработанный алгоритм, в основе которого лежат идеи из работы [2], базируется на методе функциональных уравнений динамического программирования (МФУДП), который решает задачу о рюкзаке [c.232]
ЗАДАЧА О РАНЦЕ (или о рюкзаке) [problem of knapsa k] — задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес (или габариты и т.п.) не превышал заданного, а их суммарная полезность, или иная общая оценка, была максимальной. Решается как задача целочисленного линейного программирования методами динамического программирования и др. Применяется, напр., при планировании оптимальной загрузки самолетов, кораблей, складов. [c.101]
В. Ф. Ж и р к о в. Решение задачи рюкзака для случая двухступенчатого гильотинного разреза.— Сборник науч. трудов Владимирского политехи, ин-та, 1969, вып. 9. [c.227]