Краткие теоретические сведения о методе назначенийСтраница 2
1. В каждой строке найти наименьшее значение и вычесть его из содержимого всех ячеек этой строки матрицы. (Получится по крайней мере один нуль в каждой строке.)
2. В столбце, не содержащем нулевых ячеек, найти наименьшее значение и вычесть его из содержимого всех ячеек этого столбца матрицы.
3. "Линейный тест". В матрице назначений провести минимальное число линий (горизонталей (по строкам) и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено
, т.к. назначения должны быть произведены в "пункты", соответствующие нулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутых строк и столбцов< n, перейти к шагу 4.
4. Среди невычеркнутых строк и столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий. Повторить шаг 3.
Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин (n=5). Матрица стоимостей каждой комбинации работа/машина приведена в таблице 2-1.
Таблица 2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной
Машины | |||||
Работа |
A |
B |
B |
D |
E |
1 |
$5 |
$6 |
$4 |
$8 |
$3 |
2 |
$6 |
$4 |
$9 |
$8 |
$5 |
3 |
$4 |
$3 |
$2 |
$5 |
$4 |
4 |
$7 |
$2 |
$4 |
$5 |
$3 |
5 |
$3 |
$6 |
$4 |
$5 |
$5 |
Процедура решения задачи приведена в таблице 2-2.
Таблица 2-2. Процедура решения задачи о назначениях
Шаг 1
: приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы
Машины | |||||
Работы |
A |
B |
B |
D |
E |
1 |
$2 |
$3 |
$1 |
$5 |
$0 |
2 |
$2 |
$0 |
$5 |
$4 |
$1 |
3 |
$2 |
$1 |
$0 |
$3 |
$2 |
4 |
$5 |
$0 |
$2 |
$3 |
$1 |
5 |
$3 |
$6 |
$4 |
$5 |
$5 |
Другое по теме
Учитель
Этот компонент не является столь универсальным
как задачник, оценка или нейронная сеть, поскольку существует ряд алгоритмов
обучения жестко привязанных к архитектуре нейронной сети. Примерами таких
алгоритмов могут служить обуч ...