Каноническая и многомерная задачи о ранце и их интерпретации

Содержательное описание.

Есть несколько “предметов”, о которых известны их “веса” и “полезности”. Задан “ранец” определённой грузоподъёмности. Требуется поместить в “ранец” “предметы” таким образом, чтобы они все “убрались” в “ранец” и суммарная “полезность” от них была максимальна.

Математическая модель.

Исходные параметры модели.

Пусть i=1,2,...,m - номера предметов, v(i) - вес предмета с номеров i, c(i) - полезность предмета с номером i, i=1,2,...,m, v(0) - вместимость ранца.

Варьируемые параметры модели.

Обозначим через x -m мерный вектор, элементы которого x(i)=1, если предмет с номером i будет помещен в ранец и x(i)=0, если предмет с номером i не будет помещен в ранец.

Ограничения математической модели.

v(i) x(i) v(0), (1)

x(i) {0,1}, i=1,2,...,m. (2)

Постановка оптимизационной задачи.

Критерий оптимальности для задачи о ранце имеет вид:

F(x) = c(i) x(i) max. (3)

Здесь ограничение (1) связано с вместимостью ранца, а условия (2) - естественные условия на введенные переменные.

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

Задача (1) - (3) называется задачей о ранце (канонический случай).

Если кроме ограничения (1) по весу в задаче присутствуют подобные ограничения по другим характеристикам предметов, т.е. ограничения (1) преобразуются в (4):

v(i,j) x(i) b(j), j=1,2,...,m, (4)

где v(i,j) - есть j-ая характеристика предмета с номером i, i=1,2,...,m, j=1,2,...,n, а b(j) -вместимость ранца по j-той характеристике, то задача (2), (3), (4) называется многомерной задачей о ранце.

С помощью математических моделей ранцевого типа описываются следующие прикладные задачи:

- задача загрузки уникального оборудования,

- задача формирования портфеля заказов, обеспеченного ресурсами,

- задача объемного планирования для предприятия,

- задачи загрузки контейнеров и др.

Дата добавления: 2017-02-01; Просмотров: 74; Нарушение авторских прав?; Мы поможем в написании вашей работы!