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