Задание1
Задача о назначениях
Имеется пять станков различных видов, каждый из которых может выполнять пять различных операций по обработке деталей. Производительности каждого станка при выполнении каждой операции заданы матрицей:
Определить, какую операцию и за каким станком следует закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция.
Решение.
Так как в задаче требуется определить max, a алгоритм метода дан для задач на min, умножим матрицу С на (—1). Сложим полученную матрицу, имеющую отрицательные коэффициенты, с положительным числом, например с числом 10. Получим
Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Вычтем их из соответствующих элементов матрицы, получим
Так как назначение не получено, вычеркиваем строку 2, столбцы 2, 4, 5:
Минимальный элемент равен 1. Вычитаем его из всех невычеркнутых элементов и складываем со всеми элементами, расположенными на пересечении двух линий. Получаем
Оптимальное решение, соответствующее последней матрице, равно
Суммарная производительность: 6 + 6 + 3 + 6 + 7= 28.
Таким образом, на первом станке надо делать 5-ю операцию, на втором — 1-ю операцию, на третьем — 4-ю операцию, на четвертом — 3-ю операцию, на пятом станке — 2-ю операцию. Суммарная производительность: 28 деталей в единицу времени.
