Оптимизация, системный анализ и исследование операций

Построение области Парето при комбинировании допустимых решений многокритериальной аксиальной задачи о назначениях

Л. Г. Афраймович, М. Д. Емелин

Нижегородский государственный университет

Аннотация: Рассматривается двухкритериальная трехиндексная аксиальная задача о назначениях, которая уже в однокритериальном случае является одной из классических NP-трудных задач. В рамках данной постановки ставится задача комбинирования допустимых решений, представляющая собой задачу о назначениях на множестве решений, которые содержат только компоненты выбранных допустимых решений. Предлагается полиномиальный алгоритм нахождения Парето-оптимальных решений в задаче комбинирования двух допустимых решений. На его основе строится эвристический подход оценки области Парето многокритериальной аксиальной задачи о назначениях.

Ключевые слова: аксиальная задача о назначениях, многоиндексные задачи, многокритериальные задачи, Парето-оптимальность, комбинирование решений, полиномиальная разрешимость, NP-трудность.

Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 10.11.2024
После доработки: 12.02.2025
Принята к публикации: 26.02.2025

DOI: 10.31857/S0005231025050056

 Англоязычная версия: Automation and Remote Control, 2025, 86:5, 432–444