В общем виде задача о рюкзаке формулируется следующим способом: имеется рюкзак определенного объема и неограниченное количество предметов. Для каждого предмета известен его объем (вес) и ценность (стоимость, эффективность). В рюкзак можно положить целое число предметов различного типа. Цель состоит в том, чтобы суммарная ценность всех находящихся в рюкзаке предметов была максимальна, а их объем (вес) не превышал заданной величины. К подобной формулировке может быть сведена задача максимального использования грузоподъемности подвижного состава, грузовместимости судна, автомобиля и т.п. Такая задача часто возникает при выборе оптимального управления в экономико-финансовых областях (например распределение бюджета отдела по проектам).
Решение задачи в классической постановке
Подобные задачи легко решаются с помощью надстройки "Поиск решения". Подготовлены исходные данные (рисунок ниже). Задача состоит в том, чтобы за счет подбора значений ячеек B16:B19 добиться максимального значения целевой функции (значение ячейки D20).
На первом рисунке ниже показаны ограничения на значения изменяемых ячеек. На втором рисунке ниже приводится результат расчета. Во многих практических случаях данная постановка задачи является слишком упрощенной. Далее будут рассмотрены варианты усложнения постановки задачи.
Модифицированная задача
Одним из дополнительных ограничений, возникающих при практическом использовании данной задачи, могут быть ограничения на необходимое количество предметов определенных видов, которые можно положить в рюкзак. При этом могут возникать варианты задачи, когда требуется строго определенное количество предметов или требуется не менее (не более) заданного количества предметов.
На рисунке ниже показаны исходные данные модифицированного варианта задачи. В этом случае предполагается, что в рюкзак может быть положено не менее некоторого количества предметов.
На следующем рисунке показаны ограничения на значения изменяемых ячеек B16:B19. В данном случае к ограничениям добавлено условие 16:19>=8:11, то есть задано минимальное необходимое количество предметов различных видов.
Решение задачи представлено последнем рисунке.
При необходимости дополнительное условие 16:19>=8:11 может быть изменено. Например, можно установить отдельные ограничения для всех предметов, назначив для некоторых из них точное количество предметов, в то время как для других — условие «не менее» или «не более»
