вно одну роботу, а кожну роботу виконує рівно один працівник.
Надалі ми під призначенням розуміємо відповідність між працівниками та роботами, що має нульову вартість, після того як ми виробили трансформації, що впливають лише на загальну вартість робіт.
Насамперед запишемо задачу в матричній формі:
де a, b, c, d - працівники, які мають виконати роботи 1, 2, 3, 4. Коефіцієнти a1, a2, a3, a4 позначають вартість виконання працівником «a» робіт 1, 2 , 3, 4 відповідно. Аналогічний сенс мають інші символи. Матриця квадратна, тому кожен працівник може виконати тільки одну роботу.
Крок 1
Зменшуємо елементи порядково. Знаходимо найменший з елементів першого рядка (а1, а2, а3, а4), і віднімаємо його з усіх елементів першого рядка. При цьому хоча б один з елементів першого рядка обнулится. Те ж саме виконуємо і для всіх інших рядків. Тепер у кожному рядку матриці є хоча б один нуль. Іноді нулів вже достатньо, щоб знайти призначення. Приклад показаний в таблиці. Червоні нулі позначають призначені роботи.
0a2«0a4»b1«b2»b3«00c2»c3«c4»d1«0d3»d4'
При великій кількості нулів для пошуку призначення (нульовою вартістю) можна використовувати алгоритм знаходження максимального паросполучення дводольних графів, наприклад алгоритм Хопкрофта-Карпа . Крім того, якщо хоча б в одному стовпці немає нульових елементів, то призначення неможливо.
Крок 2
Часто на першому кроці немає призначення, як, наприклад, в наступному випадку:
0a2 «a3» a4 «b1» b2 & laquo; b3 »00c2« c3 »c4« d1 »0d3« d4 »
Завдання 1 може бути ефективно (за нульову вартість) виконана як працівником a, так і працівником c, зате завдання 3 не може бути ефективно виконана ніким.
В таких випадках ми повторюємо крок 1 для стовпців і знову перевіряємо, чи можливе призначення.
Крок 3
У багатьох випадках ми досягнемо бажаного результату вже після кроку 2. Але іноді це не так, наприклад:
0a2«a3»a4«b1»b2«b3»00c2«c3»c4«d1»00d4'
Якщо працівник d виконує роботу 2, нема кому виконувати роботу 3, і навпаки.
В таких випадках ми виконуємо процедуру, описану нижче.
Спочатку, використовуючи будь-який алгоритм пошуку максимального паросполучення в дводольному графі, призначаємо якомога більше робіт тим працівникам, які можуть їх виконати за нульову вартість. Приклад показаний в таблиці, призначені роботи виділені червоним.
0a2«a3»a4«b1»b2«b3»00c2«c3»c4«d1»00d4'
Відзначимо всі рядки без призначень (рядок 1). Відзначимо всі стовпці з нулями в цих рядках (стовпець 1). Відзначимо всі рядки з «червоними» нулями в цих стовпцях (рядок 3). Продовжуємо, поки нові рядки і стовпці н...
