Задача о ранце. Здесь речь идет о собравшемся в поход путешественнике, который должен упаковать в ранец различные полезные предметы n наименований

Здесь речь идет о собравшемся в поход путешественнике, который должен упаковать в ранец различные полезные предметы n наименований, причем могут потребоваться несколько одинаковых предметов. Имеются m ограничений такого типа, как вес, объем, линейные размеры и т.д. Пусть а_ij- i-я характеристика предмета j-го наименования i= , j= , b_i- ограничения по весу, объему и т.д. Обозначим через x_j количество предметов j-го наименования, запланированное к погрузке в ранец j= . Считается, что известна полезность c_j одного предмета j.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® max.

ЦФ представляет суммарная полезность собранных предметов.

Ограничения имеют вид:

i= , (1)

x_j³ 0, x_j- целое, j= .

Условия (1) означают, что количество отобранных предметов не превышает возможностей погрузки.

Данная задача является задачей линейного целочисленного программирования.