Метод назначений — страница 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 Шаг 2: приведение столбцов - наименьшее значение вычитается из содержимого всех ячеек в столбце матрицы Машины Работы A B C D E 1 $2 $3 $1 $3 $0 2 $2 $0 $5 $2 $1 3 $2 $1 $0 $1 $2 4 $5 $0 $2 $1 $1 5 $0 $3 $1 $0 $2 Шаг 3: выполнение

"линейного теста" - число линий, вычеркивающих все нулевые ячейки, равно 4; т.к.n=5, перейти к шагу 4. Машины Работы A B C D E 1 $2 $3 $1 $3 $0 2 $2 $0 $5 $2 $1 3 $2 $1 $0 $1 $2 4 $5 $0 $2 $1 $1 5 $0 $3 $1 $0 $2 Шаг 4: Наименьшее значение среди содержимого невычеркнутых ячеек равно 1, 1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется к содержимому ячеек, находящихся на пересечении линий Машины Работы A B C D E 1 $1 $3 $0 $2 $0 2 $1 $0 $4 $1 $1 3 $2 $2 $0 $1 $3 4 $4 $0 $1 $0 $1 5 $0 $4

$1 $0 $3 Оптимальное решение, найденное с помощью "линейного" теста Машины Работы A B C D E 1 $1 $3 $0 $2 $0 2 $1 $0 $4 $1 $1 3 $2 $2 $0 $0 $3 4 $4 $0 $1 $0 $1 5 $0 $4 $1 $0 $3 Оптимальные назначения и их стоимости работа 1 - машине E $3 работа 4 - машине D $5 работа 2 - машине B $4 работа 5 - машине A $3 работа 3 - машине C $2 Суммарная стоимость $17 Нематематическое логическое обоснование метода назначения - минимизировать потери прибыли. Например, при назначении работы 1 машине A

вместо машины E убыток составит $2 ($5-$3). Программа, реализующая метод назначений, эффективно выполняет сравнения стоимостей для всего множества альтернативных назначений посредством приведения строк и столбцов. Метод решения задачи назначений требует, чтобы количество должностей и кандидатов было равным. Если это условие не выполняется, компьютер должен увеличить матрицу так, чтобы она стала квадратной. Например, если 5