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

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

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

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

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

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

с₁х₁ + с₂х₂ + . . . . + с_nx_n → max

при условиях

x_j = 1,

x_j = 0

а₁х₁ + а₂х₂ + . . . . + а_nx_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 – целые числа.

Дата добавления: 2014-08-04; просмотров: 234; Нарушение авторских прав

Мы поможем в написании ваших работ!