УДК 519.112.71 ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ ТРЁХИНДЕКСНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ О. А. <...> Медведева, С. Н. Медведев, Г. Д. Чернышова Воронежский государственный университет Поступила в редакцию 15.10.2011 г. Аннотация. <...> В работе рассматривается многокритериальная трёхиндексная задача о назначениях. <...> Предлагается алгоритм решения, в основе которого лежит переход к двойственной задаче с последующим использованием метода Удзавы. <...> Ключевые слова: дискретная оптимизация, задача о назначениях, многокритериальная задача, двойственная задача, алгоритм решения. <...> In the work the multicriteria three-index assignment problem is considered. <...> Рассматриваемая задача возникает, например, при комплектовании штатов на нескольких предприятиях одновременно. <...> Как правило, при этом каждое предприятие стремится минимизировать затраты, связанные с приёмом на работу. <...> Часто возникает ситуация, в которой не каждый претендент умеет делать любую из предложенных работ. <...> Рассмотрим математическую формализацию задачи. дентов на n1 mnk k > В =1 K ijk Ф М Ф У s jk= П 1, 0, делать ю работу на м предприятии в противном случае i - - , где im k K== j nk Известна стоимость cijk ,, , , 11 = 1, . затрат, связанных с назначением i-ого претендента на j-ое место на k-ом предприятии. <...> Требуется распределить претендентов по рабочим местам так, чтобы каждый нанятый претендент занял одно место, каждое место было занято одним претендентом © Медведева О. А., Медведев С. Н., Чернышова Г. Д., 2011 г. 32 приятии соответственно. <...> Условие конкуренции предполагает, что количество претендентов больше числа предложенных мест, то есть Пусть имеется K предприятий и m претен, …,nK мест работы на каждом пред. <...> С этой целью перепишем задачу с учётом следующих изменений коэффициентов целевых функций. <...> Обозначим через im k K j n = c Msijk = М ijk = Ф ijkПcsijk Ф У если если == = 1, , 1, , 1, , k где M – коэффициент штрафа, запрещающий назначение i-ого претендента на j-ую работу на k-ом предприятии в случае, если он не умеет её делать. <...> Требования <...>