ЗАДАЧА О РЮКЗАКЕ

— задача о наилучшем выборе предметов из общего числа предметов таким образом, чтобы суммарный вес (объем, габариты и пр.) выбранных предметов не превышал указанного предела b, а их суммарная полезность была максимальной. Каждый из предметов имеет вес а. и характеризуется коэфф. полезности с. Пусть равно единице, если предмет принимается к укладке, и равно нулю в противном случае. Тогда задача представляет собой задачу целочисленного программирования линейного, заключающуюся в нахождении целых которые максимизируют при условиях:

К 3. о р. сводятся многие задачи размещения оборудования на самолете или ракете, загрузки судов, компактной укладки оборудования и т. д. В различных конкретных задачах коэфф. полезности может описывать различные качества предметов — стоимость, эффективность, калорийность и др. Неравенство (1) может обозначать ограничение на вес, объем, отдельные размеры и др. 3. о р. как задачу целочисленного программирования можно решить Гомори методом, однако наиболее эффективными методами для нее являются ветвей и границ метод и метод функциональных ур-ний программирования динамического.

Лит. см. к ст. Программирование линейное.

Л. Н. Иомзакова.