Задачи дискретного программирования.
Многие задачи ИСО, такие, как распределение ресурсов, сетевого планирования и управления, календарного планирования, описываются математическими моделями ДП.
Рассмотрим задачу вида:
(1)
(2)
(3)
Здесь , G- некоторое множество n-мерного пространства . Если множество G является конечным или счетным, то условие (3) – это условие дискретности. В таком случае данная задача является задачей дискретного программирования (ЗДП).
Если вводится ограничение - целые числа, то приходят к задаче целочисленного программирования, которая является частным случаем ЗДП.
Если условие целочисленности накладывается только на часть компонент вектора Х, то задача (1)-(3) будет задачей частично-целочисленного программирования.
Если компоненты вектора Х могут принимать только 2 значения-0 или 1, то (1)-(3) – задача булевского программирования.
В задачах ДП область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со многими трудностями. В частности, практически невозможно применение стандартных приемов, используемых при замене дискретной задачи ее непрерывным аналогом, состоящих в дальнейшем округлении найденного решения до ближайшего целочисленного. Например, рассматривается ЗЦЛП:
Решение соответствующей ЗЛП без требования целочисленности Х*=(0,5; 0; 4,5), а искомое целочисленное решение Х*=(2; 2; 5).
Если множество G конечно, то наиболее простой метод решения задачи (1)-(3) состоит в прямом переборе. Суть метода: в любом порядке перебираются множества возможных значений Х и для каждого значения вычисляется значение целевой функции f(Х). Далее находится наибольшее (наименьшее) значение f(Х*), которое будет соответствовать оптимальному решению Х*ÎG. Однако в реальных задачах хотя G и конечно, но его размерность бывает очень большой, и такой перебор становится практически невозможным.
Поэтому для решения ЗДП разрабатываются специальные методы, основанные на принципе целенаправленного перебора, которые позволяют сократить полный перебор. Методы решения ЗДП по принципу подхода к проблеме делятся на 3 группы:
1. Методы отсечения, или отсекающих плоскостей
2. Метод ветвей и границ
3. Методы случайного поиска и эвристические методы