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

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

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

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

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

Найти (П.1)

при условиях

(П.2)

(П.3)

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

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

(П.4)

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

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

49.Приведите содержательные постановки задач, приводящие к моделям дискретного программирования.

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

Рассмотрим общую задачу дискретного программирования:

где D - некоторое множество.

Если множество D является конечным или счетным, то условие - это условие дискретности, и данная задача является задачей дискретного программирования.

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

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

Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Таким образом, для решения задач дискретного программирования необходимы специальные методы.

Методы решения задач дискретного программирования по принципу подхода к проблеме можно разделить на две группы: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ.

Математические модели задач дискретного программирования по структуре модели можно разделить на два класса: 1) целочисленные задачи; 2) экстремальные комбинаторные задачи.