Комбинаторный алгоритм назначения целей

Актуальность и цели. Комбинаторные алгоритмы назначения целей (назначения) находят применение при распределении средств поражения (ресурсов). Основным достоинством комбинаторных алгоритмов локального поиска оптимального назначения целей является невысокая асимптотическая сложность. При этом данные алгоритмы, как правило, не обеспечивают нахождение оптимального решения задачи назначения целей. В связи с этим в работе решаются задачи разработки комбинаторного алгоритма, обеспечивающего оптимальное или субоптимальное решение задачи назначение целей. Цель исследования – обоснование вида глобальной и локальной целевой функции для решения задачи назначения целей, разработка алгоритма локального поиска оптимального назначения целей комбинаторным методом и оценка качества решения задачи. Материалы и методы. Разработка комбинаторного алгоритма осуществлена на основе формализованной постановки задачи с использованием матрицы назначений целей. Сумма элементов на главной диагонали матрицы рассматривается как глобальная целевая функция. Минимум суммы элементов находится за счет перестановки столбцов и строк матрицы. Для осуществления очередной перестановки анализируются значения элементов на главной диагонали матрицы, определяется максимальный выигрыш от перестановки. Результаты. Определены функции глобального и локального поиска оптимального решения на основе анализа значений элементов на главной диагонали матрицы назначения целей и функции оценки выполнения необходимого и достаточного условий оптимальности. Решена задача назначения целей с использованием разработанного алгоритма. Рассчитаны статистические оценки результативности назначения целей с использованием разработанного алгоритма. Выводы. Разработанный комбинаторный алгоритм локального поиска минимума целевой функции назначения целей обеспечивает оптимальное или субоптимальное решение задачи назначения целей. Это подтверждается результата- ми назначения целей с использованием алгоритма линейного дискретного программирования и алгоритма локального поиска комбинаторным методом. Асимптотика алгоритма не более O(2n² ) .