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

Пример.

Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.

Иванов

Петров

Сидорова

Персонаж 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.