Рекуррентный метод решения задачи о назначениях

Abstract

Предложен новый метод решения задачи о назначениях, основанный на рекурсивном получении ее оптимального решения. Задача о назначениях формулируется в перестановочно-матричной форме, что позволяет использовать матричный подход к построению оптимального решения. Алгоритм состоит в нахождении взвешенного паросочетания минимального суммарного веса в двудольном графе с 2n вершинами. Вычислительная схема рекуррентного метода решения задачи о назначениях представлена в форме, удобной для реализации на ЭВМ.

Запропоновано новий метод розв’язання задачі про призначення, що ґрунтується на рекурсивному одержанні її оптимального розв’язку. Задача про призначення формулюється в перестановочно-матричной формі, що дає можливість використовувати матричний підхід до побудови оптимального розв’язку. Алгоритм полягає у знаходженні зваженого паросполучення мінімальної сумарної ваги у двочастковому графі з 2n вершинами. Обчислювальну схему рекурентного методу розв’язання задачі про призначення представлено у формі, зручній для реалізації на ЕОМ.

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.