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