Пример.
Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.
|
|
Иванов |
Петров |
Сидорова |
|
Персонаж 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.