7.3. Задача про призначення.

Розглянемо таку задачу. Нехай потрібно розподілити n робіт (операцій) між n робітниками таким чином, щоб мінімізувати сумарні витрати на виконання комплексу робіт. При цьому кожна робота може бути закріплена лише за одним виконавцем, а на кожен робітник може виконувати тільки одну роботу. Витрати Сij на виконання i-й роботи j-м робітником задані матрицею витрат С.

 

Змінні величини даної задачі можуть приймати тільки два значення: Xij =1, якщо i-та робота виконується на j-му верстаті або, у протилежному випадку, Xij=0. Лінійна оптимизаційна модель задачі представлена нижче:

Z=

 

Задача про призначення являє собою окремий випадок транспортної задачі, а значить може бути розв’язана таким самим способом. Проте такий метод є неефективним через виродженість розвязку.

Неважко показати, що додавання до елементів деякого рядка або стовпця матриці С постійної величини не впливає на оптимальність розв’язку. Виконуючи подібні перетворення над деякими рядками (стовпчиками), можна побудувати таку матрицю  , в якій n “незалежних” нульових елементів (“незалежних” нулів) будуть відповідати оптимальному розвязку задачі. Під “незалежними” тут слід розуміти нульові елементи, взяті по одному з кожного рядка і кожного стовпчика. Тобто, ані перший (i), ані другий (j) індекси для базисних нулів не повинні повторюватися.

Описаний спосіб одержання оптимального розв’язку покладено в основу алгоритму Флада (венгерського методу), опис якого наводиться нижче.

Алгоритм Флада

Крок 1. Виконати приведення вихідної матриці вартості призначень по рядках і стовпчиках. Для цього з кожного рядка, що не містить жодного нуля, потрібно відняти мінімальний елемент даного рядка.

Крок 2. Аналогічно слід поступити й зі стовпчиками. В результаті приведення кожний рядок і кожний стовпець матриці вартості будуть містити щонайменше один нульовий елемент.

Крок 3. Провести мінімально можливе число прямих через деякі рядки і стовпчики так, щоб викреслити всі нульові елементи матриці. Якщо кількість таких ліній дорівнює розмірності задачі (n), то поточний розвязок є оптимальним і слід перейти до кроку 5.

Крок 4. Серед не викреслених елементів обрати мінімальний. Відняти його з кожного не викресленого елемента й додати до кожного елемента, що знаходиться на перетині ліній. Повернутися до кроку 3.

Крок 5. Вибрати з матриці n “незалежних” нульових елементів. Їх адреси співпадають з адресами базисних змінних задачі та вказують на оптимальні призначення.

Вибрати з вихідної матриці С елементи з адресами “незалежних” нулів та просумувати. Отримана сума дорівнює загальним витратам на виконання комплексу робіт.

Приклад 7.2 Потрібно оптимальним чином розподілити 4 види робіт між 4 робітниками. Матриця вартості призначень С представлена нижче (табл. 7.5).

Табл. 7.5. Матриця вартості призначень С

 

Табл. 7.6. Матриця вартості призначень, приведена по рядках (крок 1)

 

Табл. 7.7. Матриця вартості призначень, приведена по стовпцях з викресленими нульовими елементами (кроки 2, 3)

 

Табл. 7.8. Матриця, що містить оптимальний розв’язок з виділеними “незалежними нулями” (крок 5)

 

Остання матриця відповідає оптимальному розвязку задачі про призначення, оскільки через усі нулі неможливо провести число ліній, менше від n=4. Склад і значення базисних змінних такі: X11= X23= X32= X44=1. Отже, перша робота має виконуватись першим робітником, друга – третім робітником, третя – другим робітником, четверта – четвертим робітником.

Для визначення сумарних витрат при оптимальному варіанті призначень необхідно повернутися до вихідної матриці вартості призначень і просумувати ті її елементи, номера яких співпадають із номерами базисних змінних в оптимальному розв’язку задачі Zopt=С11+ +С23+ С32+ С44=1+10+5=5=21 (гр.од.).

Необхідно зауважити, що алгоритм Флада може застосовуватись лише до задачі мінімізації. Разом з тим, задача “про призначення” може мати на меті не обов’язково мінімізацію витрат, але й максимізацію деякого показника ефективності призначень (наприклад, продуктивності виконання працівниками комплексу робіт). В останньому випадку задачу максимізації необхідно перетворити на задачу мінімізації. Для цього у вихідній матриці оцінок ефективності призначень знаходять максимальний елемент і віднімають від нього всі інші елементи матриці. До перетвореної таким чином матриці можна застосувати алгоритм Флада.