Здравствуйте, Evgeny20!

1. Для исходной матрицы стоимости

находим эквивалентную матрицу, заменяя каждый элемент его дополнением до максимального. В данном случае максимальный элемент равен 9, поэтому заменяем 9 на 0, 8 на 1, 7 на 2 и т.д. Получаем

2. Редуцируем матрицу по строкам, уменьшая все элементы каждой строки на величину минимального элемента этой строки. В данном случае первая и последняя строки уменьшается на 2, вторая, третья и пятая - на 1, остальные не меняются:

Полученная матрица содержит хотя бы один ноль в каждой строке.
3. Редуцируем матрицу по столбцам, уменьшая все элементы каждого столбца на величину минимального элемента этого столбца. В данном случае все столбцы уже содержат минимум один ноль, поэтому матрица не меняется:

4. В полученной полностью редуцированной матрице методом проб и ошибок находим допустимое решение, содержащее в данном случае пять нулей из разных строк и столбцов. Для первого и третьего столбца, содержащих по одному нулю, выбор однозначен:

для остальных столбцов возможны варианты:

Для исходной матрицы стоимости соответствующие варианты будут иметь вид:

Нас интересует вариант с максимальной суммой выделенных элементов. Для первого и второго варианта она будет равна 7 + 8 + 8 + 9 + 7 = 39, для третьего, четвёртого и шестого - 7 + 8 + 9 + 9 + 7 = 40, наконец, для пятого и седьмого - 8 + 8 + 9 + 9 + 7 = 41. Таким образом, имеем два наилучших решения:

и

которым соответствует следующий выбор претендентов: второй, четвёртый, шестой, седьмой и третий/пятый.