УДК 519.112.71 ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ ОДНОЙ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ О. А. <...> Малюгина, С. Н. Медведев, Г. Д. Чернышова Воронежский государственный университет Поступила в редакцию 05.03.2010 г. Аннотация. <...> В работе рассматривается задача о назначениях с двумя критериями. <...> Предлагается алгоритм решения, в основе которого лежит переход к двойственной задаче с последующим использованием метода Удзавы. <...> Ключевые слова: Дискретная оптимизация, задача о назначениях, многокритериальная задача, двойственная задача, алгоритм решения. <...> Рассматривается задача распределения вакантных рабочих мест между претендентами, в которой каждый претендент умеет выполнять определённый круг работ, не обязательно совпадающий со всеми работами. <...> Предприятие в свою очередь имеет возможность обучать претендентов некоторым работам, если претендент не умеет выполнять какую-либо из них. <...> Обозначим через sij = П1, если ый претендент j-; . <...> Ф М Ф У i - 0, умеет делать ую работу в противном случае В результате каждому претенденту ставится в соответствии вектор — перечень работ, которые он умеет делать: Кроме того, известна стоимость 1 ss j n sij {} i ={} m 1, i == Œ 0,1 ij,1, , , . cij затрат, связанных с назначением i-ого претендента на j-ое место. <...> Рассматривается ситуация, характеризующаяся тем, что имеется возможность дополнительного обучения работам (из некоторого списка работ {} Pn). <...> Известна стоиХ 1, ., © Малюгина О. А., Медведев С. Н., Чернышова Г. Д., 2010 xij = мость 2 претендента j-ой работе. cij затрат, связанных с обучением i-ого Потребуем выполнение следующего условия: если i-ый претендент назначен на j-ую работу, то он не может быть направлен на обучение. <...> При этом затраты, связанные с назначением и с дополнительным обучением, должны быть минимальны. <...> Для использования стандартного алгоритма решения задачи (венгерского метода) вначале произведём корректировку матриц затрат в соответствии с исходной информацией: 1 cij = Ф ijПcsij = 1 cij = Ф ij 2 <...>