УДК 519.112.71 ДВОЙСТВЕННЫЙ АЛГОРИТМ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ О. А. <...> Медведева, С. Н. Медведев, Г. Д. Чернышова Воронежский государственный университет Поступила в редакцию 08.07.2013 г. Аннотация. <...> В работе рассматривается многокритериальная задача о назначениях. <...> Предлагается алгоритм решения, в основе которого лежит переход к двойственной задаче с последующим использованием метода Удзавы. <...> Предлагается способ формирования функции Лагранжа, позволяющий не решать на каждом этапе задачу о назначениях, что существенно упрощает алгоритм решения. <...> Ключевые слова: дискретная оптимизация, задача о назначениях, многокритериальная задача, двойственная задача, алгоритм решения. <...> In the paper the multicriteria assignment problem is considered. <...> This paper introduces the way of Lagrange function formation, allowing not to solve an assignment problem at each stage that significantly simplifies the decision algorithm. <...> Многокритериальная задача о назначениях возникает, например, при комплектовании штатов на нескольких предприятиях одновременно. <...> Как правило, при этом каждое предприятие стремится минимизировать затраты, связанные с приёмом на работу. <...> Пусть имеется K предприятий (k = 1,…,K), на каждом из которых существует определённый набор вакансий (работ) (j = 1,…,nk ). <...> Кроме того, для каждого предприятия заданы матрицы затрат Cc претендента на j-ую работу на k-ом предприятии. <...> Далее рассматривается ситуация, когда требуется минимизировать затраты каждого из K предприятий. <...> При этом на каждом этапе алгоритма необходимо решать задачу о назначениях, что обременительно в случае большого размера задачи. <...> В данной работе предложен другой вариант формирования функции Лагранжа, что дало возможность существенно упростить алгоритм решения. <...> Обозначим через nn n =+ + число работ на всех предприятиях. <...> Рассмотрим для простоты закрытую задачу о назначениях (m = n). <...> Математическая формализация задачи при этом выглядит следующим образом - общее В xj n,, , nk n i=1 x 11 1 Здесь LXk ij k kK. <...> = 1, Для обеспечения равномерности затрат предприятий <...>