Пример. Распределить ресурсы по объектам

Распределить ресурсы по объектам.

РЕШЕНИЕ. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим

2-й шаг. Ни одно назначение не получено, необходимо провести модификацию матрицы стоимостей.

3-й шаг. Вычёркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

min = 2.

Вычитаем его из всех невычеркнутых элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим

Итак,

Ответ. Первый ресурс направляем на 3-й объект, второй – на 2-й объект, четвёртый – на 1-й объект, третий ресурс – на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на какой-то объект, то соответствующая стоимость полагается равной достаточно большому числу М.

3. Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не сдержала отрицательных элементов. Затем задачу следует решать как задачу минимизации.

4. Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

Планирование загрузки оборудования

с учётом максимальной производительности

станков

На предприятии пять станков различных видов, каждый из которых может выполнять пять различных операций по обработке деталей. Известна производительность каждого станка при выполнении каждой операции, заданная матрицей

.

Определить, какую операцию и за каким станком следует закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция.

РЕШЕНИЕ. Так как в задаче требуется определить max, а алгоритм метода дан для задач на 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 деталей в единицу времени.