Программирование дискретных структур — это раздел математического программирования, переменные в задачах которого могут принимать лишь дискретные значения, к примеру, целочисленные.
Введение
Дискретное программирование было сформировано в качестве самостоятельной и важной части математического программирования в конце шестидесятых годов прошлого века. В терминологии дискретного программирования могут быть сформулированы многие важнейшие экономические задачи, а также ряд задач из других сфер человеческой деятельности. Помимо этого, к проблемам дискретного программирования могут быть сведены некоторые задачи экстремальной комбинаторики. Дискретное программирование считается осень важным, имеющим большие перспективы, направлением математического программирования.
Дискретное программирование считается разделом оптимального программирования, изучающего экстремальные задачи, с накладываемым на искомую переменную, условием целочисленности, а также условием конечности области допустимых решений. То есть, тут применяется модель общей задачи математического программирования с добавочным ограничением, а именно, $x_1, x_2, ..., x_n$ должны быть целочисленными. Задачей дискретного программирования является задача математического программирования:
$ F(x°) = min F(x)$.
Где: $x \ Є \ G$ является множеством допустимых решений, и оно конечно.
То есть:
$0≤│G│= N ∠ ∞$.
Где $│G│$ является числом элементов множества G.
Программирование дискретных структур
Сперва следует рассмотреть отличительные черты задач дискретного программирования. Одной из основных особенностей является понятие регулярности задачи. Регулярными являются такие задачи, в которых выполнен следующий набор условий:
- Для любой точки x Є G может быть определено необходимым образом понятие наполненной окрестности Gx с G, которая состоит из точек, принадлежащих G.
- Можно представить сравнительно просто необходимые и достаточные условия локальной оптимальности. На базе таких условий локальный оптимум целевой функции F(x) на множестве G можно найти с помощью конечных процессов.
- Локальный оптимум целевой функции должен совпадать с глобальным. К числу задач, которые не являются регулярными, могут быть отнесены, в том числе, так называемые многоэкстремальные задачи, то есть, задачи, где глобальный экстремум не совпадает с локальным экстремумом. К классу нерегулярных задач могут быть отнесены дискретные задачи, в которых множество G не выступает как связное и выпуклое (к примеру, множество G может являться конечным или счетным, или декартовым произведением конечных или счетных множеств).
В задачах регулярного математического программирования большая часть методик базируется на следующем исходном положении, а именно, если точки х1 Є G и х2 Є G являются близкими, то значения f(x1) и f(x2) также являются близки. В задачах дискретной оптимизации данное положение может не выполняться. Если в данном классе задач удастся ввести естественным образом понятие окрестности, то близкие точки из данной окрестности могут сколь угодно сильно иметь отличия по значениям функции.
В определенных задачах дискретной оптимизации не всегда удается естественным образом задать понятие окрестности, тогда оно может вводиться при помощи искусственных построений. По этой причине в задачах дискретной оптимизации близость двух точек х1 Є G и х2 Є G можно оценить только по значениям f{x1) и f(x2).
Допустим, что имеется задача частично целочисленного линейного программирования общего вида. Проблема существовании допустимого решения может быть сведена к определению обстоятельства, является ли разрешимой система линейных равенств и неравенств в целых неотрицательных числах. Общеизвестно, что это трудоемкая вычислительная задача из класса NP (non-deterministic polynomial). По этой причине в общей задаче рассматриваемого класса определение допустимого решения может быть столь же трудоемким, как и нахождение оптимального решения.
По структурной организации математической модели задачи дискретного программирования могут быть поделены на следующие главные классы:
- Задачи, обладающие неделимостями.
- Задачи, выступающие в качестве экстремальных комбинаторных.
- Задачи, имеющие разрывные целевые функции.
- Задачи, базирующиеся на невыпуклых и несвязных областях.
Математические модели задач с неделимостями базируются на требовании целочисленности переменных, которое вытекает из физических условий практических задач. В подобных задачах переменные х1, ..., хп призваны обозначать количества физически неделимых ресурсов или типов продукции, таких как, станки, самолеты, детали и тому подобное.
В экстремальных комбинаторных задачах требуется определить экстремум определенной целевой функции, представленной на конечном множестве, компонентами которого являются перестановки из n символов. Одной из самых простых задач данного класса считается известная задача о назначениях.
Задача о назначениях является распределительной задачей, в которой для исполнения любой работы необходим один и только один ресурс (это может быть один специалист, один автомобиль и так далее), а любой из ресурсов можно использовать на одной и только одной работе. То есть ресурсы являются неделимыми между работами, а работы являются неделимыми между ресурсами. Это означает, что задача о назначениях представляет собой частный случай транспортной задачи.
Очень много экономических систем могут быть охарактеризованы присутствием так называемых постоянных затрат, которые требуется произвести в любом случае, вне зависимости от объема производства. Учет в моделях таких и аналогичных факторов ведет к возникновению в них целевых функций, которые не обладают свойством непрерывности. В качестве примера можно привести транспортную задачу с фиксированными доплатами.
Методики, позволяющие решить задачи дискретного программирования, подразделяются на следующие классы:
- Отсечения.
- Набор комбинаторных методов.
- Набор приближенных методов.
