Метод назначений — страница 2

мерой эффективности является стоимость, она минимизируется. Например, пусть имеются четыре должности, на которые необходимо назначить четырех кандидатов, которые в этом случае становятся работниками. Каждому работнику может быть назначена единственная должность. Заметим, что количество должностей равно количеству работников. Необходимо составить матрицу, чтобы показать все возможные взаимосвязи между четырьмя

должностями и четырьмя работниками. Работники представляются строками матрицы, а должности - столбцами, как показано в таблице 1. 16 ячеек матрицы содержат стоимости каждой возможной комбинации должность-работник. Например, стоимость назначения должности 2 работнику 2 составляет $19. Содержимое ячеек матрицы определяет интегральную меру эффективности, которая должна минимизироваться, поскольку является стоимостью. Если

содержимое ячеек матрицы представляет собой прибыль, мера эффективности должна максимизироваться. Таблица 1. Матрица назначений работников на должности Должности 1 2 3 4 Канди- 1 16 9 14 17 даты 2 7 19 8 14 3 15 6 9 10 4 19 17 11 4 Замечание: Содержимое ячеек - стоимости соответствующих комбинаций должность-работник. Cтоимость в этом примере может зависеть от квалификации потенциального работника, его опыта и т.п. Одно из возможных решений

приведенной выше задачи выглядит следующим образом: Назначить должность 1 работнику 2 - стоимость: $ 7 Назначить должность 2 работнику 3 - стоимость: $ 6 Назначить должность 3 работнику 1 - стоимость: $14 Назначить должность 4 работнику 4 - стоимость: $ 4 Общая стоимость этих назначений $31. Является ли эта стоимость наименьшей? Может быть, да, а может быть, и нет. В этом примере существует 24 возможных назначения (4!). Процедура, используемая в

компьютерной модели, должна определять минимальную суммарную стоимость. Приведенная выше задача может быть сформулирована как задача линейного программирования и решена с использованием модуля линейного программирования. Однако, легче и эффективнее для решения задач подобного типа использовать метод назначений, который состоит из следующих четырех шагов. 1. В каждой строке найти наименьшее значение и вычесть его из

содержимого всех ячеек этой строки матрицы. (Получится по крайней мере один нуль в каждой строке.) 2. В столбце, не содержащем нулевых ячеек, найти наименьшее значение и вычесть его из содержимого всех ячеек этого столбца матрицы. 3. "Линейный тест". В матрице назначений провести минимальное число линий (горизонталей (по строкам) и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Если минимальное число