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

Математическая модель ЗН

Задача о назначениях. Венгерский алгоритм [29:55]

Лекция 14: Задача о назначениях // НОУ ИНТУИТ [57:09]

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

Постановка задачи

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

,

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

Метод решения

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

Пример ЗН

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

Решение венгерским методом

Оптимальное решение равно

Другие задачи:

• Каноническая задача;
• Производственная задача;
• Общая прямая задача линейного программирования;
• Общая двойственная задача линейного программирования;
• Классическая транспортная задача;
• Распределительная задача;
• Транспортная задача с промежуточными пунктами;
• Трёхиндексная транспортная задача;
• Задача целочисленного программирования;
• Задача о рюкзаке.

Ссылки

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