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

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

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

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

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

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

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

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

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

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