Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.
Иванов Петров Сидорова
Персонаж 1 7 5 5
Персонаж 2 7 6 5
Персонаж 3 8 10 9
Персонаж 4 2 2 3
Персонаж 5 7 4 4
Распределить роли так, чтобы сумма баллов была максимальной. В ответе написать сумму баллов
Указание: добавить фиктивный персонаж и удвоить столбцы всех актеров
И И П П С С
Персонаж 1 7 7 5 5 5 5
Персонаж 2 7 7 6 6 5 5
Персонаж 3 8 8 10 10 9 9
Персонаж 4 2 2 2 2 3 3
Персонаж 5 7 7 4 4 4 4
Фиктивный 0 0 0 0 0 0
Получим матрицу соответствия
Решение.
умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (10) так, чтобы матрица не содержала бы отрицательных элементов:
3 3 5 5 5 5
3 3 4 4 5 5
2 2 0 0 1 1
8 8 8 8 7 7
3 3 6 6 6 6
10 10 10 10 10 10
во вновь полученной матрице в каждой строке будет как минимум один ноль.
0 0 2 2 2 2 3
0 0 1 1 2 2 3
2 2 0 0 1 1 0
1 1 1 1 0 0 7
0 0 3 3 3 3 3
0 0 0 0 0 0 10
Затем такую же операцию проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
0 0 2 2 2 2
0 0 1 1 2 2
2 2 0 0 1 1
1 1 1 1 0 0
0 0 3 3 3 3
0 0 0 0 0 0
0 0 0 0 0 0
проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.Фиксируем нулевое значение в клетке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 6), (4; 5).Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 6), (4; 5).Фиксируем нулевое значение в клетке (3, 4). Другие нули в строке 3 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 6), (4; 5).Фиксируем нулевое значение в клетке (4, 6). Другие нули в строке 4 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 6), (4; 5).В итоге получаем следующую матрицу:
[-0-] [0] 2 2 2 2
[0] [-0-] 1 1 2 2
2 2 [-0-] [0] 1 1
1 1 1 1 [-0-] [0]
[-0-] [-0-] 3 3 3 3
[-0-] [-0-] 0 [-0-] 0 [-0-]
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 4), то решение недопустимое.. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:строку 6, столбец 1, столбец 2, строку 3, строку 4Получаем сокращенную матрицу (элементы выделены):
0 0 2 2 2 2
0 0 1 1 2 2
2 2 0 0 1 1
1 1 1 1 0 0
0 0 3 3 3 3
0 0 0 0 0 0
Минимальный элемент сокращенной матрицы (min(2, 2, 2, 2, 1, 1, 2, 2, 3, 3, 3, 3) = 1) вычитаем из всех ее элементов:
0 0 1 1 1 1
0 0 0 0 1 1
2 2 0 0 1 1
1 1 1 1 0 0
0 0 2 2 2 2
0 0 0 0 0 0
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
0 0 1 1 1 1
0 0 0 0 1 1
3 3 0 0 1 1
2 2 1 1 0 0
0 0 2 2 2 2
1 1 0 0 0 0
во вновь полученной матрице в каждой строке будет как минимум один ноль.Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.После вычитания минимальных элементов получаем полностью редуцированную матрицу.проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Фиксируем нулевое значение в клетке (3, 4). Другие нули в строке 3 и столбце 4 вычеркиваем. Фиксируем нулевое значение в клетке (4, 5). Другие нули в строке 4 и столбце 5 вычеркиваем. Фиксируем нулевое значение в клетке (5, 2). Другие нули в строке 5 и столбце 2 вычеркиваем. Фиксируем нулевое значение в клетке (6, 6). Другие нули в строке 6 и столбце 6 вычеркиваем. В итоге получаем следующую матрицу:
[0] [-0-] 1 1 1 1
[-0-] [-0-] [0] [-0-] 1 1
3 3 [-0-] [0] 1 1
2 2 1 1 [0] [-0-]
[-0-] [0] 2 2 2 2
1 1 [-0-] [-0-] [-0-] [0]
Количество найденных нулей равно k = 6. В результате получаем эквивалентную матрицу Сэ:
0 0 1 1 1 1
0 0 0 0 1 1
3 3 0 0 1 1
2 2 1 1 0 0
0 0 2 2 2 2
1 1 0 0 0 0
определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить максимальное значение прибыли.
[0] [-0-] 1 1 1 1
[-0-] [-0-] [0] [-0-] 1 1
3 3 [-0-] [0] 1 1
2 2 1 1 [0] [-0-]
[-0-] [0] 2 2 2 2
1 1 [-0-] [-0-] [-0-] [0]
Cmax = 6 + 7 + 10 + 3 + 7 + 0 = 33Путь: (2;3), (1;1), (3;4), (4;5), (5;2), (6;6)Альтернативный вариант №2.
[0] [-0-] 1 1 1 1
[-0-] [-0-] [-0-] [0] 1 1
3 3 [0] [-0-] 1 1
2 2 1 1 [0] [-0-]
[-0-] [0] 2 2 2 2
1 1 [-0-] [-0-] [-0-] [0]
Cmax = 6 + 7 + 10 + 3 + 7 + 0 = 33Путь: (2;4), (1;1), (3;3), (4;5), (5;2), (6;6)Альтернативный вариант №3.
[-0-] [0] 1 1 1 1
[-0-] [-0-] [0] [-0-] 1 1
3 3 [-0-] [0] 1 1
2 2 1 1 [0] [-0-]
[0] [-0-] 2 2 2 2
1 1 [-0-] [-0-] [-0-] [0]
Cmax = 7 + 7 + 6 + 10 + 3 + 0 = 33(5;1), (1;2), (2;3), (3;4), (4;5), (6;6)
Решение:
Cmax = 33, (5;1), (1;2), (2;3), (3;4), (4;5), (6;6)
Cmax = 33, (2;4), (1;1), (3;3), (4;5), (5;2), (6;6)
Cmax = 33, (2;3), (1;1), (3;4), (4;5), (5;2), (6;6)
