Оптимальное решение, найденное с помощью "линейного" теста

Оптимальные назначения и их стоимости

работа 1 - машине E $3 работа 4 - машине D $5

работа 2 - машине B $4 работа 5 - машине A $3

работа 3 - машине C $2 Суммарная стоимость $17

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

Метод решения задачи назначений требует, чтобы количество должностей и кандидатов было равным. Если это условие не выполняется, компьютер должен увеличить матрицу так, чтобы она стала квадратной. Например, если 5 работников претендуют на 4 должности, компьютер дополнит матрицу до размера 5*5 за счет введения фиктивной должности. Все значения стоимостей для фиктивной должности должны полагаться равными нулю, как показано в таблице 3. Заметим, что стоимость назначения работника 5 должна быть определена и включена в соответствующие ячейки матрицы.

Если имеется больше должностей, чем работников (кандидатов), компьютер также должен увеличить матрицу, чтобы она стала квадратной. Предположим, что имеется 6 должностей и только 4 работника (кандидата). Компьютер дополнит матрицу до размера 6*6, как показано в таблице 4. Заметим, что работники 5 и 6 являются фиктивными и стоимости назначений для фиктивных работников полагаются равными нулю.

Таблица 3. Расширенная матрица назначений - 4 должности для 5 кандидатов