Дайте общую математическую формулировку задач дискретного программирования

Класс задач оптимизации, в которых область определения переменных состоит из отдельных изолированных точек, составляет предмет изучения дискретного программирования.

Широкий класс нелинейных и дискретных задач может решаться с использованием идеи рекуррентного подхода (методов типа математической индукции), являющихся основой динамического программирования, идея которого первоначально была предложена Р. Беллманом[1].

Постановка задачи дискретного программирования.Многиезадачи системного анализа, такие как распределение ресурсов, задачи сетевого планирования и управления, календарного планирования, описываются математическими моделями дискретного программирования.

Рассмотрим общую задачу максимизации.

Найти (П.1)

при условиях

(П.2)

(П.3)

где D - некоторое множество R⁽ⁿ⁾

Если множество D является конечным или счетным, то условие (П.3) - это условие дискретности, и данная задача является задачей дискретного программирования (ЗДП). Чаще всего условие дискретности разделено по отдельным переменным следующим образом:

(П.4)

где D - конечное (или счетное) множество.

Если вводится ограничение х_; - целые числа (j=l,2,..., n), то приходят к задачам целочисленного программирования (ЦП), которое является частным случаем дискретного программирования.