Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Задача о назначениях

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Задача о назначениях. Венгерский алгоритм [29:55]
Лекция 14: Задача о назначениях // НОУ ИНТУИТ [57:09]

Задача о назначениях — это задача оптимального назначения работ исполнителям.

Постановка задачи[править]

Пусть имеется n работ (A1,A2,…,An) и n исполнителей (B1,B2,…,Bn). Пусть известны доходы cij от назначения i-ой работы j-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. Тогда задача о назначениях (ЗН) формулируется следующим образом:

ЗН01.PNG,

где xij1 если есть назначение i-ой работы j-ому исполнителю, 0 - если нет назначения.

Метод решения[править]

Задача о назначениях решается венгерским методом.

Пример ЗН[править]

ЗН09.PNG

ЗН10.PNG

Подготовительный этап[править]

ЗН11.JPG

ЗН13.PNG

ЗН14.JPG

Решение венгерским методом[править]

ЗН22.PNG ЗН23.PNG

Оптимальное решение равно ЗН30.PNG

Другие задачи:[править]


Ссылки[править]

  • Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
  • Участник:Logic-samara