Критерии подобия динамических задач комбинаторной оптимизации

Аханова Марина Анатольевна, Овчинникова Светлана Валерьевна, Терехова Наталья Владимировна

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

Ключевые слова:комбинаторная оптимизация (КО), комбинаторная конфигурация, динамические задачи, сходство задач, целевая функция.