Задача о рюкзаке

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

Решение задачи в классической постановке

Подобные задачи легко решаются с помощью надстройки Поиск решения. По аналогии с рассмотренными ранее задачами подготовлены исходные данные (рис. 4.38). Задача  состоит в том, чтобы за счет подбора значений  ячеек B16:B19 добиться максимального значения  целевой функции (значение  ячейки D20).

Рис. 4.38. Исходные данные к задаче о рюкзаке

На рис. 4.39 показаны ограничения на значения изменяемых ячеек.

На рис. 4.40 приводится результат расчета.

Во многих  практических случаях  данная  постановка  задачи является слишком  упрощенной.  Далее будут рассмотрены различные варианты  усложнения постановки задачи.

Рис. 4.39. Ограничения на значения изменяемых ячеек

Рис. 4.40. Решение задачи о рюкзаке

Модифицированная задача

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

На  рис. 4.41 показаны  исходные  данные  модифицированного варианта  задачи. В этом случае предполагается, что в рюкзак может быть положено не менее некоторого количества  предметов.

. Транспортная логистика

Рис. 4.41. Исходные данные к модифицированной задаче о рюкзаке

Рис. 4.42. Ограничения на значения изменяемых ячеек для модифицированной задачи о рюкзаке

На рис. 4.42 показаны ограничения на значения изменяемых ячеек B16:B19. В данном случае к ограничениям добавлено условие $B$16:$B$19>=$D$8:$D$11, то есть задано минимальное необходимое количество  предметов различных видов.

Рис. 4.43. Решение модифицированной задачи о рюкзаке

Решение задачи представлено  на рис. 4.43.

При необходимости дополнительное условие $B$16:$B$19>=$D$8:$D$11 может быть изменено.  Например, можно  установить  отдельные  ограничения для всех предметов, назначив для некоторых из них точное количество предметов, в то время как для других — условие «не менее» или «не более».


 

Источник: Трусов А. Ф. Excel 2007 для менеджеров и экономистов: логистические,  производственные и оптимизационные расчеты (+CD). — СПб.: Питер, 2009. — 256 с.: ил.

Похожие посты:

Вы можете оставить комментарий, или ссылку на Ваш сайт.

Оставить комментарий