Задача о назначениях
Постановка задачи. Имеется n видов работ и n исполнителей. Известны затраты , необходимые для того, чтобы -й исполнитель выполнил -ю работу. Нужно назначить исполнителей на работы таким образом, чтобы суммарные затраты на проведение всех работ были минимальными. Каждый исполнитель делает одну работу.
Запишем экономико-математическую модель:
|
Целевая функция
Сумма элементов каждого столбца =1(одна единица, остальные нули) Сумма элементов каждой строки =1 (одна единица, остальные нули)
|
Задача о назначениях является частным случаем транспортной задачи, т.е., данную задачу можно решать методом потенциалов, но задача имеет более простую структуру, чем транспортная, поэтому очевидно, что для нее должны существовать более простые методы решения. Один из них мы рассмотрим.
Венгерский метод решения задачи о назначениях
Идея метода: если
какую-либо строку (или столбец) матрицы
затрат уменьшить на одно и тоже число,
то оптимальное решение задачи не
изменится. Решаем до тех пор, пока затраты
остаются неотрицательными, и не найдется
такого набора
,
при котором
Алгоритм решения:
1. В каждой строке находим минимальный элемент и вычитаем его из каждого элемента строки, далее то же самое проделываем со столбцами.
Пример.
Проектный институт получил заказ на составление проекта. Проект состоит из четырёх этапов, каждый из которых может быть начат после выполнения предыдущего. Этапы проекта могут быть возглавлены четырьмя сотрудниками. Каждый сотрудник предоставил данные о времени выполнения каждой из частей проекта. Матрица затрат имеет вид:
,
где в столбцах – этапы проекта, а в
строках – сотрудники.
Требуется так распределить этапы проекта между сотрудниками, чтобы суммарное время на выполнение проекта было минимальным.
Проводим нулевое назначение, для этого выбираем строку или столбец с минимальным количеством нулей, один из нулей помечаем, а остальные нули данной строки и столбца с помеченным нулем вычеркиваем, и так по всей матрице. Если оставшиеся помеченные нули отвечают полному назначению на работу, то полученный план оптимален. Тогда возвращаемся к исходной матрице, отмечаем клетки, в которых были помеченные нули, суммируем по этим клеткам, получаем оптимальное значение целевой функции. Иначе переходим к шагу 3.
0’ Помеченный ноль вычеркнутый ноль
3. а) Помечаем все строки, в которых нет помеченных нулей;
б) помечаем все столбцы, в которых есть помеченные нули и есть вычеркнутые нули в помеченных строках;
в) вычеркиваем помеченные нули в помеченных столбцах, переходим на пункт а), и так до тех пор, пока есть что помечать.
4. Вычеркиваем все непомеченные строки и помеченные столбцы. Среди оставшихся элементов находим минимальный, вычитаем его из не вычеркнутых столбцов и прибавляем к вычеркнутым строчкам. Переходим на шаг 2.
.
Назначение получено, следовательно, план оптимален.
-
минимальный срок, за который институт
может выполнить свой проект.
Пример
В конкурсе на занятие пяти вакансий (V1, V2, V3, V4, V5) участвуют семь претендентов (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого претендента, на соответствующие вакансии, даны в виде матрицы - С (тестирование производилось по десятибалльной системе).
Определить, какого претендента и на какую вакансию следует принять, причем так, чтобы сумма баллов всех претендентов оказалась максимальной.
С =
-
V1
V2
V3
V4
V5
P1
7
5
7
6
7
P2
6
4
8
4
9
P3
8
6
4
3
8
P4
7
7
8
5
7
P5
5
9
7
9
5
P6
6
8
6
4
7
P7
7
7
8
6
4
Рис.22