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

Имеется n предметов, вес предмета j – a _j, его ценность – с _j. Требуется загрузить ранец набором предметов с общим весом А с максимальной суммарной ценностью.

Введем переменные x _j, , имеющие следующий смысл

x _j = 1, если j-й предмет подлежит загрузке,

x _j = 0 в противном случае.

Задача о ранце сводится к максимизации

с ₁ х ₁ + с ₂ х ₂ +.... + с _n x _n → max

при условиях

x _j = 1,

x _j = 0

а ₁ х ₁ + а ₂ х ₂ +.... + а _n x _n ≤ А.

Пример.

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

Обозначим через i = 1, 2,..., m типы бомб, через j = 1, 2,..., n – типы бомбардировщиков, через к = 1, 2,..., р – боевые операции.

Введем величины

bi- имеющийся запас бомб типа i,

aik- эффективность бомбы типа i на операции к,

nj- планируемое число вылетов бомбардировщика j,

wk- "вес", приписываемый командованием операции к.

Искомой величиной здесь является

xijk- количество бомб типа I, подлежащее загрузке в бомбардировщик j при его использовании в операции к.

Задача сводится к минимизации суммарного эффекта

при ограничениях

, i = 1, 2,..., m

x _ijk ≥ 0, x _ijk – целые числа.