Примеры задач ДП

1. Задача о рюкзаке. Рассмотрим классическую задачу ЦП, так называемую задачу о рюкзаке (или ранце), которая относится к классу задач с неделимостями. Содержательный смысл задачи состоит в следующем. Турист, отправляясь в поход, собирает рюкзак, масса которого не должен превышать величину М (например, в кг). Турист может положить в рюкзак n видов неделимых предметов, причем i -й предмет имеет массу и ценность c_i (в некоторой шкале ценностей, заранее определенной туристом). Турист стремится укомплектовать рюкзак так, чтобы максимизировать ценность его содержимого. Ценность считается аддитивной, то есть ценность содержимого рюкзака есть сумма ценностей входящих в него предметов. Математически задача, которую решает турист, может быть сформулирована следующим образом:

В этой задаче x_i обозначает количество предметов i -го вида в рюкзаке.

2. Задача о коммивояжере. Имеется n + 1 городов (населенных пунктов) А ₀, А ₁, …, А_n. Задана матрица расстояний между городами. Коммивояжер (торговый агент), выезжая из города А ₀, должен побывать в каждом из остальных городов А ₁, А ₂, …, А_n по одному разу и вернуться в город А ₀. При этом коммивояжер стремится минимизировать пройденное расстояние. Введем переменные-индикаторы:

Теперь математически задачу о коммивояжере можно записать следующим образом:

Здесь - неотрицательные целые вспомогательные переменные. Неравенство в системе условий введено для того, чтобы не было циклов (за исключением цикла, начинающегося и завершающегося в пункте А ₀).

3. Задача о размещении производства. Имеется n пунктов А ₁, А ₂, …, А_n, в которых можно расположить предприятия, выпускающие один однородный продукт (например, цемент). Производственные мощности этих предприятий x_i могут принимать только целые положительные значения (например, это количество печей).

Будем предполагать, что объем продукта, производимого в пункте i пропорционален мощности предприятия x_i и равен величине vx_i.

Производственные затраты также пропорциональны мощностям предприятий. Затраты в пункте i равны величине c_ix_i.

Произведенный продукт потребляется в m пунктах B ₁, B ₂, …, B_m. Потребности в продукте в этих пунктах равны b ₁, b ₂, …, b_m соответственно.

Транспортные затраты перевозки одной единицы продукта из пункта A_i в пункт B_j равны c_ij. Обозначим через x_ij количество продукта, перевозимого из пункта A_i в пункт B_j.

Требуется разместить предприятия в пунктах А ₁, А ₂, …, А_n и определить их мощности таким образом, чтобы минимизировать суммарные производственные затраты и транспортные расходы при условии удовлетворения потребностей пунктов B ₁, B ₂, …, B_m.

Математически эта задача формулируется следующим образом:

(а)

(б)

В целевой функции первое слагаемое характеризует производственные затраты, а второе слагаемое – транспортные расходы. Условие (а) означает, что произведенный предприятиями продукт полностью отправляется потребителям. Условие (б) означает, что потребности пунктов B ₁, B ₂, …, B_m полностью удовлетворяются.

В сформулированной оптимизационной задаче переменные целочисленные, а переменные непрерывные. Такую задачу называют задачей частично целочисленного программирования.

Дата добавления: 2014-01-06