Лекция: Задача о ранце

Задача о ранце является одной из известных задач исследования операций. Турист собирает в рюкзак (ранец) необходимые ему для похода вещи. У него есть нужных ему различных предметов. Каждый предмет характеризуется целочисленным весом и ценностью. Общий вес всех предметов больше, чем величина (грузоподъемность туриста). Цель состоит в выборе предметов для упаковки в рюкзак с максимальной общей ценностью при условии удовлетворения ограничения по грузоподъемности. Эта задача называется бинарной задачей о ранце, т.к. при построении ее модели используются бинарные (т.е. принимающие значения 0, 1) решающие переменные, причем если предмет отобран для упаковки и ‑ если нет. По сути, задача о ранце ‑ пример задачи о распределении ресурсов. Математическая модель имеет вид:

.

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