А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 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]).

Предыдущая страница | Оглавление | Следующая страница



Защита от автоматического заполнения   Введите символы с картинки*