|
|
|
|
|
Основы теории принятия решениий Учебное пособие. Москва, 2002. 6. Целочисленное программирование Задача о ранце. Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен. Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать спутник, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы. Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные Хk , k = 1,2,…,n (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом Хk = 1, если предмет размещают в ранце, и Хk = 0, если нет, k = 1,2,…,n. Для каждого предмета известны две константы: Аk - вес k-го предмета и Сk - полезность k-го предмета, k = 1,2,…,n . Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид C1 Х1 + С2 Х2 + С3 Х3 + …. + СnХn → max , А1 Х1 + А2 Х2 + А3 Х3 + …. + АnХn ≤ В. В отличие от предыдущих задач, управляющие параметры Хk , k = 1,2,…,n , принимают значения из множества, содержащего два элемента - 0 и 1. К целочисленному программированию относятся задачи размещения (производственных объектов), теории расписаний, календарного и оперативного планирования, назначения персонала и т.д. (см., например, монографию [3]).
|
||