Пример 4. Найдем минимальную стоимость назначения для выполнения работ на стан­ках за четыре шага

Найдем минимальную стоимость назначения для выполнения работ на стан­ках за четыре шага. Исходные цифры взяты из предыдущей таблицы.

Шаг la. Используя данную таблицу, вычтем минимальное число каждой строки из каждого числа в строке. Результат будет следующий.

Шаг 16. Вычтем минимальное число каждой колонки из каждого числа в колонке. Результат будет следующий.

Шаг 2. Зачеркнем минимальным числом прямых линий все нули. Поскольку только две линии пересекают таблицу, решение не является оптимальным.

Шаг 3. Вычтем минимальное нсзачеркнутое число (2 в этой таблице) из
каждого незачеркнутого числа и прибавим его к числам, находящимся на пересе­
чении двух линий.

Вернемся к шагу 2. Покроем нули прямыми линиями снова.

Поскольку для этого необходимы три линии, то может быть сделано оптималь­ное назначение (шаг 4 на стр. 254). Назначение: R – 34 на машину С, S – 66 на машину В, Т – 50 на машину А.

(Минимальные затраты) = $6 + $10 + $9 = $25.

(Замечание: если бы мы назначили S – 66 на машину А, мы не смогли бы
назначить Т – 50 на место, обозначаемое нулем.)

Некоторые задачи назначения определяют порядок макси­мизации выручки, эффективности или увольнений. Очень легко получить эквивалент минимизационной проблеме, превращая каждое число в таблице в условия потерь. Чтобы представить (осуществить) такое превращение, мы вычтем каждое число в исходной таблице увольнений из наибольшего числа в таблице.

Затем проделаем первый шаг четырехшагового метода решения проблемы назначения. В результате, минимизируя условия по­терь, получаем то же назначение, какое соответствует проблеме максимизации.