Задача о ранце

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

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

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

.

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

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

x_j 0, x_j- целое, .

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

Дата добавления: 2015-07-21