Три актёра озвучивают мультфильм с пятью персонажами
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.
Иванов Петров Сидорова
Персонаж 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
Получим матрицу соответствия
Нужно полное решение этой работы?
Ответ
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)
Решение
Умножением всех элементов на (-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
проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
[-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)
Задать вопрос
на новый заказ в Автор24.
