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

Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.

Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат - спутник Земли, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы.

С точки зрения экономики предприятия и организации производства более актуальна другая интерпретация задачи о ранце, в которой в качестве "предметов" рассматриваются заказы (или варианты выпуска партий тех или иных товаров), в качестве полезности - прибыль от выполнения того или иного заказа, а в качестве веса - себестоимость заказа.

Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные Xk, K=1,2,…,N (т. е. переменные, принимающие два значения, а именно, 0 и 1). При этом Xk=1, если предмет размещают в ранце, и Xk=0, если нет, K=1,2,…,N. Для каждого предмета известны две константы: Ak - вес K-го предмета, и Ck - полезность K - го предмета, K=1,2,…,N. Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид:

C1X1+ C2X2+ C3X3+ … + CnXnð max,

A1X1+ A2X2+ A3X3+ … + AnXn ≤ B.

В отличие от предыдущих задач, управляющие параметры Xk, K=1,2,…,N, принимают значения из множества, содержащего два элемента - 0 и 1.

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

Укажем два распространенных метода решения задач целочисленного программирования.

< Предыдущая		Следующая >