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

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

Машина	Работа
А	В	С
R – 34	$11	$14	$6
S – 66	$8	$10	$11
Т – 50	$9	$12	$7

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

Машина	Работа
А	В	С
R – 34
S – 66
Т – 50

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

Машина	Работа
А	В	С
R – 34
S – 66
Т – 50

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

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

Машина	Работа
А	В	С
R – 34
S – 66
Т – 50

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

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

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

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

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

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

Дата добавления: 2015-03-31