Служба занятости имеет в наличии 4 вакантных места по разным специальностям

Так как решаем задачу на максимум, то все элементы матрицы умножаем на (-1), прибавляем максимальное число 9 и решаем задачу на минимум.
Так как матрица не является квадратной, то введем фиктивную строку
4326035152450640100640130
Редуцируем матрицу по строкам и столбцам
432603515245064010064013001100
4326024041350540000540030
Получим матрицу
4 3 2 6 0
2 4 0 4 1
3 5 0 5 0
5 2 0 4 3
0 0 0 0 0
Проверяем на оптимальность, назначение не состоялось, проводим через нули прямые, вычеркиваем строку 5, столбец 3 и столбец 5 . В сокращенной матрице находим минимальный элемент, вычитаем его из всех элементов и складываем с элементами, расположенными на пересечениях вычеркнутых строк и столбцов, получаем
2 1 2 4 0
0 2 0 2 1
1 3 0 3 0
3 2 0 2 3
0 0 2 0 2
Редуцируем матрицу по строкам и столбцам
2 1 2 4 0
0 2 0 2 1
1 3 0 3 0
3 2 0 2 3
0 0 2 0 2
Проверяем на оптимальность, назначение не состоялось, проводим через нули прямые, вычеркиваем строку 5, столбец 3 и столбец 5 и строку 2