Методы оптимальных решений. Часть 3. Задача о назначениях

В процессе управления производством часто возникают задачи, связанные с назначением исполнителей на различные виды работ. Например, подбор кадров и назначение кандидатов на вакантные должности, распределение источников капитальных вложений между различными проектами научно-технического развития, распределение экипажей самолетов между авиалиниями и т.д.
Задача о назначениях (ЗН) является специфической задачей транспортного типа дискретного линейного программирования. При рассмотрении ЗН можно использовать теорию, методологию и результаты линейного программирования, а для решения применять и симплекс-метод, и метод потенциалов, и методы отсечения, и методы ветвей и границ. Однако эти методы в данном случае неэффективны, так как любое допустимое базисное решение задачи о назначениях (в силу специфики задачи) является вырожденным. Оригинальным алгоритмом решения ЗН является венгерский метод, который был разработан и опубликован в 1955 году Харолдом Куном. Ему же принадлежит и название, данное в честь венгерских математиков Кенига и Эгервари.
В данной работе рассматривается исходный вариант метода как поучительный пример интересных и необычных математических методов. Учебное пособие предназначено для студентов экономических специальностей. Оно может быть интересно всем интересующимся теорией принятия оптимальных управленческих решений.