О назначениях
Дано m = 5 видов машин и m = 5 видов работ с трудоемкостью (маш-ч.), представленной в таблице 10.1. Закрепить работы за машинами таким образом, чтобы суммарная трудоемкость работ была наименьшей.
Таблица 10.1
i/j 1 2 3 4 5
1 9 2 5 6 6
2 9 2 2 6 3
3 4 8 5 7 3
4 9 4 8 5 8
5 9 7 5 11 9
Решение
Исходные данные:
m – виды машин;
– индекс вида оборудования;
m – виды работ;
j= – индекс вида работ;
A = - матрица характеристик,
где aij -
Найти Х = - матрицу назначения,
где Хij – коэффициент назначения, принимающий значения:
Хij =
Целевая функция:
F = - суммарная трудоемкость,
Ограничения:
, ,
где ; .
Для каждого оборудования (строки) выбираем работу с = min (aij и к ней приводим все остальные характеристики работ, характеризующие данное оборудование. Получим приведенные оценки aij , определяемые по формуле:
Приведенные оценки по оборудованию по строкам представим в табл. 10.2.
Таблица 10.2
i/j 1 2 3 4 5
Ai'= 1 7 0 3 4 4
2 7 0 0 4 1
3 1 5 2 4 0
4 5 0 4 1 4
5 4 2 0 6 4
Далее в каждом столбце определяем min a'ij и отнимем ее от всех остальных элементов столбца:
В таблице 10.3 приведенная матрица A’’.
Таблица 10.3
i/j 1 2 3 4 5
Aij''= 1 6 0 3 3 4
2 6 0 0 3 1
3 0 5 2 3 0
4 4 0 4 0 4
5 3 2 0 5 4
3
. Выбор «лучшего» нулевого значения из множества нулей, находящихся в приведенной матрице, производится по коэффициенту
Кij = min aij + min aij ,
i j
где - наименьшая приведенная характеристика в столбце, где находится анализируемый «0»,
- наименьшая приведенная характеристика в строке, где находится анализируемый «0».
Итак, для каждого = 0 определяем Kij (см.табл.10.4)
К1,2 = min {6,3,3,4} + min {0,5,0,2}= 3 + 0 = 3;
К2,2 = 0 + 0; К2,3 = 0 + 0;
К3,1 = 0 + 3 = 3; К3,5 = 0 + 1 = 1;
К4,2 = 0 + 0; К4,4 = 0 + 3 = 3;
К5,3 = 2 + 0 = 2.
Выбирается a"ij = 0 c max Kij, что говорит о наибольшем удалении пары (i,j) от остальных видов оборудования и работ.
Для нашего случая это будет пара (1,2), имеющая max Kij = 3. Паре (1,2) присваивается коэффициент назначения хij = 1 и заносится в матрицу назначения (табл.10.4), исходная матрица назначения Х имеет нулевые значения, т.е. хij = 0.
Таблица 10.4
i/j 1 2 3 4 5
1 0 1 0 0 0
2 0 0 0 0 1
3 1 0 0 0 0
4 0 0 0 1 0
5 0 0 1 0 0
Выделенная пара (1,2) вычеркивается из дальнейшего рассмотрения, т.е
Задать вопрос
на новый заказ в Автор24.
