Задача о назначении
Пример.
Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.
|
Иванов |
Петров |
Сидорова |
Персонаж 1 |
6 |
4 |
8 |
Персонаж 2 |
10 |
6 |
8 |
Персонаж 3 |
10 |
0 |
9 |
Персонаж 4 |
0 |
2 |
4 |
Персонаж 5 |
6 |
4 |
0 |
Распределить роли так, чтобы сумма баллов была максимальной. В ответе написать сумму баллов
Решение. Добавим фиктивный персонаж и удвоим столбцы всех актеров
|
И |
И |
П |
П |
С |
С |
Персонаж 1 |
6 |
6 |
4 |
4 |
8 |
8 |
Персонаж 2 |
10 |
10 |
6 |
6 |
8 |
8 |
Персонаж 3 |
10 |
10 |
0 |
0 |
9 |
9 |
Персонаж 4 |
0 |
0 |
2 |
2 |
4 |
4 |
Персонаж 5 |
6 |
6 |
4 |
4 |
0 |
0 |
Фиктивный |
0 |
0 |
0 |
0 |
0 |
0 |
Получим матрицу соответствия
1. Из максимального элемента матрицы вычитаем все элементы и получаем матрицу НеСоответствия .
2. Проведем редукцию по столбцам и получим
Проведем редукцию по строкам и получим
.
2в. Вычеркиваем все нули:
Преобразование:
Оптимальные назначения.
|
И |
И |
П |
П |
С |
С |
Персонаж 1 |
8 | |||||
Персонаж 2 |
10 | |||||
Персонаж 3 |
10 | |||||
Персонаж 4 |
4 | |||||
Персонаж 5 |
4 | |||||
Фиктивный |
0 |
Ответ:
|
Иванов |
Петров |
Сидорова |
Персонаж 1 |
6 |
4 |
[ 8 |
Персонаж 2 |
[10 |
6 |
8 |
Персонаж 3 |
[10 |
0 |
9 |
Персонаж 4 |
0 |
2 |
[4 |
Персонаж 5 |
6 |
[4 |
0 |
Сумма баллов
Иванов → персонажи 2 и 3.
Петров → персонаж 5
Сидорова → персонажи 1 и 4.
< Предыдущая | Следующая > |
---|