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

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

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

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

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

,

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

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

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

Пример ЗН

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

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

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

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

• Транспортная задача;
• Распределительная задача;
• Задача о назначениях;
• Транспортная задача с промежуточными пунктами;
• Транспортная задача с промежуточными пунктами с запретами;
• Транспортная задача с промежуточными пунктами и ограничением по транзиту;
• Открытая транспортная задача с промежуточными пунктами 1;
• Открытая транспортная задача с промежуточными пунктами 2;
• Открытая транспортная задача с промежуточными пунктами 3;
• Открытая транспортная задача с промежуточными пунктами 4;
• Трёхиндексная транспортная задача.

Ссылки

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