Журнал «Современная Наука»

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

Аханова Марина Анатольевна (к.с.н., доцент, ФГБОУ ВО «Тюменский индустриальный университет»)

Овчинникова Светлана Валерьевна (к.с.н., доцент, ФГБОУ ВО «Тюменский индустриальный университет»)

Терехова Наталья Владимировна (к.п.н., доцент, ФГБОУ ВО «Тюменский индустриальный университет»)

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

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

Читать полный текст статьи …

Ссылка для цитирования:
Аханова М. А., Овчинникова С. В., Терехова Н. В. Критерии подобия динамических задач комбинаторной оптимизации // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2022. -№05. -С. 41-45 DOI 10.37882/2223-2966.2022.05.02

ПРАВОВАЯ ИНФОРМАЦИЯ:
Перепечатка материалов допускается только в некоммерческих целях со ссылкой на оригинал публикации. Охраняется законами РФ. Любые нарушения закона преследуются в судебном порядке.
© ООО "Научные технологии"